Восходит к Давиду Гильберту На рубеже 20 века сформулировал мировую проблему

Операции над МТ

• Пусть a01 = a02 = a0 и a11 = a12 = a1. Внешний алфавит композиции Т1Т2 является объединением внешних алфавитов машин Т1 и Т2:

• Операция композиции, выполняемая над алгоритмами, позволяет получать новые, более сложные алгоритмы из ранее известных простых алгоритмов.
• 2. Итерация машины Тьюринга. Эта операция применима только к одной машине.
• Пусть qz - заключительное состояние машины Т, а qn - какое-либо состояние машины Т, не являющееся заключительным. Заменим всюду в программе Р машины Т состояние qz на qn . Полученная программа определяет новую машину Т′(qz, qn), которая называется итерацией машины Т по паре состояний (qz, qn). Если машина Тьюринга имеет одно заключительное состояние, то после выполнения итерации получается машина, не имеющая
• заключительного состояния.