Машина Алана Тьюринга как воплощение умозрительной концепции компьютера

В математике получило широкое распространение определение алгоритма как точного предписания конечной последовательности однозначных, понятных действий, направленных на достижение указанной цели, исходя из некоторых начальных данных.

Уточним особенности сформулированного определения:

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

2. Отдельный алгоритм зачастую составляет часть другого, более сложного алгоритма. Вообще, решение любой сложной задачи существенно упрощается, если ее можно свести к последовательности подзадач. Это тем более имеет смысл, если подзадачи типичны для широкого круга других задач..

3. Любой алгоритм является дискретным, т. е. распадается на последовательность предписаний, направленных на выполнение некоторых элементарных действий или операций. Эти предписания должны быть понятны исполнителю.

4. Исполнитель должен уметь правильно производить все элементарные действия, содержащиеся в алгоритме.

5. Алгоритмам свойственна массовость, т. е. применимость к различным исходным данным. Решение любой задачи «в общем виде» по существу всегда представляет собой некоторый алгоритм.

6. Наконец, алгоритм должен быть результативным, т. е. приводить к цели за конечное число шагов. Если же процесс решения завершается безрезультатно или не заканчивается вовсе, то говорят, что алгоритм не применим к взятым исходным данным

Несмотря на значительные достижения в разработке и распространении всевозможных алгоритмов в математике, попытки научного подхода к алгоритмам вплоть до XX века были малоуспешными. Причина – трудоемкость строгого формального определения понятия алгоритм. Формулировка, приведенная выше, может быть названа определением лишь в интуитивном смысле. Она не является строгой, В ней нет указаний на то, что может быть объектами алгоритма, а понятия типа «точное предписание», «понятные действия» -- расплывчаты.

Отсутствие формального определения алгоритма приводило к ряду заблуждений. Так Годфрид Лейбниц в свое время пытался построить ни более ни менее как общий алгоритм решения любой алгебраической задачи. Аналогичные попытки в несколько более конкретной форме предпринимались в начале XX века. Имеется в виду список нерешенных проблем, представленный знаменитым математиком Давидом Гильбертом на Международном математическом конгрессе в Париже в 1900 году В этом списке второй значилась проблема нахождения метода, который позволил бы определить.»выполнимо ли данное высказывание на языке формальной логики, т. е. установить его истинность».Безуспешность всех этих поисков постепенно привела к выводу о том, что такие задачи алгоритмически неразрешимы. Проблема формального определения алгоритма стала еще более острой. Ее решение было найдено лишь в 30-х годах прошлого века Аланом Тьюрингом. В основе решения лежало осознание того, что любой алгоритм оперирует не с реальными объектами, а с их символическими отображениями. Несколько позднее эту мысль удалось выразить еще более точно: объектами алгоритмов является информация, представленная в дискретной форме. Выяснилось также, что гарантией точности и однозначности алгоритма служит однозначность и точность языка, на котором он описывается. Причина расплывчатости интуитивного определения алгоритма заключается в том, что его исполнителем неявно предполагался человек, получающий предписания на естественном языке, одна из важнейших особенностей которого – многозначность. Поэтому естественный язык затрудняет процесс формализации многих понятий, в том числе и алгоритма.

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

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

Алфавит информационных слов, с которыми оперирует машина Тьюринга, может быть произвольным, но конечным; он называется внешним. Помимо него, необходим внутренний алфавит для обозначения внутренних состояний и некоторых особых ситуаций. ПРИМЕР!!! В результате работа машины Тьюринга допускает символическое описание в виде специальной таблицы переходов. В каждой строке этой таблицы текущему входному символу и текущему состоянию ставится в соответствие выходной символ, новое состояние и указание, слева или справа от текущего нужно взять следующий обрабатываемый символ. Строки таблицы называются командами, а таблица в целом – программой. Работа МТ начинается с «настройки» на начальное внутреннее состояние и первый символ входного слова. По ним в программе находится нужная команда, а в результате – выходной символ, новое состояние и место, откуда нужно считать следующий входной символ. Так происходит до тех пор, пока не будет достигнуто особое, «конечное» состояние, соответствующее решению задачи.

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

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

Алан Мэтисон Тьюринг родился в Лондоне в 1912 году в семье чиновника. Интерес к науке, и в частности к математике, у него проявился рано, еще в начальной школе. В 1935 году он впервые начал работать в области математической логики и уже через год изобрел свою умозрительную машину, по своему логическому устройству являющейся прообразом цифровых компьютеров, созданных только спустя десять лет. Во время войны Алан Тьюринг принимал участие в работе группы, занимавшейся созданием специальных вычислительных машин для целей дешифровки немецких сообщений и был награжден за свой вклад в криптоанализ орденом Кавалера Британской империи IV степени. В конце 40-х годов Тьюринг занялся проблемой машинного интеллекта, и сегодня анализ этой проблемы Тьюрингом «остался пожалуй самым лучшим из всего, что стоит прочитать каждому, желающему понять суть дела». Кроме выдающихся успехов, которых он добился в области компьютерной науки и машинного интеллекта, в области «чистой» математики Тьюринг получил ряд результатов в теории аппроксимации групп Ли, конечных групп и в вычислении дзета-функции Римана. Умер 8 июня 1954 года, ему было 42 года.