15.5. Универсальная машина Тьюринга
В заключение опишем, что такое универсальная
машина Тьюринга. В обычной машине
Тьюринга программа «зашита» в устройство
управления, а входная информации (условия
задачи) записывается на бесконечной
ленте. В универсальной машине в устройстве
управления записана программа, реализующая
алгоритм подражания, т. е. программную
реализацию правил работы любой машины
(см. п.15.2), вернее, правила обращения с
ее программой. Тогда входной информацией
для универсальной машины является пара
- слово ит,
стандартно кодирующее машину-алгоритм,
решающий данный класс задач Z;
и слово vz,
кодирующее условие задачи
.
Универсальная машина, используя ит,
перерабатывает vz
в T(vz).
Ясно, что для построения универсальной
машины потребуется использование
техники машин с полулентами и универсального
алфавита. Эта машина будет работать
очень «вяло», теряя очень много времени
на переходы от обрабатываемого слова
к программе и обратно, однако ясно, что
справедлива следующая теорема.
Теорема 15.11 Универсальная машина
Тьюринга существует.
Программирование для машин Тьюринга
(после приобретения некоторых навыков)
достаточно полезное занятие, как требует
лишь алгоритмических навыков, а не
удержания в голове стандартных
конструкций, характерных для
программирования на алгоритмических
языках высокого уровня. Здесь нет
фактически программистских проблем, а
есть только алгоритмические проблемы.
Решение задач по программированию для
машин Тьюринга позволяет выработать и
развить приемы алгоритмизации.