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

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

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, — эта важная идея является следствием разработок Тьюринга.