Эволюция разума - Курцвейл Рэймонд (читать книги онлайн без сокращений TXT) 📗
Блок-диаграмма машины Тьюринга, состоящей из считывающей и записывающей головки и внутренней программы, осуществляющей переходы между состояниями.
Входной сигнал задается информацией на ленте. Программа работает, а когда алгоритм выполнен, машина останавливается и выходные данные оказываются отпечатанными на ленте. Заметим, что, хотя теоретически лента имеет бесконечную длину, любая реальная программа, не попадающая в бесконечный цикл, использует лишь ограниченную часть ленты, так что, если мы возьмем ленту конечного размера, машина по-прежнему сможет решать некий набор задач.
Схема машины Тьюринга кажется простой — так сделал ее создатель. Он хотел, чтобы его машина была максимально простой (но не проще, если перефразировать Эйнштейна [121]). В результате работ Тьюринга и его бывшего учителя Алонзо Черча был сформулирован так называемый тезис Черча — Тьюринга: если некая функция не может быть вычислена машиной Тьюринга, она не может быть вычислена никакой другой машиной, подчиняющейся законам природы. Хотя машина Тьюринга выполняет лишь несколько команд и обрабатывает за один раз только один бит информации, она может решить любую задачу, которую способен решить любой другой компьютер. Иными словами, любая машина, эквивалентная машине Тьюринга, может вычислить любой алгоритм (решить любую задачу, которую мы в состоянии сформулировать).
В «строгой» формулировке тезиса Черча — Тьюринга постулируется эквивалентность между тем, что и как думает человек, и тем, что может рассчитать машина. Основная идея заключается в том, что человеческий мозг подчиняется законам природы и поэтому его способность обрабатывать информацию не может превышать аналогичную способность машины (в том числе машины Тьюринга).
Безусловно, статья Тьюринга 1936 г. заложила теоретические основы информатики, но важно отметить, что на работу Тьюринга большое влияние оказала лекция венгерско-американского математика Джона фон Неймана (1903–1957), которую он прочел в Кембридже в 1935 г. Тьюринг использовал в своей машине концепцию фон Неймана о хранимой программе [122]. Верно и то, что на фон Неймана оказала влияние статья Тьюринга, где элегантным образом изложены принципы информатики; в конце 1930-х и в начале 1940-х гг. фон Нейман рекомендовал прочесть эту статью всем своим коллегам [123].
В той же статье Тьюринг поведал о другом неожиданном открытии, касающемся неразрешимых задач. Неразрешимые задачи — это те, что хорошо описываются единственным решением (которое, как можно показать, существует), но (как тоже можно показать) не могут быть решены никакой машиной Тьюринга (то есть вообще никакой машиной). Представление о существовании таких задач в корне противоречит сформировавшейся к началу XX в. догме о том, что все проблемы, которые можно сформулировать, являются решаемыми. Тьюринг показал, что число неразрешимых задач не меньше числа разрешимых задач. В 1931 г. к такому же выводу пришел Курт Гедель, сформулировавший «теорему о неполноте». Такая странная ситуация: мы можем сформулировать задачу, можем доказать, что у нее существует единственное решение, но при этом знаем, что никогда не сможем это решение найти.
Тьюринг показал, что вычислительные машины действуют на основании очень простого механизма. Поскольку машина Тьюринга (и, следовательно, любой компьютер) может определять свою дальнейшую функцию на основе полученных ею ранее результатов, она способна принимать решения и создавать иерархические информационные структуры любой сложности.
В 1939 г. Тьюринг сконструировал электронный калькулятор Bombe, который помогал дешифровать сообщения, составленные немцами на кодирующей машине Enigma. К 1943 г. группа инженеров при участии Тьюринга закончила создание машины Colossus, которую иногда называют первым в истории компьютером. Это позволило союзникам расшифровывать сообщения, созданные более сложной версией Enigma. Машины Bombe и Colossus были сконструированы для решения единственной задачи и не могли перепрограммироваться. Но свою функцию они выполняли блестяще. Считается, что отчасти благодаря им союзники могли предвидеть тактику немцев на протяжении всей войны, а Королевские военно-воздушные силы Великобритании в Битве за Британию смогли одолеть втрое превосходящие их по численности силы Люфтваффе.
Именно на этой основе Джон фон Нейман создал компьютер современной архитектуры, отражающей третью из четырех важнейших идей теории информации. На протяжении прошедших с тех пор почти семидесяти лет основное ядро этой машины, названной «машиной фон Неймана», практически не изменилось — как в микроконтроллере в вашей стиральной машине, так и в самом крупном суперкомпьютере. В статье, опубликованной 30 июня 1945 г. и озаглавленной «Первый проект отчета о EDVAC», фон Нейман изложил основные идеи, которые с тех пор направляли развитие информатики [124]. В машине фон Неймана присутствует центральный процессор, где выполняются арифметические и логические операции, модуль памяти, в котором хранятся программы и данные, массовая память, программный счетчик и входные/выходные каналы. Хотя статья предназначалась для внутреннего пользования в рамках выполнения проекта, для создателей компьютеров она стала Библией. Вот так иногда обычный рутинный отчет может изменить мир.
Машина Тьюринга не была предназначена для практических целей. Теоремы Тьюринга не имели отношения к эффективности решения задач, а скорее описывали спектр задач, которые теоретически могут быть решены с помощью компьютера. Напротив, цель фон Неймана заключалась в создании концепции реального компьютера. Его модель заменила однобитную систему Тьюринга многобитной (обычно кратную восьми битам) системой. Машина Тьюринга имеет последовательную ленту памяти, так что программы затрачивают очень большое время на перемещение ленты вперед и назад для записи и извлечения промежуточных результатов. Напротив, в системе фон Неймана доступ к памяти осуществляется произвольным образом, что позволяет немедленно извлекать любые нужные данные.
Одной из ключевых идей фон Неймана является концепция хранимой программы, которую он развил за десять лет до создания компьютера. Суть концепции заключается в том, что программа хранится в том же модуле памяти с произвольным доступом, что и данные (а часто даже в том же блоке памяти). Это позволяет перепрограммировать компьютер для решения разных задач и создавать самомодифицирующийся код (в случае записывающих накопителей), что обеспечивает возможность рекурсии. До того времени практически все компьютеры, включая Colossus, создавались для решения конкретных задач. Концепция хранимой программы позволила компьютеру стать поистине универсальной машиной, соответствующей представлению Тьюринга об универсальности машинных вычислений.
Еще одно важное свойство машины фон Неймана заключается в том, что в каждой инструкции содержится операционный код, определяющий арифметическую или логическую операцию и адрес операнда в памяти компьютера.
Концепция фон Неймана об архитектуре компьютера отразилась в проекте EDVAC, над которым он работал совместно с Преспером Дж. Эккертом и Джоном Моучли. Компьютер EDVAC начал функционировать только в 1951 г., когда уже существовали другие компьютеры с хранимой программой, такие как Манчестерская малая экспериментальная машина, ENIAC, EDSAC и BINAC, причем все они были созданы под влиянием статьи фон Неймана и при участии Эккерта и Моучли. Фон Нейман также был причастен к появлению некоторых из этих машин, включая последнюю версию ENIAC, где использовался принцип хранимой программы.
У компьютера с архитектурой фон Неймана имелось несколько предшественников, но ни один из них — за одним неожиданным исключением — нельзя назвать истинной машиной фон Неймана. В 1944 г. Говард Эйкен выпустил Mark I, который можно было в какой-то степени перепрограммировать, но он не использовал хранимой программы. Машина считывала инструкции с перфокарты и немедленно их выполняла. В машине также не было предусмотрено условных переходов.
