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

Автор книги: авторов Коллектив

сообщить о нарушении

Текущая страница: 2 (всего у книги 7 страниц)

Итак, что представляет собой машина Тьюринга? Из каких частей или компонентов она состоит? А-машина – это абстрактное устройство, не имеющее реального прототипа и представляющее собой простейший компьютер. Она способна считывать и записывать символы на ленте, разделенной на ячейки. Теоретически эта лента бесконечна, то есть не имеет края ни справа, ни слева. Очевидно, что она представляет собой основную память; в современном компьютере эквивалентом можно считать оперативную память – RAM (ОЗУ, оперативное запоминающее устройство). Интересно отметить, что Тьюринг посчитал бесконечную ленту необходимой для компьютера, предваряя этим возникновение одного из важнейших элементов – памяти. По очевидным причинам память компьютера не может быть бесконечной, и этим объясняется «зависание» техники, когда ее памяти недостаточно для выполнения определенной программы или операции.

Но что можно записать на ленту? Представим, что мы располагаем алфавитом, состоящим всего из двух символов – 0 и 1, а также еще одним символом, означающим пустую ячейку, – назовем его пропуск, или В. Система из этих трех символов составляет алфавит, который мы обозначим как А. То есть в каждой ячейке бесконечной ленты будет записан символ: 0, 1 или В (см. рисунок).

Представим себе машину Тьюринга в самой элементарной конфигурации. С одной стороны, ей необходима головка для считывания и записи, с помощью которой считывается содержимое ячейки, а затем стирается и записывается новый символ. В общей модели машины Тьюринга считалось, что после завершения цикла чтения ячейки, стирания содержимого и записи нового символа головка и вместе с ней вся машина сдвигается по отношению к ленте на одну позицию вправо (П) или влево (Л). То есть можно представить, что лента или машина переходит к позиции П или Л. Также машине необходим небольшой объем памяти – реестр, в котором хранится информация о состоянии или конфигурации в определенный момент времени. Реестр похож на светофор, который может быть красным (К), желтым (Ж) или зеленым (3). В конкретный момент времени машина находится в определенном состоянии, и количество возможных состояний является конечным. Обозначим его множество буквой Q (см. рисунок). Представим, что наша машина находится в одном из четырех состояний: E1, Е2, ЕЗ или Е4. Также имеется начальное состояние 1₀, соответствующее записи в реестре при запуске машины в работу.

Итак, машина располагает двумя конечными наборами символов – величинами, записываемыми в ячейки ленты (А = (0, 1, В)), и состояниями реестра машины (Q = (I₀, El, Е2, ЕЗ, Е4)). Для того чтобы машина Тьюринга функционировала, она должна следовать определенному протоколу, словно офисный служащий. Всякий раз, когда служащий выполняет свою работу, он совершает определенную последовательность действий, и после завершения одного шага он должен знать, каким будет следующий. Подобным образом каждый раз, обработав символ на ленте, машина Тьюринга должна до начала обработки следующего символа актуализировать свое состояние.

СОСТОЯНИЯ МАШИНЫ

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

Для того чтобы машина Тьюринга могла менять состояние, используется таблица, названная таблицей переходов, которую обозначим символом Д. В соответствии с этой таблицей, используя правила перехода, или функции, машина после завершения одной операции переходит к следующей. Таким образом, обратившись к таблице, машина Тьюринга после завершения операции актуализирует свое состояние. Каждый раз, когда головка для считывания/записи находит на ленте символ, она соотносит его с символом, описывающим собственное состояние машины и указывающим, что она должна сделать далее для каждой комбинации символов. То есть в таблице представлено состояние ячейки и состояние машины, А х Q. В соответствии с этой комбинацией по таблице определяются следующее состояние Q и новый символ А, который будет записан на ленте вместо считанного, а также то, в каком направлении должно будет перемещаться устройство по ленте: вправо (П) или влево (Л). Таким образом, в самом простом виде работа машины Тьюринга определялась тремя элементами: состоянием машины Q, алфавитом А и таблицей А, в которой собирается информация о каждом завершенном шаге машины Тьюринга для выполнения следующего.

