Книга: Размышления о думающих машинах. Тьюринг. Компьютерное исчисление

ПОСТРОИТЬ МАШИНУ ТЬЮРИНГА

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

Одна из первых моделей появилась в 1972 году в Университете Брандейса в Массачусетсе (США). Ее создатель Ира Гилберт преследовал цель обучать студентов основам информатики. Чуть позже появилось несколько версий машины Тьюринга из деталей LEGO. С помощью соединяющихся друг с другом пластиковых кубиков Денис Кузено построил машину Тьюринга, хотя эта модель не была полностью автоматизирована. Для хранения в программируемом микроконтроллере таблицы переходов в ней применялись «умные» кубики LEGO RCX, использующиеся любителями-робототехниками. Еще одна модель машины Тьюринга была построена с помощью LEGO японцем Джо Нагатой. В 2010 году Майк Дейви создал винтажную модель в память о машине, описанной в работе Тьюринга, которая была опубликована в 1936 году. В его устройстве были использованы микроконтроллер Parallax Propeller и SD-карта, на которой хранились данные о состояниях машины.

Все эти примеры показывают, что практическая реализация на уровне hardware машины Тьюринга не так проста. В то же время существует немало примеров моделирования машины Тьюринга с помощью software, в основном потому что такой вариант гораздо доступнее. Среди самых интересных проектов можно назвать «Turing and Post Machines: C++ Simulators» — подборку программ на языке C++ для моделирования машины разных типов (детерминистской, индетерминистской, универсальной, с ошибками, с разными лентами и др.); симулятор Visual Turing, разработанный для операционной системы Windows и позволяющий увидеть в действии разные машины Тьюринга. Еще один пример простой машины Тьюринга на языке Java называется tmsimbgm. Существует оригинальная программа jkturing Джона Кеннеди из Университета Санта-Моники (США), созданная для операционной системы MS-DOS и обновленная для разных версий Windows, хотя этот вариант моделирования несколько более скромный, чем Visual Turing или Jflap. Очень любопытна модель Uber Turing Machine 2011 года, включающая алфавит для написания алгоритмов. Все эти программы вызывают интерес, потому что представляют собой варианты моделирования машины Тьюринга на универсальной машине Тьюринга — компьютере.

Одной из самых интересных задач является возможность создать машину Тьюринга, используя другую машину — игру «Жизнь». Этот автомат был придуман в 1970 году Джоном Хортоном Конвеем (р. 1937), профессором Кембриджского университета, где учился и Тьюринг. Речь идет о модели компьютера, которая была очень популярна среди любителей науки, особенно после того, как ее описал популяризатор математики Мартин Гарднер (1914-2010) в журнале Scientific American. Игра представляет собой клеточный автомат, то есть двумерную решетку, клетки которой заполнены конечными автоматами, также известными как машины конечных состояний. Речь идет об объекте, находящемся в одном из множества состояний, при этом данное множество конечно. Например, светофор может находиться в течение некоторого времени t в состоянии «зеленый», то есть в одном из трех возможных (красный, желтый, зеленый). Другой пример — нейрон, который может находиться в состоянии покоя или возбуждения. В машине Тьюринга, использующей для моделирования клеточный автомат, с течением времени (?) состояния каждого конечного автомата обновляются. Обновление или расчет, каким будет состояние в следующий отрезок времени (? + 1), происходит в соответствии с набором правил, известных как правила перехода, меняющие состояние каждого конечного автомата с учетом его актуального состояния и состояний соседних автоматов.

Оглавление книги