4.3.2. Примеры вычислений

Приведем примеры вычислений на машине Тьюринга-Поста. Полагаем

А = {ао,1}, Q = {qo,...,qn}. Вводим следующее представление натуральных чисел в виде слов словаря А

О = 1° = ао, 1 = l\ 2 = И = 1\ 3 = 111 = l п = 1 = Г,...

п раз

Пример 4.4. Вычислим функцию f{n) =71 + 1.

Начальное машинное слово ТП = giaolao. Это число п. Программа ф

gieo 92Д, 921 qR, qao ql, ql qsL, qaao goao. Вычисление

gieolao «0921"ao ... aol"q2ao eolgal aol~gзl ... ... аодз1+ 93001"+ goaol"+ (stop). Машинное слово goaol+ - это число n + 1. Следовательно, „-1-1 = l"+i =ф(1")

f(n)=n + l.

Пример 4.5. Вычислим функцию д{п,т) = п + т.

Начальное машинное слово m = giaolaoleo- Это пара чисел (n,m).

Программа ф

giao qR, 921 qR, qao 9з1, дз1 QsR, дзо qiL, qil qsao, qsao qeL, gel qeL, qeao qoao-Вычисление

giaolaolao -aog2laol"ao ... -aolgaaolao ао1"дз1™+ао ... ао1"+™+дзао дз1"+™д41ао • 931"+™9500 aol+-gelao ... - aogel+ao • -geaol+ao -goaol+ao (stop). Машинное слово goeol+ao - это число n + m. Следовательно,

71-Ьт=1"+" =(1"+™)

д{п, т) = п + т.

4.3.3. Тезис Тьюринга

Вспоминая тезис Чёрча, естественно провести следующее рассуждение: если вычислимые функции - это частично рекурсивные, а последние вычисляются на мапшнах Тьюринга-Поста, то не содержится ли в этом рассуждении ответ на то, что такое вычислимая функция. Утверждение, которое хотелось бы сделать, но которое не поддерживается строгим доказательством, - это [8, с.266]

Тезис Тьюринга. Все вычислимые частичные функции вычисляются на машинах Тьюринга-Постл.

4.3.4. Универсальная машина Тьюринга-Поста

Машина Тьюринга-Поста называется универсальной, если она может при определенных начальных входных данных вычислить любую функцию, которая вычислима на какой-либо машине Тьюринга-Поста.

Иначе говоря, с учетом тезиса Тьюринга можно сказать, что универсальная машина Тьюринга-Поста способна вычислить любую вычислимую функцию. Доказано, что универсальная машина Тьюринга-Поста существует.

4.4. алан тьюринг

Алан Матисон Тьюринг (23.6.1912-7.6.1954) - английский инженер и математик. Член Лондонского королевского общества (1951). Родился в Лондоне. Окончил Кембриджский университет (1935). Работал сначала там же. Математические работы Тьюринга в основном посвящены математической логике и вычислительным машинам. Кроме того, ему принадлежат отдельные результаты в области аппроксимации групп Ли конечными группами и в вычислении дзета-функции Римана. В 1936 году Тьюринг выяснил связь общерекурсивных функций с обшдми идеями «вычислимости» и «выводимости». Используя схему абстрактной машины, доказал ряд важных для кибернетики положений в области математической логики.

Во время второй мировой войны занимался электроникой, позднее возглавил работу по созданию вычислительных машин в Национальной физической лаборатории в Таддингтоне. Однако его проект «автоматического вычислительного устройства» (Automatic Computing Engine - АСЕ), законченный в 1946 году, был признан излишне самонадеянным и не получил одобрения. По сути, эта разработка содержала первое подробное описание компьютера в современном понимании этого слова .

В Манчестере в 1951 году в результате развития проекта MADAM вводится в действие один из первых в мире полностью работос1ЮСобных компьютеров Ferranti Mark 1, и Тьюринг начинает первые вычислительные эксперименты по нелинейному моделированию формообразования у растений и раковин. Он пишет работу по вопросам морфогенеза -научному направлению, определяюш;ему математические закономерности в развитии форм живых существ.

Конечно, расчет конфигурации цветка был не единственной и не главной задачей, выполнявшейся на «Марке 1». Спустя несколько лет он был использован при создании английской атомной бомбы. Сохранились свидетельства того, что Тьюринг проводил на нем и «несанкционированные» вычисления. Что еще считал «Марк» - известно тсшько ему и Тьюрингу. Возможно, это были работы для правительственного Департамента кодов GCHQ (Government Code unit) - организации, продолжавшей работы по дешифровке, начатые во время войны в Блечли. С этой организацией Тьюринг не прекращал сотрудничество. На этот раз в центре внимания GCHQ были шифры советской резидентуры в Англии. Но не исключено, что вычислительные эксперименты касались ранних «детских» увлечений Тьюринга: в этот период он разрабатывает квантовую теорию спиноров - компонентов элементарных частиц - и работает над некоторыми вопросами теории относительности. Тогда же он проявляет серьезный интерес к методике психоанализа Юнга и записывает все свои сны. Эти записи не сохранились.

8 июня 1954 года Алан Матисон Тьюринг, кавалер ордена Бри-

По статье Далидовича Г. Заметки об искусственном интеллекте:

Рис. 4.2:

(1912-1954).

Л.Тьюринг