Для того чтобы понять, как функционирует машина Тьюринга, приведем простой пример с тремя состояниями Q = {Е1, Е2, ЕЗ} и лентой памяти, ячейки которой могут содержать символы А = {0, 1}. Будем считать начальное состояние 1₀ равным Е1, головка считывания/записи находится во второй ячейке слева от рассматриваемого участка ленты, например имеющего вид 011110. Если таблица переходов сформирована тремя таблицами ниже, по одной на каждое из состояний El, Е2 и ЕЗ, то как будет вести себя машина?

Символ ленты

Записанный символ

Переход

Следующее состояние

0

1

Л

Е2

1

0

П

ЕЗ

Символ ленты

Записанный символ

Переход

Следующее состояние

0

0

Л

ЕЗ

1

1

П

Е1

Символ ленты

Записанный символ

Переход

Следующее состояние

0

1

Л

Е1

1

0

П

Е2

Читая таблицу переходов и учитывая, что каждая операция реализуется в единицу времени (t₀, t₁, t₂,...), получаем, что начальное положение t₀ имеет следующий вид.

Согласно таблице переходов и учитывая, что машина в начальный момент времени t₀ находится в состоянии Е1, символ на ленте 1, в ячейке будет записан 0, шаг в следующую ячейку справа, состояние изменится на ЕЗ.

Действия машины для следующего момента времени t₁, когда она будет находиться в состоянии ЕЗ, указаны в таблице переходов. Затем, после того как головка считает в ячейке символ 1, машина перейдет в состояние Е2, в ячейке будет записан 0, шаг в следующую ячейку вправо.

После завершения предыдущей операции наступит момент времени t₂. Так как машина находится в состоянии Е2 и из ячейки считывается 1, то, следуя указаниям таблицы переходов, в ячейку будет записано 1, устройство перейдет вправо, и машина изменит состояние на Е1.

Последний момент времени, t₄. Машина находится в состоянии Е1, в считываемой ячейке стоит символ 1. Согласно таблице переходов, в ячейку будет записан 0, шаг вправо, переход в состояние ЕЗ.

У-МАШИНА ТЬЮРИНГА. МОЖЕТ ЛИ МАШИНА БЫТЬ УНИВЕРСАЛЬНОЙ

Одним из ограничений машины Тьюринга является то, что она ведет себя как компьютер, выполняющий единственный алгоритм, то есть способный реализовывать только одну задачу. С исторической точки зрения одной из первых машин Тьюринга стала система AGC (Apollo Guidance Computer – бортовой управляющий компьютер миссии «Аполлон»). Эта машина была главным бортовым компьютером миссий NASA, позволивших совершить доставку человека на Луну 20 июля 1969 года. Задолго до этой эпопеи, осознавая присущее его машине ограничение, Алан Тьюринг сделал расширение своей машины, назвав результат универсальной машиной Тьюринга, или у-машиной. Речь идет о машине Тьюринга, которую можно использовать в виде любой другой машины Тьюринга, то есть способной обрабатывать другие алгоритмы. Таким образом, компьютер – это пример универсальной машины Тьюринга. Еще один пример – смартфоны, или мобильные телефоны, работающие как мини-компьютер.

ЛУННАЯ МИССИЯ «АПОЛЛОН-11»

Один из самых интересных примеров машины Тьюринга – миникомпьютер миссий «Аполлон», организованных NASA для доставки человека на Луну. Это была машина Тьюринга, разработанная в Массачусетском технологическом институте для навигации и прилунения. Среди множества мини-компьютеров, созданных для разных миссий, AGC (Apollo Guidance Computer – бортовой компьютер «Аполлона») был самым популярным. Программа, с помощью которой можно моделировать работу мини-компьютера миссий «Аполлон», а также выполнять современные программы, написанные для Windows, Linux, Mac Os или другой операционной системы, называется Virtual AGC. Она написана на Ассемблере, низкоуровневом языке программирования, в связи с тем что память мини-процессора AGC – всего 38912 символа длиной 15 бит (последовательность 15 единиц и нулей). Программа моделирует виртуальный компьютер в машине AGC, выполняющий программу, хранящуюся в его памяти. На лунном модуле мини-компьютер AGC использовал программу Luminary, в то время как на командном модуле применялась программа Colossus. Обе они доступны на симуляторе.

