Искусственный интеллект. Что стоит знать о наступающей эпохе разумных машин - стр. 6
Для начала он придумал машину, которая могла считывать символы с перфоленты (см. рис. 1.1). Вы подаете в машину перфоленту, а она изучает символы и на основании заложенных правил принимает решение о своем следующем действии. К примеру, такое устройство могло сложить два числа, записанных на перфоленте, и вывести на ленту результат операции. В дальнейшем это устройство получило название «машина Тьюринга». Но поскольку каждая машина Тьюринга имела собственный свод правил (то есть фиксированную программу), она не годилась для тестирования гипотезы Гильберта.
В 1930-х годах Алан Тьюринг придумал новый тип машин, который смог бы последовательно считывать символы с перфоленты. После принятия решения на основании своих внутренних правил устройство выполняло одно из пяти действий: передвигало ленты вправо или влево, удаляло символ, дописывало новый символ или останавливалось. Такое устройство получило название «машина Тьюринга».
Тьюринг также предположил, что даже саму перфоленту можно использовать для программирования действий машины – то есть базовой версии программного обеспечения. Такая схема получила название «универсальная машина Тьюринга» и стала основой всех современных компьютеров.
Рис. 1.1. Тьюринг так никогда и не построил свою теоретическую вычислительную машину, но она послужила основой для всех современных компьютеров
Тьюринг понял, что можно создать машину, которая сначала будет считывать процедуру с ленты, а затем использовать эту информацию для определения своих внутренних правил. Таким образом, машина станет программируемой и способной к выполнению тех же действий, что и отдельно взятая машина Тьюринга с фиксированным набором правил. Такое гибкое устройство, которое мы называем «универсальной машиной Тьюринга», и является компьютером.
Почему так? Процедура, записанная на ленте, является аналогом компьютерной программы. Универсальная машина Тьюринга загружает программу с ленты на свое устройство – именно это мы и делаем с программами на жестком диске. Сейчас ваш компьютер используется в качестве текстового процессора, а через минуту он превращается в музыкальный плеер.
После изобретения Тьюрингом теоретического компьютера он смог ответить на вопросы: что такое «вычисляемость»? Что может и не может делать компьютер?
Для опровержения гипотезы Гильберта Тьюрингу нужно было найти лишь одно логическое выражение, которое компьютер не смог бы однозначно трактовать как истинное или ложное. Поэтому Тьюринг сформулировал конкретный вопрос: сможет ли компьютер проанализировать программу и решить, способна ли она «остановиться» или же будет выполняться вечно, до своего отключения? Другими словами, истинен или ложен факт, что программа остановится? Ответ оказался следующим: нет, не сможет. Таким образом, он пришел к выводу, что процедуры Гильберта не существует, и «проблема разрешения» была решена. Фактически вывод Тьюринга заключался в том, что существует бесконечное множество задач, которые компьютер не сможет выполнить.