Cтраница 3
При этом, разумеется, машина Тьюринга должна работать бесконечно долго. Можно построить машину Тьюринга, вычисляющую значения любой наперед заданной частично рекурсивной функции. Целесообразно, однако, видоизменить описанную выше первоначальную схему машины Тьюринга. Примем, что последний символ sp пятерок символов, описывающих работу машины Тьюринга, может принимать, кроме введенных выше значений 1, и третье значение-остановка машины. С таким дополнением машина Тьюринга превращается в обычную алгоритмическую систему. Она либо преобразует первоначально записанное на ленту входное слово р бесконечно долго, либо после конечного числа шагов преобразований остановится. [31]
Интуитивно мы можем представить, что значит, что один язык программирования мощнее другого или что некоторое подмножество языка является его адекватным ядром. Однако попытки формализовать это понятие наталкиваются на серьезные трудности теоретического характера. Эти трудности связаны с тем, что даже крайне простые языки являются универсальными в следующем смысле. Если язык допускает программирование с использованием простых арифметических функций и функций для обработки списков, то можно моделировать любую эффективную структуру управления - обычно посредством подходящего кодирования работы машины Тьюринга. В частности, в простом языке с некоторой базовой арифметикой можно записать программу для любой частично рекурсивной функции. Обычно такое кодирование очень неестественно и крайне неэффективно. Поэтому, если мы хотим продолжить практическое изучение сравнительной мощности разных языков, следует отказаться от точно заданных функций и рассматривать вместо этого абстрактные, неинтерпретированные программы, или схемы. В следующих разделах излагаются результаты предварительных исследований в этой области. [32]
Таким образом, мы отождествляем гипотезу А. Ньюэллас утверждением отом, что человеческий мозг можно адекватно промоделировать машиной Тьюринга. Машина Тьюринга - - это абстрактная машина, состоящая из бесконечной в одну сторону ленты, разделенной на клетки, и управляющей головки, которая может передвигаться вдоль ленты. Символы входного алфавита, включающие пустой символ, могут размещаться на ленте по одному в клетке. Языки, порождаемые в результате работы машины Тьюринга, называются рекурсивно-перечислимыми. [33]
Будем считать, что он пишет на отдельных листах бумаги. Помимо текущего листа, есть стопка бумаг справа и стопка слева; в любую из них можно положить текущий лист, завершив с ним работу, а из другой стопки взять следующий. Поскольку очень мелкие буквы на листе неразличимы, число отчетливо различных состояний листа конечно, так что можно считать, что в каждый момент на листе записана одна буква из некоторого конечного ( хотя и весьма большого) алфавита. Человек тоже имеет конечную память, так что его состояние есть элемент некоторого конечного множества. Теперь уже видно, что действия человека как раз соответствуют работе машины Тьюринга с большим ( но конечным) алфавитом и большим ( но конечным) числом внутренних состояний. [34]