Модель мини-компьютера миссий «Аполлон» на эмуляторе Virtual AGC.

Превращение автоматической машины Тьюринга в универсальную представляет собой решительный шаг вперед в истории компьютеров. А если рассмотреть еще один факт, имеющий большую важность (знаменитый тезис Чёрча – Тьюринга), то можно сделать вывод, что изобретение компьютеров было уже совсем близко. Американский математик Алонзо Чёрч – одна из ключевых фигур математической логики – совместно с Аланом Тьюрингом сформулировал тезис, названный тезисом Чёрча – Тьюринга. Говоря современным языком, этот тезис устанавливает, что универсальная машина Тьюринга (и, таким образом, компьютер) может решать любые задачи, решение которых может быть выражено в виде алгоритма. Однако нужно учесть, что в то время слово алгоритм еще не использовалось, вместо него говорили «эффективный метод вычисления». Под алгоритмом мы понимаем совокупность шагов или правил, приводящих к определенному результату или решению задачи. Следовательно, для компьютера синонимом алгоритма является решение задачи. Всякий алгоритм обладает рядом свойств.

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

– Во-вторых, шаги или правила должны быть определены четко и однозначно. Приведем простой школьный эксперимент для «измерения числа я»: 1) обмотайте банку бумажной лентой, лишний материал ленты обрежьте; 2) снимите бумажную ленту и измерьте ее длину; 3) поместите банку между двумя книгами и измерьте расстояние между краями книг, соприкасающимися с банкой, для получения диаметра; 4) вычислите частное длины и диаметра. Полученная величина и будет я.

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

– В-четвертых (это также дополнительное требование), путь к решению должен состоять из минимального количества шагов.

Например, процедура стирки состоит из следующих шагов.

– Шаг 1. Разобрать одежду по цветам. Белые вещи и вещи светлых тонов должны стираться отдельно от цветных и темных вещей.

– Шаг 2. Прочитать этикетки на одежде, чтобы выяснить максимальную температуру и способ стирки (а также сушки, глажки и так далее).

– Шаг 3. Насыпать в лоток стиральной машины порошок.

– Шаг 4. Уложить одежду в стиральную машину. Выбрать соответствующую программу и температуру.

– Шаг 5. Достать выстиранную одежду.

– Шаг 6. Конец программы.

На уроках математики в школе используется много простых алгоритмов. Например, решение системы уравнений методом подстановки предусматривает следующий алгоритм.

– Шаг 1. В обоих выражениях выделить одну неизвестную.

– Шаг 2. Уравнять выражения.

– Шаг 3. Решить уравнение.

– Шаг 4. Подставить полученную величину в одно из двух уравнений, где выделена одна неизвестная.

– Шаг 5. Решить получившееся в предыдущем пункте уравнение.

– Шаг 6. Конец программы.

Эти заключения приводят нас к выводу о том, что компьютер представляет собой машину Тьюринга, работающую с алгоритмами. Когда решение задачи может быть выражено в виде алгоритма, считается, что задача разрешима. Швейцарский инженер Никлаус Вирт (р. 1934), автор языков программирования «Алгол», «Модула-2» и «Паскаль», участвовал в разработке определения программы в 1975 году. Согласно его определению, программа – соединение алгоритма с формой организации данных внутри программы; организация данных также получила название структура данных. Отсюда происходит знаменитое выражение Вирта: алгоритм + структура данных = программа.

АЛОНЗО ЧЁРЧ, ЛЯМБДА-ИСЧИСЛЕНИЕ И «ЛИСП»

Несмотря на то что с Тьюрингом всегда ассоциировалась машина, носящая его имя, после того как с трудами этого исследователя познакомился другой замечательный математик, Алонзо Чёрч (1903-1995), последний опубликовал работу, которая отнимала у машины Тьюринга часть оригинальности.

В 1930-е годы Чёрч вместе со Стивеном Клейни (1909-1994) ввели Х-исчисление – абстрактную математическую систему для формализации и анализа вычислимости функций.

