Охота на электроовец. Большая книга искусственного интеллекта - Марков Сергей Николаевич
Тьюринг доказал, что его «универсальная вычислительная машина» способна выполнять любые мыслимые математические вычисления, если они могут быть представлены в виде алгоритма. Для того чтобы показать неразрешимость проблемы разрешения, Тьюринг доказал, что проблема остановки (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 рабочих дней, были заслушаны показания 77 свидетелей, занявшие в общей сложности около 20 000 страниц стенограмм. Вердикт судьи окружного суда Миннесоты Эрла Р. Ларсона, вынесенный 19 октября 1973 г., гласил: основные идеи, лежавшие в основе ENIAC, были получены от Атанасова, изобретение, заявленное в ENIAC, также было совершено Атанасовым. Суд установил тот факт, что Мокли присвоил идеи Атанасова и в течение более тридцати лет подсовывал их миру в качестве собственных. Патент Мокли и Эккерта был отозван [379].
Сегодня, почти полвека спустя, у этого судебного решения находится немало критиков. Попробуем пролить немного света на эту детективную историю, разыгравшуюся в конце 1930‑х — начале 1940-х гг.
Джон Винсент Атанасов был первым из девяти детей, родившихся в семье американского инженера-электрика болгарского происхождения Ивана Атанасова и Ивы Лусены Парди, учительницы математики. Вот что писал Джон об отце: «Мой отец родился 6 января 1876 года, в то время, когда наш народ готовил восстание против турок. Незадолго до начала восстания турецкие власти вынудили жителей деревни Бояджик покинуть свои жилища, а затем подожгли дома. Мой дедушка бежал с сыном на руках, за ним следовала моя бабушка, и в этот момент группа турецких солдат дала залп ему в грудь. Пуля, убившая его, оставила шрам на лбу моего отца на всю оставшуюся жизнь. Моя бабушка была замужем ещё дважды. Моему отцу было 13 лет, когда он приехал в Соединённые Штаты, а в 15 лет он осиротел. После столь невероятного начала своей жизни он окончил Колгейтский университет и женился на моей матери, американке, дедушка которой участвовал в Гражданской войне между Севером и Югом» [380], [381].
В 1903 г. семья с новорождённым Джоном переехала во Флориду, где его отец получил должность инженера-электрика в Остине, а затем в промышленном городке Брюстере, основанном в 1910 г. компанией American Cyanamid. В наши дни Брюстер представляет собой пустынный город-призрак, официальное население которого, по данным переписи 2010 года, составляет три человека [382]. Джон хорошо учился в школе, увлекался спортом, особенно бейсболом. Но когда отец приобрёл новую логарифмическую линейку — она произвела неизгладимое впечатление на мальчика и изменила его интересы.
Джон заинтересовался математическими принципами работы линейки, и это привело его к изучению тригонометрических функций. С помощью своей матери он прочитал «Алгебру в колледже» (A College Algebra) [383] Джеймса Тейлора. Эта книга содержала начала дифференциального исчисления, главу о бесконечных рядах и о вычислении логарифмов. В течение нескольких месяцев девятилетний вундеркинд смог освоить азы математической науки в достаточной степени для того, чтобы далее обходиться без посторонней помощи. За это время, опираясь на помощь мамы, он узнал о различных системах счисления, в том числе о двоичной.
