хранить произвольный символ (на практике достаточно двух: 0 и 1). Кроме того, есть считывающая головка, способная обследовать одну ячейку ленты. После обследования лента может быть смещена на одну ячейку влево или вправо по отношению к головке. МТ руководствуется набором правил перехода. В каждый момент она находится в определённом состоянии, которому соответствует некоторое подмножество правил перехода. Каждое правило гласит: если машина находится в состоянии X с символом Y в ячейке ленты, пребывающей под считывающей головкой, то символ Y следует заменить новым символом Y′, переместить ленту на одну ячейку влево или вправо и изменить состояние на X′. Произвольное множество правил может быть само записано в виде последовательности символов на ленте МТ. Тьюринг использовал это свойство для определения понятия универсальной машины Тьюринга (УМТ), которая представляет собой МТ, способную имитировать произвольную МТ по её описанию на ленте. Такая способность УМТ напоминает способность молекулы ДНК кодировать саму себя[375].

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

Entscheidungsproblem в переводе с немецкого дословно означает «проблема (или задача) решения», по-русски мы обычно говорим «проблема разрешения». Впервые проблема была сформулирована в 1928 г. Давидом Гильбертом, едва ли не самым известным математиком XX столетия. Вопрос задачи звучит следующим образом: существует ли алгоритм, который, получив на вход утверждение, отвечает «да» или «нет» в зависимости от того, является ли данное утверждение «универсально справедливым»? В соответствии с теоремой Гёделя о полноте исчисления предикатов утверждение является «универсально справедливым» тогда и только тогда, когда оно может быть выведено из аксиом. Поэтому проблему разрешения можно рассматривать как вопрос о существовании алгоритма, позволяющего определить, можно ли, используя правила логики, вывести заданное утверждение из аксиом. В 1936 г. Чёрчу удалось доказать принципиальную невозможность создания такого алгоритма. В том же году, но несколько позже этот же результат независимо получил и Тьюринг, и именно этому посвящена его статья «О вычислимых числах…». Сегодня мы называем полученный результат теоремой Чёрча — Тьюринга.

Тьюринг доказал, что его «универсальная вычислительная машина» способна выполнять любые мыслимые математические вычисления, если они могут быть представлены в виде алгоритма. Для того чтобы показать неразрешимость проблемы разрешения, Тьюринг доказал, что проблема остановки (halting problem) для машин Тьюринга неразрешима: невозможно гарантированно за конечное количество шагов алгоритмически решить, остановится ли когда-нибудь произвольно взятая машина Тьюринга.

Хотя доказательство Тьюринга было опубликовано после аналогичного доказательства Чёрча, выполненного на основе лямбда-исчисления, подход Тьюринга выглядел более наглядным. Идея УМТ, то есть такой гипотетической машины, которая способна выполнять задачи любой другой вычислительной машины, оказалась весьма продуктивной. Согласно тезису Чёрча — Тьюринга, машины Тьюринга и лямбда-исчисление способны вычислять всё, что можно в принципе вычислить.

В 1939 г. Джону Россеру удалось доказать, что все три подхода — общерекурсивные функции Гёделя, универсальная машина Тьюринга и лямбда-исчисление Чёрча — являются взаимно эквивалентными и, следовательно, все три могут быть равнозначно использованы для определения эффективной вычислимости.

Интересными побочными продуктами изысканий Тьюринга стали понятия тьюринг-эквивалентности и тьюринг-полноты. Две машины P и Q являются тьюринг-эквивалентными, если машина P может симулировать работу машины Q и, наоборот, машина Q может симулировать работу машины P. Тьюринг-полной машиной называется машина, способная симулировать работу машины Тьюринга. Разумеется, не существует физических устройств, обладающих бесконечным объёмом памяти — аналогом бесконечной ленты МТ. Но это ограничение при использовании понятия тьюринг-полноты обычно игнорируется, то есть тьюринг-полными называют машины, которые при наличии у них бесконечной памяти могли бы выполнять любые вычисления, доступные МТ.

В свете теоретических работ Тьюринга над проблемой разрешения становится более понятной идея, лежащая в основе теста Тьюринга. Признать наличие разума у машины можно будет тогда и только тогда, когда будет на практике доказана способность этой машины симулировать человеческий разум. Так называемый физический тезис Чёрча — Тьюринга гласит: любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга. Если он верен, то тьюринг-полная машина способна вычислить всё, что в принципе может быть вычислено. Неудивительно, что создание первых тьюринг-полных компьютеров стало важнейшей вехой в истории развития вычислительной техники.

Так кому же принадлежит приоритет в создании такой машины? В своей работе, написанной в 1997 г., доктор Рауль Рохас показал, что машина Цузе Z3 может рассматриваться как тьюринг-полная. Для этого, однако, нужно совершить некоторый трюк, а именно склеить между собой два конца перфоленты, кодирующей программу. В машине Цузе не было операторов цикла или условного перехода, однако создание искусственного цикла, в который будет обёрнуто «тело» программы, позволяет тем не менее достичь желанной тьюринг-полноты. В принципе, подобный трюк мог бы быть возможен для Z1 и Z2, однако в случае Z1 машина не останавливалась при делении на ноль[376] (единственной причиной остановки было достижение конца программы), что делало при закольцованной ленте остановку машины невозможной, следовательно, Z1 даже теоретически не могла стать тьюринг-полной машиной, а Z2, как указывает профессор Рохас, испытывала большие проблемы ввиду ненадёжности работы многочисленных реле и так и не стала полностью функциональной машиной[377].

По крайней мере до 1946 г. Harvard Mark I умел выполнять операции лишь строго последовательно[378], а без возможности осуществления условного перехода машина не может быть тьюринг-полной.

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

2.7.5 Забытый изобретатель Джон Винсент Атанасов

Многие годы считалось, что первой ЭВМ была машина ENIAC (от Electronic Numerical Integrator and Computer — электронный численный интегратор и компьютер), созданная Джоном Мокли и Джоном Эккертом и запущенная в эксплуатацию 10 декабря 1945 г.

Однако в начале 1970-х гг. это утверждение было подвергнуто сомнению. Первой ласточкой стал иск, поданный в 1971 г. Sperry Rand Corporation к CDC и Honeywell, а окончательный крест на приоритете ENIAC был поставлен после того, как были рассекречены материалы о компьютере Colossus. В настоящее время считается, что первой электронной (хотя и не тьюринг-полной) машиной стал компьютер ABC Джона Атанасова и Клиффорда Берри, а второй — компьютер Colossus Mark I Томаса Флауэрса. В ходе судебного разбирательства по иску 1971 г., длившегося 135 рабочих дней, были заслушаны показания