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

1. Композиция машин Тьюринга. Пусть машины Т1 и Т2 имеют программы Р1 и Р2. Предположим, что внутренние алфавиты этих машин не пересекаются; пусть qz1 - заключительное состояние машины Т1, а q02 - начальное состояние машины Т2. Заменим всюду в программе Р1 заключительное состояние qz1 на начальное состояние q02 машины Т2 и полученную программу объединим с программой Р2. Новая программа Р определяет машину Т, называемую композицией машин Т1 и Т2 по паре состояний (qz1, q02).

Композиция машин может быть обозначена Т1 ⋅Т2 или Т1Т2. Более подробно композиция машин записывается следующим образом:

Т = Т(Т₁, Т₂, (q_z1, q₀₂)), где

T₁ = (Q₁, A₁, δ₁, p₀₁, p_z1, a₀₁, a₁₁),

Т₂= (Q₂, A₂, δ₂, p₀₂, p_z2, a₀₂, a₁₂).

Пусть a₀₁ = a₀₂ = a₀ и a₁₁ = a₁₂ = a₁. Внешний алфавит композиции Т₁.Т₂ является объединением внешних алфавитов машин Т₁ и Т₂:

p₀₂

Т= (Q₁ È Q₂ \ {p_z1}, A₁ ÈA₂, | (δ₁, È δ₂), p₀₁, p_z2, a₀, a₁).

p_z1

Операция композиции, выполняемая над алгоритмами, позволяет получать новые, более сложные алгоритмы из ранее известных простых алгоритмов.

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

3. Разветвление машин Тьюринга. Пусть машины Тьюринга Т₁, Т₂ и Т₃ задаются программами Р₁, Р₂ и Р₃ соответственно. Считаем, что внутренние алфавиты этих машин попарно не пересекаются. Пусть q_z11 и q_z12 - какие-либо различные заключительные состояния машины Т₁. Заменим всюду в программе Р₁ состояние q_z11 начальным состоянием q02 машины Т₂, а состояние q_z12 начальным состоянием q₀₃ машины Т₃. Затем новую программу объединим с программами Р₂ и Р₃. Получим программу Р, задающую машину

Тьюринга и обозначаемую:

Т = Т(Т₁, (q_z11, q₀₂), Т₂, (q_z12, q₀₃), Т₃).

Машина Т называется разветвлением машин Т₂ и Т₃, управляемым машиной Т₁.

Дата добавления: 2015-07-26; просмотров: 278; Нарушение авторских прав

Мы поможем в написании ваших работ!