Охота на электроовец. Большая книга искусственного интеллекта
Шрифт:
Первым элементом МТ является лента бесконечной длины, разделённая на ячейки. Каждая ячейка может хранить произвольный символ (на практике достаточно двух: 0 и 1). Кроме того, есть считывающая головка, способная обследовать одну ячейку ленты. После обследования лента может быть смещена на одну ячейку влево или вправо по отношению к головке. МТ руководствуется набором правил перехода. В каждый момент она находится в определённом состоянии, которому соответствует некоторое подмножество правил перехода. Каждое правило гласит: если машина находится в состоянии X с символом Y в ячейке ленты, пребывающей под считывающей головкой, то символ Y следует заменить новым символом Y?, переместить ленту на одну ячейку влево или вправо и изменить состояние на X?. Произвольное множество правил может быть само записано в виде последовательности символов на ленте МТ. Тьюринг использовал это свойство для определения понятия универсальной машины Тьюринга (УМТ), которая представляет собой МТ, способную имитировать произвольную МТ по её описанию
375
Кокшотт У. П., Микаэльсон Г., Коттрел А. (2017). Бёттке, синтаксис и тест Тьюринга / Пер. с англ. Горлова А.В., Маркова С.С // https://22century.ru/popular-science-publications/boettke-syntax-and-the-turing-test
В заголовке работы Тьюринга мы встречаем странное слово Entscheidungsproblem, которое у людей, не являющихся носителями немецкого языка, вероятно, ассоциируется с заклинаниями для вызова потусторонних сил. Почему Тьюринг, родившийся в лондонском Сити и практически всю жизнь проживший в Великобритании, решил в названии одной из самых значимых своих работ перейти на немецкий язык?
Entscheidungsproblem в переводе с немецкого дословно означает «проблема (или задача) решения», по-русски мы обычно говорим «проблема разрешения». Впервые проблема была сформулирована в 1928 г. Давидом Гильбертом, едва ли не самым известным математиком XX столетия. Вопрос задачи звучит следующим образом: существует ли алгоритм, который, получив на вход утверждение, отвечает «да» или «нет» в зависимости от того, является ли данное утверждение «универсально справедливым»? В соответствии с теоремой Гёделя о полноте исчисления предикатов утверждение является «универсально справедливым» тогда и только тогда, когда оно может быть выведено из аксиом. Поэтому проблему разрешения можно рассматривать как вопрос о существовании алгоритма, позволяющего определить, можно ли, используя правила логики, вывести заданное утверждение из аксиом. В 1936 г. Чёрчу удалось доказать принципиальную невозможность создания такого алгоритма. В том же году, но несколько позже этот же результат независимо получил и Тьюринг, и именно этому посвящена его статья «О вычислимых числах…». Сегодня мы называем полученный результат теоремой Чёрча — Тьюринга.
Тьюринг доказал, что его «универсальная вычислительная машина» способна выполнять любые мыслимые математические вычисления, если они могут быть представлены в виде алгоритма. Для того чтобы показать неразрешимость проблемы разрешения, Тьюринг доказал, что проблема остановки (halting problem) для машин Тьюринга неразрешима: невозможно гарантированно за конечное количество шагов алгоритмически решить, остановится ли когда-нибудь произвольно взятая машина Тьюринга.
Хотя доказательство Тьюринга было опубликовано после аналогичного доказательства Чёрча, выполненного на основе лямбда-исчисления, подход Тьюринга выглядел более наглядным. Идея УМТ, то есть такой гипотетической машины, которая способна выполнять задачи любой другой вычислительной машины, оказалась весьма продуктивной. Согласно тезису Чёрча — Тьюринга, машины Тьюринга и лямбда-исчисление способны вычислять всё, что можно в принципе вычислить.
В 1939 г. Джону Россеру удалось доказать, что все три подхода — общерекурсивные функции Гёделя, универсальная машина Тьюринга и лямбда-исчисление Чёрча — являются взаимно эквивалентными и, следовательно, все три могут быть равнозначно использованы для определения эффективной вычислимости.
Интересными побочными продуктами изысканий Тьюринга стали понятия тьюринг-эквивалентности и тьюринг-полноты. Две машины P и Q являются тьюринг-эквивалентными, если машина P может симулировать работу машины Q и, наоборот, машина Q может симулировать работу машины P. Тьюринг-полной машиной называется машина, способная симулировать работу машины Тьюринга. Разумеется, не существует физических устройств, обладающих бесконечным объёмом памяти — аналогом бесконечной ленты МТ. Но это ограничение при использовании понятия тьюринг-полноты обычно игнорируется, то есть тьюринг-полными называют машины, которые при наличии у них бесконечной памяти могли бы выполнять любые вычисления, доступные МТ.
В свете теоретических работ Тьюринга над проблемой разрешения становится более понятной идея, лежащая в основе теста Тьюринга. Признать наличие разума у машины можно будет тогда и только тогда, когда будет на практике доказана способность этой машины симулировать человеческий разум. Так называемый физический тезис Чёрча — Тьюринга гласит: любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга. Если он верен, то тьюринг-полная машина способна вычислить всё, что в принципе может быть вычислено. Неудивительно, что создание первых тьюринг-полных компьютеров стало важнейшей вехой в истории развития вычислительной техники.
Так кому же принадлежит приоритет в создании такой машины? В своей работе, написанной в 1997 г., доктор Рауль Рохас показал, что машина Цузе Z3 может рассматриваться как тьюринг-полная. Для этого, однако, нужно совершить некоторый трюк, а именно склеить между собой два конца перфоленты, кодирующей программу. В машине Цузе не было операторов цикла или условного перехода, однако создание искусственного цикла, в который будет обёрнуто «тело» программы, позволяет тем не менее достичь желанной тьюринг-полноты. В принципе, подобный трюк мог бы быть возможен для Z1 и Z2, однако в случае Z1 машина не останавливалась при делении на ноль [376] (единственной причиной остановки было достижение конца программы), что делало при
376
Rojas R. (1996). Konrad Zuse's Legacy: The Architecture of the Z1 and Z3 / IEEE Annals of the History of Computing, Vol. 19, No. 2, 1997 // http://page.mi.fu-berlin.de/rojas/1996/Konrad_Zuses_Legacy.pdf
377
Профессор Рауль Рохас, персональные коммуникации.
По крайней мере до 1946 г. Harvard Mark I умел выполнять операции лишь строго последовательно [378] , а без возможности осуществления условного перехода машина не может быть тьюринг-полной.
Mark I и первые машины Цузе стали первыми электромеханическими машинами, преодолевшими барьер тьюринг-полноты. Однако, несмотря на эти выдающиеся результаты, ресурсы технологии, лежащей в их основе, уже были исчерпаны. На смену этим могущественным гибридам пришли электронные машины.
378
Bloch R. (1984-02-22). Oral history interview with Richard M. Bloch // https://conservancy.umn.edu/bitstream/handle/11299/107123/oh066rb.pdf
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] .
379
Dalakov G. The ENIAC of John Mauchly and John Eckert / History of Computers: hardware, software, internet… // https://history-computer.com/ModernComputer/Electronic/ENIAC.html
Сегодня, почти полвека спустя, у этого судебного решения находится немало критиков. Попробуем пролить немного света на эту детективную историю, разыгравшуюся в конце 1930-х — начале 1940-х гг.
Джон Винсент Атанасов был первым из девяти детей, родившихся в семье американского инженера-электрика болгарского происхождения Ивана Атанасова и Ивы Лусены Парди, учительницы математики. Вот что писал Джон об отце: «Мой отец родился 6 января 1876 года, в то время, когда наш народ готовил восстание против турок. Незадолго до начала восстания турецкие власти вынудили жителей деревни Бояджик покинуть свои жилища, а затем подожгли дома. Мой дедушка бежал с сыном на руках, за ним следовала моя бабушка, и в этот момент группа турецких солдат дала залп ему в грудь. Пуля, убившая его, оставила шрам на лбу моего отца на всю оставшуюся жизнь. Моя бабушка была замужем ещё дважды. Моему отцу было 13 лет, когда он приехал в Соединённые Штаты, а в 15 лет он осиротел. После столь невероятного начала своей жизни он окончил Колгейтский университет и женился на моей матери, американке, дедушка которой участвовал в Гражданской войне между Севером и Югом» [380] , [381] .
380
Sendov B. (2001). John Atanasoff. The Man Who Invented the Computer // https://web.archive.org/web/20180306172639/http://www.johnatanasoff.com:80/pride_in_Bulgaria.php
381
Атанасов Дж. (1985). До моята бащина земя // https://webstage.bg/istoriya/4187-do-moyata-bashtina-zemya-dzhon-atanasov.html
В 1903 г. семья с новорождённым Джоном переехала во Флориду, где его отец получил должность инженера-электрика в Остине, а затем в промышленном городке Брюстере, основанном в 1910 г. компанией American Cyanamid. В наши дни Брюстер представляет собой пустынный город-призрак, официальное население которого, по данным переписи 2010 года, составляет три человека [382] . Джон хорошо учился в школе, увлекался спортом, особенно бейсболом. Но когда отец приобрёл новую логарифмическую линейку — она произвела неизгладимое впечатление на мальчика и изменила его интересы.
382
https://www.census.gov/prod/cen2010/cph-1-11.pdf