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

Построение МТ

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

Операции над машинами Тьюринга

• 1. Композиция машин Тьюринга. Пусть машины Т1 и Т2 имеют программы Р1 и Р2.
• Предположим, что внутренние алфавиты этих машин не пересекаются; пусть qz1 - заключительное состояние машины Т1, а q02 - начальное состояние машины Т2. Заменим всюду в программе Р1 заключительное состояние qz1 на начальное состояние q02 машины Т2 и полученную программу объединим с программой Р2. Новая программа Р определяет машину Т, называемую композицией машин Т1 и Т2 по паре состояний (qz1, q02).
• Композиция машин может быть обозначена Т1 ⋅Т2 или Т1Т2. Более подробно композиция машин записывается следующим образом:
• Т = Т(Т1, Т2, (qz1, q02)), где
• T1 = (Q1, A1, δ1, p01, pz1, a01, a11),
• Т2= (Q2, A2, δ2, p02, pz2, a02, a12).