Риторическая теория числа

Уважаемые господа, разрешите задать вопрос. Для чего человечеству понадобилась машина Тьюринга в традиционном ее понимании (а другого по-моему и быть не может, тогда это не м.Т.) — очень даже понятно, и о том, что с её помощью сделано, написано море книг. В том числе как мне представляется, и конструктивная математика (точнее математическая логика) эт. е. её порождение. Так вот мой вопрос: зачем понадобилась «конечная» машина Тьюринга, что это такое, и как она работает?

В. Н. Левин:

EEV, Вы пишите мне: «Вашу исходная фраза «ПРЕДСТАВИТЬ ВСЕ простые числа одним набором НЕЛЬЗЯ!» заменяем на: «Представить все простые числа одним множеством нельзя, или, другими словами: множество простых чисел не составляет одно множество».

Протестую. Ваша связка «другими словами» в корне меняет смысл исходной фразы. Допущения «представим», «допустим», лежат в плоскости Субъекта, являются характеристиками ЕГО состояния. В цитате, которую Вы привели, я утверждал о том, что Евклид сделал вывод, выводящий его за пределы его собственных предположений, — я упрекал его за неявное использование ОНТОЛОГИЧЕСКИХ гипотез. Вы Вашей подменой совершаете ту же самую некорректность — делаете прыжок из плоскости свойств СУБЪЕКТА в плоскость свойств ОБЪЕКТА, которому в прыжке ПРИПИСЫВАЕТЕ «естественные» свойства, придуманные Вашей подкоркой. Вы также подразумеваете, что «ЛЮБУЮ совокупность объектов можно объявить множеством, ввиду определения понятия МНОЖЕСТВО». Вот это уже ДУДКИ! Кризис в основаниях математики в начале XX в. случился, в частности, из-за того, что корректного определения понятию множества найти не смогли. Пример — известный парадокс Рассела: «Возьмём множество W — всех таких множеств, которые не являются элементами самих себя. Оно непусто. Например, множество цыплят — не цыпленок. Спрашивается, множество W является элементом самого себя или нет? Если НЕТ — то его надо включить в W. Если ДА (включили) — значит, по определению W — его надо из W исключить! ПАРАДОКС!»

Михаил М.:

Андрей Св., уточните вопрос. Вы спрашиваете вообще о машинах Тьюринга, или создалось впечатление, что есть особые, «конечные» в противовес «бесконечным»? На самом деле таких разновидностей нет. По определению, классическая машина Тьюринга — это конечный автомат, управляющий головкой, под которой находится лента, разбитая на ячейки. В каждом такте работы автомат может перейти в другое состояние, а головка может записать или стереть символ некоторого алфавита в находящейся под ней ячейке, либо может сдвинуть ленту на одну ячейку вправо или влево. Считать ленту изначально бесконечной, либо надстраиваемой по мере необходимости — дело вкуса, на вычисления не влияет. Ничего не изменится также, если считать, что лента конечна, но машина может делать новые ячейки делением крайних ячеек пополам. Зачем придумали такие машины? Так интересно же, что можно вычислять столь простыми агрегатами как выяснилось — всё, что может вычислить любое другое устройство. Доказать это конечно нельзя, но, поскольку более «мощных» вычислителей придумать не получается, можно принять за аксиому, что и гласит «тезис Тьюринга».

В.Н. Левин:

Андрей Св., Вы спрашиваете: «Для чего человечеству понадобилась машина Тьюринга в традиционном ее понимании ... очень даже понятно, ...Так вот мой вопрос: зачем понадобилась “конечная” машина Тьюринга, что это такое, и как она работает».

Уважаемый Андрей! Каждый ПРОФЕССИОНАЛЬНЫЙ программист знает, что «конечная машина Тьюринга» — т. е. «умозрительный» компьютер определит свойства «вычислимости-невычислимости» функций иначе, чем традиционная машины Тьюринга. К чему может привести теоретизирование, отталкивающееся от «конечной машины» (согласен, это уже не машина Тьюринга) — НЕ ЗНАЮ. Тема явно поисковая. Может, кто-нибудь что-то фундаментальное здесь откроет. Как знать заранее?

В добавление — если возникнет вопрос, чем «вычислимость» по «конечной машине» отличается от «вычислимости» по машине Тьюринга.

Для «конечной машины» мало предъявить алгоритм, чтобы считать соответствующую функцию «вычислимой».

Необходимо, чтобы предъявленный алгоритм приводил к объявленному результату в заранее указанных ограничениях по времени и по использованному объему памяти.

Например, если Вы программируете систему противоракетной обороны, то Вы должны уметь в ОГРАНИЧЕННОЙ памяти за считанные секунды размещать и обрабатывать колоссальные объемы информации.

Далеко не каждая «вычислимая» по Тьюрингу функция окажется при этом вычислимой за требуемое время.