Функция – математическое выражение у = f(x), отражающее связь между двумя переменными, например длиной х и весом у синих китов, в виде выражения у = 3,15х – 192. Это понятие, предложенное в XVII веке Декартом, Ньютоном и Лейбницем, в 1930-е годы было пересмотрено с целью разработки общей теории математических функций.

Новый синтаксис

Одной из заслуг Чёрча считается введение нового синтаксиса для представления данного класса математических выражений. Так, если, например, мы вычислим значение выражения (+(*23)(*56)), при этом звездочка – оператор умножения, то получим 36, поскольку (2 · 3) + (5 · 6) = 6 + + 30 = 36. Математическая функция должна быть абстрактной. Также для λ-исчисления используется более сложное выражение (λx. + x1), означающее: «Функция (представленная символом λ) от переменной (здесь х), которая имеет вид λ(x) (представлена здесь как.), добавляет (оператор +) величину переменной (то есть х) к 1». Мы можем несколько усложнить предыдущее выражение, записав ((λ х. + х1)3), результат которого равен 4, поскольку мы указали, что х = 3. Предсказуемо, что для преобразования всех элементов λ-исчисления мы можем усложнять операции. Другой заслугой такого типа исчисления стало его влияние на теорию, изучающую компьютерное программирование.

Проблема остановки

Однако если λ-исчисление и получило известность, то только благодаря тому, что Чёрч использовал эту абстракцию для изучения проблемы остановки, придя в результате к понятию разрешимой задачи, то есть идеи, лежащей в основе машины Тьюринга. В свою очередь, Тьюринг в 1937 году доказал, что λ-исчисление и его машина эквивалентны, то есть представляют собой два пути, по которым можно прийти к одному результату. Когда машина Тьюринга обрабатывает одно из указанных выражений, например (+31), она останавливается после того, как получен результат, в данном случае 4, то есть эта задача является разрешимой. С практической точки зрения λ-исчисление вдохновило развитие так называемых функциональных языков программирования, одним из примеров которых является «Лисп» – важнейший язык искусственного интеллекта. Появился он в 1958 году благодаря Джону Маккарти (1927-2011), автору термина «искусственный интеллект». Среди характеристик, которые язык унаследовал от λ-исчисления, – использование скобок:

(defstruct persona

(имя Alan)

(возраст 41))

или более просто:

(format t «Привет, Тьюринг!»)

ДРУГИЕ МАШИНЫ ТЬЮРИНГА

В 1982 году нобелевский лауреат в области физики Ричард Фейнман (1918-1988) выдвинул захватывающую задачу, к которой мы обратимся в последней главе. После обнаружения ограничений в вычислительных способностях машин Тьюринга, помимо известной проблемы остановки (поговорим о ней в следующем параграфе), Фейнман предсказал существование вопросов, которые никогда не смогут быть обработаны компьютером. Он предположил, что и машины Тьюринга, и компьютеры не могут применяться для моделирования явлений квантовой природы, наблюдаемых на уровне атомов и не соответствующих классической физике. Ученый хотел сказать, что квантовые явления относятся к неразрешимым задачам, следовательно, они не могут быть обработаны обычным компьютером: машина Тьюринга, помимо прочих особенностей, должна для этого находиться одновременно в разных состояниях или одновременно считывать данные из разных ячеек. Компьютер для обработки квантовых явлений должен быть способным воспринимать не только состояния 0 и 1, но и возможные средние значения между 0 и 1 и одновременно использовать разные регистры оперативной памяти. После этого, в 1985 году, другой английский физик израильского происхождения, Дэвид Дойч (р. 1953), разработал новый класс машины Тьюринга, в котором эти ограничения были преодолены, – квантовую машину Тьюринга. Квантовые компьютеры способны моделировать неразрешимые задачи, такие как квантовые феномены, и, естественно, их ждет широкое применение.

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

Курт Гёдель (1906-1978), создатель теоремы о неполноте, пошатнувшей основы математики.

Деталь машины Тьюринга, построенной из деталей конструктора LEGO.

Алан Тьюринг участвует в забеге на длинную дистанцию в Доркинге (Англия) в 1946 году. В этом забеге он занял второе место.

