Эндрю Ходжес - Вселенная Алана Тьюринга

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

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

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

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

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

Из этого следовало, что одна машина могла воспроизводить действия, выполняемые любой другой машиной. Такое устройство Алан и назвал универсальной машиной. Она должна была считывать дескриптивные числа, зашифровывать их в таблицы, а затем производить действия этих таблиц.Универсальная машина могла выполнять любые действия, которые производила любая другая таблица… Такая машина могла выполнять любые действия, и этого было достаточно, чтобы на время крепко задуматься. Более того, такая машина имела совершенно определенный вид, и Алан разработал соответствующую таблицу для универсальной машины.

И самое главное – Алану удалось доказать, что математика никогда не будет исчерпана никаким конечным множеством операций.

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

Слово «компьютер» здесь использовалось в своем значении, относящемся к 1936 году: лицо, выполняющее вычисления. В другом месте своей работы он обратился к идее, что «человеческая память неизбежно является ограниченным ресурсом», но эту мысль он выразил в ходе своего размышления о природе человеческого разума. Его предположение, на котором основывались его доводы о том, что состояния были исчислимы, было довольно смелым предположением. Особенно примечательно это было тем, что в квантовой механике физические состояния могли быть «в некоторой степени похожими». Далее он продолжил рассуждать о природе вычислений: «Представим, что производимые компьютером операции разложены на «простые операции», настолько элементарные, что невозможно представить дальнейшего их разложения на еще более простые операции. Каждая такая операция несет в себе некоторое изменение в физической системе, которую представляют собой компьютер и его лента. Нам известно состояние системы при условии, что мы знаем последовательность символов на рабочей ленте, которую считывает компьютер (возможно, в особом установленном порядке), а также состояние компьютера. Мы можем предположить, что в ходе простой операции не может быть изменено больше одного символа. Любые другие изменения могут быть разложены на более простые изменения подобного вида. Ситуация относительно ячеек с изменяемыми таким образом символами точно такая же, как и в случае со считанными ячейками. Таким образом, мы можем без ограничения общности предположить, что ячейки с измененными символами равнозначны считанным ячейкам.