Разветвление машин Тьюринга

Пусть машины Т₁, Т₂, Т₃ заданы программами П₁, П₂, П₃ и внутренние алфавиты машин не пересекаются. Пусть q_1i и q_1j - какие-либо различные заключительные состояния машины Т₁. Заменим в программе П₁ состояние q_1i некоторым начальным состоянием q₂₁ машины Т₂, а состояние q_1j-некоторым начальным состоянием q₃₁ машины Т₃. Объединив новую программу с П₂ и П₃, получим программу П, задающую машину . Говорят, что Т есть разветвление машин Т₁ и Т₂, работающих под управлением Т₁.

Эквивалентность машин Тьюринга

Машины Тьюринга Т₁ и Т₂ называются эквивалентными в алфавите А, если для всякого входного слова Р в алфавите А выполняется соотношение: Т₁(Р)=Т₂(Р), которое означает, что Т₁(Р) и Т₂(Р) определены или не определены одновременно, т.е. применимы или не применимы к слову Р. Эквивалентность машин Т₁ и Т₂ обозначается .

Символ называется знаком условного равенства.

Понятие об алгоритмической неразрешимости

Словосочетание «решить задачу» допускает множество толкований. В математике иногда решают задачу с помощью интуиции (озарения). Рассмотрим решение с алгоритмической точки зрения: задача может быть решена, если существует алгоритм, приводящий к результату (решению задачи). Если для решения некоторой задачи построен решающий ее алгоритм, говорят, что задача алгоритмически разрешима. Во многих случаях алгоритм может быть найден. Но что означает ситуация, когда не удалось найти необходимый алгоритм? Ставить и разрешать математически точно вопросы об алгоритмической неразрешимости задач стало возможно только после появления формального определения понятия алгоритма. К настоящему времени выявлено достаточно много задач, для которых доказано, что не существует алгоритма, их решающего. Такие задачи называются алгоритмически неразрешимыми.