Также возможна машина Тьюринга, считывающая информацию из ячеек на нескольких лентах. Предлагались и другие альтернативы, например индетерминистская машина Тьюринга, в которой таблица переходов предусматривает для определенного состояния несколько правил перехода, и их выбор происходит случайно. Однако настоящим вызовом стал класс машин, которые Тьюринг назвал оракулом, или о-машиной. В этой разработке ученый попытался преодолеть ограничения традиционной машины, обеспечив ее достаточной вычислительной мощностью для решения проблемы остановки или задач, решение которых невозможно было выразить с помощью алгоритма. О-машина – это машина Тьюринга, подключенная к черному ящику, называемому оракулом и позволяющему преодолевать ограничения машины. Оракул можно представить как вторую ленту. В этой машине вводится специальный знак – маркер. Между маркерами помещается символ, по которому машине требуется консультация оракула. Дойдя до него, машина Тьюринга переходит в специальное состояние, названное состоянием вызова, и направляет оракулу запрос. Если оракул признает символ принадлежащим к его системе символов, машина переходит в состояние 1, в противном случае – в состояние 0. Оракул стал первой попыткой исследований Тьюринга в области, которая впоследствии получит название гипервычислений, или сверхтъюринговых вычислений y, то есть вычислений, находящихся за пределами возможностей компьютера, предложенного самим английским ученым.

ПРОБЛЕМА ОСТАНОВКИ. ПОЧЕМУ КОМПЬЮТЕР «ЗАВИСАЕТ»

После создания машины Тьюринга английский ученый стал изучать проблему разрешения (по-немецки – EntscheidungsproЫетп) с помощью собственной концепции, известной с тех пор как проблема остановки. Проблема состоит в том, чтобы предсказать, остановится машина Тьюринга, «зависнет», как это делают современные компьютеры, или продолжит работать после считывания очередного символа. Таким образом, вопрос, на который пытался дать ответ Тьюринг, состоял в возможности применения механического процесса (специальной программы) для определения, остановится ли другая программа при получении на входе определенной величины или данных. Сегодня на любом компьютере можно легко повторить некоторые простые опыты по этому и другим вопросам, над которыми работал Тьюринг. Учитывая сходство между машиной Тьюринга и компьютером, на котором выполняется программа, решение проблемы будет состоять в ответе на вопрос, остановится выполнение программы или она будет выполняться бесконечно. Рассмотрим эти две ситуации со следующими программами на языке BASIC-256. Так, эта программа остановится после выполнения

print «Привет, Тьюринг!»,

а вторая будет выполняться вновь и вновь без остановки:

r=true

while г

print «Привет, Тьюринг!»

end while

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

Предположим, мы даем название остановка (кандидат, вход) программе, способной выяснить, остановится ли выполнение другой программы, которую мы назвали кандидат; произойдет ли остановка при получении определенных входных данных, которые мы назовем вход. Действительно, если мы представим программу остановка (кандидат, вход) в форме псевдокода, получим

Программа остановка (кандидат, вход)

if input = вход и кандидат → остановится

then остановка (кандидат, вход) = истина

if input = вxoд и кандидат → не остановится

then остановка (кандидат, вход) = ложь;

Представим, что, используя программу остановка (кандидат, вход), мы пишем другую программу, которая называется парадокс (вход):

программа парадокс (вход)

if остановка (кандидат, вход) = ложь

then return истина

else return ложь

Сделаем в наших рассуждениях еще один шаг и вслед за Тьюрингом обозначим через Р программу парадокс. Далее выполним программу остановка (Р, Р). Если программа, вложенная в главную, вернет ответ «Ложь», значит, программа Р не останавливается, получив в качестве входных данных программу, идентичную себе самой, тогда основная программа парадокс (Р), вернув значение « Истина», должна остановиться, но это невозможно и, значит, ложно.

Напротив, если программа остановка (Р, Р) вернет ответ «Истина», так как программа Р остановит свое выполнение, получив в качестве входных данных величину Р, тогда программа парадокс Р не остановится, возвращая значение «Ложь». Принимая во внимание все противоречия, Тьюринг сделал вывод, что программа остановка (или halt) не позволяет оценить Р. Другими словами, проблема остановки неразрешима.

