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

Курт Гёдель (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 века.