Игра в имитацию - Эндрю Ходжес (2015)

Следующей необходимой функцией для машины была возможность считывать информацию или, по словам самого Алана, «сканировать» ячейку ленты, на которой остановилось считывающее устройство. Также она должна была обладать функцией не только записи символов, но и уметь их стирать. При этом она могла переместиться только на одну ячейку за раз. В таком случае какие действия оставались для машиниста пишущей машинки? Алан действительно отметил в своей работе возможность того, что он сам называл «машинами выбора», в которых внешний оператор должен принимать решения в определенных моментах работы устройства. Вместе с тем целью его работы было создание именно автоматических машин, для работы которых не потребуется вмешательство человека. С самого начала он хотел всесторонне изучить то, что Харди называл «сверхъестественной машиной», — механический процесс, который смог бы решить третью проблему Гильберта путем считывания предоставленного математического суждения, и в конечном результате записывая решение: имеет ли оно доказательство или нет. Существенной идеей для подобного устройства оставалась возможность производить решение без вмешательства человеческого суждения, воображения или интеллекта.

Любая «автоматическая машина» должна была работать сама по себе, производя считывание и запись информации, перемещаясь вперед и назад, в соответствии с тем, как она была задумана. На каждом этапе ее работы действия должны быть строго определены текущей конфигурацией и считанным символом. Для большей точности конструкция машины должна была уметь определять свое действие в случае каждой комбинации конфигурации и считанного символа:

записать новый (заданный) символ в пустую ячейку, или оставить уже записанный символ в неизменном виде, или стереть символ и оставить ячейку пустой;

остаться в прежней конфигурации или сменить ее на другую (заданную) конфигурацию;

переместиться на ячейку влево, или вправо, или остаться в текущей позиции.

Если всю эту информацию, определяющую действия машины, записать, получится «таблица переходов», имеющая конечное количество действий. Такая таблица может полностью описать работу машины, и независимо от того, была ли машина сконструирована или нет, такая таблица могла представить всю необходимую информацию о ее работе. С абстрактной точки зрения, именно таблица и являлась самой машиной.

С изменениями, вносимыми в таблицу, изменялось бы и поведение самой машины. Бесконечное множество таблиц соответствовало бы бесконечному множеству возможных машин. Алану удалось воплотить неясную идею «определенного метода» или «механического процесса» в чем-то более точном — «таблице переходов». Теперь ему оставалось ответить на один очень конкретный вопрос: может ли одна из таких машин, одна из таких таблиц произвести решение вопроса, который поставил Гильберт?

Рассмотрим пример подобной машины. Приведенная ниже «таблица переходов» полностью описывает машину Тьюринга с функцией счетной машины. Начиная с позиции сканирующего устройства слева от двух групп единиц, разделенных одной пустой ячейкой, машина просуммирует две группы и остановится. Таким образом, это действие изменит заданное состояние ленты.

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

Полная таблица, описывающая это действие, будет выглядеть следующим образом:

Просканированный символ