Хотя и не существует программы, которая служила бы универсальным инструментом для удовлетворительного решения проблемы остановки, ученые решили, что можно написать программу, дающую ответы на отдельные случаи, то есть, говоря современным языком, частные программы. Этот класс программ был назван программами PHS (partial halting solver), или программами, частично решающими проблему остановки. Однако со временем ситуация была сочтена такой же неразрешимой, как и с проблемой остановки. Вновь используя язык BASIC-256, напишем программу, которая получает на вход программу Р$. Задача состоит в получении на выходе (output) сообщения о том, останавливается ли выполнение программы Р$:

input Р$

if Р$ = «halt» then

print «программа останавливается ДА»

else

print «программа останавливается НЕТ»

endif

end

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

БЕСКОНЕЧНОСТЬ МАШИН ТЬЮРИНГА

Современный компьютер можно считать машиной Тьюринга, имеющей внутри себя еще одну такую машину. Для пояснения этой идеи приведем в пример один из первых компьютеров, ENIAC (Electronic Numerical Integrator And Computer). Этот мастодонт начала компьютерной эры может быть представлен как машина Тьюринга с тремя лентами: одна лента – для считывания входных данных, другая – для записи и возвращения результата, а третья выполняла роль памяти.

Современные компьютеры

В современном компьютере машина Тьюринга, имевшаяся в ENIAC, должна быть изменена, принимая во внимание, что входящая лента раздваивается на вспомогательную память (например, жесткий диск, SD– или флеш-карта) и клавиатуру. В такой машине в виде ленты выхода можно представить монитор, лента памяти соответствует RAM (ОЗУ). Если мы будем рассматривать операционную систему (разные версии Windows Microsoft, или Linux/Unix, или Mac OS) как машину Тьюринга, получится, что совокупность программ, позволяющих управлять ресурсами компьютера, – это машина Тьюринга, контролирующая другую такую же машину, которой является сам компьютер. Кроме того, когда программист пишет программу – совокупность инструкций, то есть исходный код, – он, в свою очередь, должен перевести эти инструкции в машинный или двоичный вид с помощью компилятора, который также можно считать машиной Тьюринга. После преобразования программа может быть выполнена микропроцессором – важнейшим устройством в компьютере. Лежащая в основе всего модель представляет и компьютер, и программу, с помощью которой мы переводим программы на язык, делающий возможным их выполнение, и операционную систему как машины Тьюринга. Другими словами, «все это программы, все это software», к которым нужно добавить электронные схемы, hardware, как будто бы речь идет о software, – эта важная идея является следствием разработок Тьюринга.

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

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

Одна из первых моделей появилась в 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), происходит в соответствии с набором правил, известных как правила перехода, меняющие состояние каждого конечного автомата с учетом его актуального состояния и состояний соседних автоматов.

СОЗДАНИЕ МАШИНЫ ТЬЮРИНГА С ПОМОЩЬЮ ИГРЫ «ЖИЗНЬ»

В конце XX века несколько ученых и любителей науки задались вопросом: можно ли построить машины Тьюринга с помощью игры «Жизнь»? Поль Рендель 2 апреля 2000 года создал модель машины Тьюринга с помощью клеточного автомата Джона Хортона Конвея, а 10 февраля 2010 года повторил свой замечательный опыт. В первой модели использовалась решетка 1714 х 1647, с помощью конечных автоматов которой была создана машина Тьюринга. Она имела три возможных состояния и могла обрабатывать на ленте памяти три разных символа. В эксперименте 2010 года была создана модель универсальной машины Тьюринга. Возможность моделирования машины Тьюринга с помощью игры «Жизнь» привела к удивительному выводу: игра «Жизнь» имела аналогичные с компьютером возможности. Более того, любое природное явление, например формирование колец Сатурна или взаимодействие зайцев и волков, можно смоделировать с помощью компьютера. Существуют и другие успешные примеры создания машин Тьюринга с помощью игры «Жизнь», некоторые из них даже получили собственные названия: MRM (Minsky Register Machine) или ее универсальная версия URM, а также CoreWorld, LogiCell и другие.