Универсальная машина Тьюринга. Теоретическая модель современного компьютера
До сих пор мы придерживались той точки зрения, что различные алгоритмы осуществляются в различных машинах Тьюринга, отличающихся своими функциональными схемами. Однако можно построить универсальную тьюрингову машину, способную в известном смысле выполнять любой алгоритм, а значит, способную выполнить работу любой тьюринговой машины. Алгоритм подражания Для того чтобы лучше уяснить себе, как это делается, представим себе следующий эксперимент. Пусть на ленту машины подана начальная информация U, и предположим, что некоторому человеку предложено указать, как будет перерабатывать машина эту информацию и во что она переработает ее окончательно. Если этот человек знаком с принципами работы тьюринговых машин, то достаточно ему сообщить, кроме этой начальной информации U, еще функциональную схему машины. Тогда человек, подражая работе машины и выписывая нужные конфигурации, сможет получить тот же результат, что и машина. Но это как раз и означает, что такой человек способен выполнять работу любой тьюринговой машины, если ему только задана ее функциональная схема. Сам же процесс подражания машине в соответствии с ее функциональной схемой может быть регламентирован в виде точного предписания, которое можно сообщить человеку, не имеющему ни малейшего понятия о машинах Тьюринга. Если человека, располагающего таким предписанием, которое естественно называть алгоритмом подражания, снабдить функциональной схемой какой-либо машины Тьюринга и, кроме того, некоторой начальной конфигурацией, изображенной на ленте, то он окажется способным в точности подражать работе соответствующей машины и в результате выдаст тот же результат. Подобный алгоритм подражания можно было бы задать хотя бы в виде следующей системы указаний: