Универсальная машина Тьюринга

Занумеруем все машины Тьюринга, вычисляющие одноместные функции. Универсальная машина Тьюринга МУ работает так над парой n, x так:

– если n – номер МТ, вычисляющей f, то на выходе имеем f (x),

– если n – не номер МТ, то машина останавливается.

Описание МУ. На ленте записаны числа n и x.

(1) Находим число s (n) команда в машине с номером n.

(2) Находим номер каждой команды n ₁, n ₂, …, n_s.

(3) Раскодируем номера команд и запишем на ленте эти команды. На ленте возникнет ситуация

К1

0

К2

…

X

5 яч. 5 яч. 5 яч.

(4) Если в состоянии управляющее устройство находится над символом , то после этого программа ищет команду К, у которой левая часть , . После этого управляющее устройство возвращается на то место, откуда начался поиск команды. Здесь состояние относится к , состояние относится к МУ и используется при декодировании номера – состояние МУ при вычислении .