Тьюринг. Компьютерное исчисление

Также возможна машина Тьюринга, считывающая информацию из ячеек на нескольких лентах. Предлагались и другие альтернативы, например индетерминистская машина Тьюринга, в которой таблица переходов предусматривает для определенного состояния несколько правил перехода, и их выбор происходит случайно. Однако настоящим вызовом стал класс машин, которые Тьюринг назвал оракулом, или о-машиной. В этой разработке ученый попытался преодолеть ограничения традиционной машины, обеспечив ее достаточной вычислительной мощностью для решения проблемы остановки или задач, решение которых невозможно было выразить с помощью алгоритма. О-машина — это машина Тьюринга, подключенная к черному ящику, называемому оракулом и позволяющему преодолевать ограничения машины. Оракул можно представить как вторую ленту. В этой машине вводится специальный знак — маркер. Между маркерами помещается символ, по которому машине требуется консультация оракула. Дойдя до него, машина Тьюринга переходит в специальное состояние, названное состоянием вызова, и направляет оракулу запрос. Если оракул признает символ принадлежащим к его системе символов, машина переходит в состояние 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 ложь

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