2.1. Тьюринг Алан
Тьюринг Алан Матисон (Turing, Alan Mathison) (1912–1954), английский математик, логик. Тьюринг родился в Лондоне 23 июня 1912. Учился в Шерборнской школе, затем в Кембриджском университете, который окончил в 1935. В том же году был избран членом совета Кингз-колледжа. В 1936–1938 работал над докторской диссертацией в Принстонском университете в США. В 1937 он опубликовал известную работу «О вычислимых числах, с приложением к проблеме разрешимости» (On the Computable Numbers, with an Application to the Entscheidungsproblem), в которой, используя «машины Тьюринга», показал невозможность существования формальной, чисто механической процедуры, которая позволяла бы решать, выводимо ли данное высказывание из некоторого набора математических аксиом. Вместе с К.Гёделем Тьюринг похоронил надежды Д.Гильберта и его последователей, полагавших, что всю математику можно представить в виде набора аксиом и получаемых на их основе теорем. Поскольку машина Тьюринга является абстрактной вычислительной машиной, было доказано, что существует класс логических задач, не разрешимых с помощью любого компьютера.
Во время Второй мировой войны Тьюринг работал в организации, занимавшейся расшифровкой кодов противника. Принимал участие в создании электромеханического устройства для дешифровки текстов, получаемых с помощью немецкой шифровальной машины «Энигма», и в течение некоторого времени возглавлял отдел, осуществлявший радиоперехват. После войны Тьюринг предложил весьма амбициозный проект АСЕ (Automatic Computing Engine – Автоматическая Вычислительная Машина), над которой работал в Национальной физической лаборатории в 1945–1948. Когда работа над проектом замедлилась по бюрократическим причинам, он перешел на преподавательскую работу в Манчестерский университет, где к его услугам был уже действовавший небольшой компьютер «Марк-1». С конца 1940-х годов Тьюринг занимался математическими проблемами биологии. Свои идеи Тьюринг сформулировал в нескольких выступлениях и интервью, а также в статье Вычислительные машины и разум (Computing Machinery and Intellegence), опубликованной в журнале «Майнд» («Mind») (1950). Эта статья стала эпохальной для той отрасли компьютерной науки, за которой впоследствии закрепилось название «искусственный интеллект». В 1951 Тьюринг был избран членом Лондонского королевского общества.
Умер Тьюринг в своем доме в Уилмслоу, близ Манчестера, 7 июня 1954
Тьюринг внес значительный вклад в символическую логику и основания математики, введя понятие абстрактной (воображаемой) «вычислительной машины» (называемой ныне машиной Тьюринга), способной доказывать утверждения механическим путем. Машина Тьюринга послужила основой для создания современного компьютера, объяснив принцип его действия и логические возможности за десятилетие до того, как была сконструирована первая машина такого рода.
Машина Тьюринга – машина, имитирующая о осуществляющая алгоритмические процессы. Концепция такого рода машины возникла в середине 30-х годов 20 века в результате анализа действий человека, выполняющего в соответствии с заранее разработанным планом те или иные вычисления, то есть последовательные преобразования знаковых комплексов. Анализ этот в свою очередь, был осуществлен Тьюрингом с целью решения назревшей к тому времени проблемы поиска точного математического эквивалента для общего интуитивного представления об алгоритме.
Машина Тьюринга – это математическая модель идеализированного вычислительного устройства. Ее удобно представить в виде автоматически функционирующего устройства, способного находиться в конечном числе внутренних состояний и снабженного бесконечной внешней памятью - лентой. Лента разделена на конечное число ячеек, в каждой ячейке ленты в определенный момент времени записан один из символов а0, а1, а2, ..., аN.
В каждой ячейке ленты может стоять любой символ из заданного алфавита, в котором выделен «пустой» символ - признак того, что ячейка пустая.
Машина имеет конечное множество внутренних состояний, начальное (с него начинается работа машины) и конечное состояние, попав в которое, машина прекращает работу.
Кроме ленты, имеется головка чтения/записи, которая, во-первых, умеет двигаться вперед, назад и стоять на месте; во-вторых, умеет читать содержимое, стирать и записывать символы из данного алфавита; в третьих , управляется программой.
Программа представляет собой таблицу, в которой в каждой клетке записана команда. Каждая клетка определяется двумя параметрами – символом алфавита и состоянием машины. Команда представляет собой указание, куда передвинуть головку чтения/записи из текущего состояния, какой символ записать в текущую ячейку и в какое состояние перейдет машина.
Машина Тьюринга - это модель компьютера, и решает она следующую проблему: если для решения задачи можно построить машину Тьюринга, то она алгоритмически разрешима.
И машина Тьюринга, и машина Поста эквивалентны по своим возможностям. Разработаны практически в одно и то же время (в 1936 году) независимо друг от друга.
Можно ли любой алгоритм представить в форме машины Тьюринга? Ответ на этот вопрос дается в виде так называемого тезиса Тьюринга: всякий алгоритм представим в форме машины Тьюринга. Это тезис потому, что его невозможно доказать, так как в нем фигурируют, с одной стороны, интуитивное понятие «всякий алгоритм», а с другой стороны – точное понятие «машина Тьюринга».
Класс нормальных алгоритмов Маркова и класс алгоритмов, представленных в форме машин Тьюринга, совпадают.