ВУЗ:
Составители:
Операция композиции, выполняемая над алгоритмами, позволяет получать новые, более
сложные алгоритмы из ранее известных простых алгоритмов.
2. Итерация машины Тьюринга. Эта операция применима только к одной машине.
Пусть q
z
- заключительное состояние машины Т, а q
n
- какое-либо состояние машины Т,
не являющееся заключительным. Заменим всюду в программе Р машины Т состояние q
z
на
q
n
. Полученная программа определяет новую машину Т′(q
z
, q
n
), которая называется
итерацией машины Т по паре состояний (q
z
, q
n
). Если машина Тьюринга имеет одно
заключительное состояние, то после выполнения итерации получается машина, не имеющая
заключительного состояния.
3. Разветвление машин Тьюринга. Пусть машины Тьюринга Т
1
,
Т
2
и
Т
3
задаются
программами Р
1
,
Р
2
и
Р
3
соответственно. Считаем, что внутренние алфавиты этих машин
попарно не пересекаются. Пусть q
z11
и q
z12
- какие-либо различные заключительные
состояния машины Т
1
. Заменим всюду в программе Р
1
состояние q
z11
начальным состоянием
q
02
машины
Т
2
, а состояние q
z12
начальным состоянием q
03
машины
Т
3
. Затем новую
программу объединим с программами Р
2
и
Р
3
. Получим программу Р, задающую машину
Тьюринга и обозначаемую:
Т = Т(Т
1
, (q
z11
, q
02
), Т
2
, (q
z12
, q
03
), Т
3
).
Машина Т называется разветвлением машин Т
2
и
Т
3
, управляемым машиной Т
1
.
3.7. Примеры построения машин Тьюринга
Пример 1. Построить машину Тьюринга, которая правильно вычисляет функцию f(x) =
x+1 по правилам двоичного сложения.
Решение. Исходя из формулировки задачи, требующей вычислить функцию по правилам
сложения в двоичной системе сложения, выберем входной алфавит:
А ={0, 1, ε}.
Представим машины Тьюринга таблицей соответствия и графом.
Таблица соответствия:
0 1
ε
q
0
q
0
0R q
0
1R
Q
1
ε L
q
1
q
2
1L q
1
0L q
2
1L
q
2
q
2
0L Q
2
1L
q
z
ε R
Представление машины Тьюринга в виде графа:
1
→
1R
0
→
0R
1
→
0L
ε
→
ε
L
q
0
q
1
q
2
q
z
0
→
1L
ε
→
1L
ε
→
ε
R
0 → 0L
1
→
1L
Запишем программу построенной машины Тьюринга для случая, когда входная цепочка
на ленте равна двоичному числу 111. Слева от каждой команды приведем представление
входной цепочки на ленте до выполнения данной команды. Символ, который находится под
головкой, будем помечать подчеркиванием.
1) q
0
1 → q
0
1R ε111ε 6) q
1
1 → q
1
0L ε110ε
Операция композиции, выполняемая над алгоритмами, позволяет получать новые, более сложные алгоритмы из ранее известных простых алгоритмов. 2. Итерация машины Тьюринга. Эта операция применима только к одной машине. Пусть qz - заключительное состояние машины Т, а qn - какое-либо состояние машины Т, не являющееся заключительным. Заменим всюду в программе Р машины Т состояние qz на qn . Полученная программа определяет новую машину Т′(qz, qn), которая называется итерацией машины Т по паре состояний (qz, qn). Если машина Тьюринга имеет одно заключительное состояние, то после выполнения итерации получается машина, не имеющая заключительного состояния. 3. Разветвление машин Тьюринга. Пусть машины Тьюринга Т1, Т2 и Т3 задаются программами Р1, Р2 и Р3 соответственно. Считаем, что внутренние алфавиты этих машин попарно не пересекаются. Пусть qz11 и qz12 - какие-либо различные заключительные состояния машины Т1. Заменим всюду в программе Р1 состояние qz11 начальным состоянием q02 машины Т2, а состояние qz12 начальным состоянием q03 машины Т3. Затем новую программу объединим с программами Р2 и Р3. Получим программу Р, задающую машину Тьюринга и обозначаемую: Т = Т(Т1, (qz11, q02), Т2, (qz12, q03), Т3). Машина Т называется разветвлением машин Т2 и Т3, управляемым машиной Т1. 3.7. Примеры построения машин Тьюринга Пример 1. Построить машину Тьюринга, которая правильно вычисляет функцию f(x) = x+1 по правилам двоичного сложения. Решение. Исходя из формулировки задачи, требующей вычислить функцию по правилам сложения в двоичной системе сложения, выберем входной алфавит: А ={0, 1, ε}. Представим машины Тьюринга таблицей соответствия и графом. Таблица соответствия: 0 1 ε q0 q0 0R q0 1R Q1 ε L q1 q2 1L q1 0L q2 1L q2 q2 0L Q2 1L qz ε R Представление машины Тьюринга в виде графа: 1→ 1R 1 → 0L 0 → 0L ε → ε L 0 → 1L ε → ε R q0 q1 q2 qz ε → 1L 0 → 0R 1 → 1L Запишем программу построенной машины Тьюринга для случая, когда входная цепочка на ленте равна двоичному числу 111. Слева от каждой команды приведем представление входной цепочки на ленте до выполнения данной команды. Символ, который находится под головкой, будем помечать подчеркиванием. 1) q01 → q01R ε111ε 6) q11 → q10L ε110ε
Страницы
- « первая
- ‹ предыдущая
- …
- 15
- 16
- 17
- 18
- 19
- …
- следующая ›
- последняя »