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

В 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