ВУЗ:
Составители:
Рубрика:
Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
126
1
q
(начальная конфигурация)
↓
Λ
b
b
Λ
— 2-й шаг
2
q
↓
Λ
b
b
Λ
— 3-й шаг
2
q
↓
Λ
b
b
Λ
— 4-й шаг
2
q
↓
Λ
b
b
a
— 5-й шаг
0
q
(заключительная конфигу -
рация)
Работа МТ закончена.
Работу МТ можно описать следующим образом : она запоминает 1-ю
букву исходного слова (или при этом стирает его ); головка движется впра -
во до первой пустой клетки, в которую и записывается первая буква ис-
ходного слова .
Замечание. Часто программу МТ записывают в другой, более ком-
пактной форме в виде таблицы. Например, программа примера 1 может
выглядеть следующим образом:
Λ
a
b
1
q
2
qП
Λ
2
q
0
qНa
2
qПb
Пример 2. Построить машину Тьюринга , вычисляющую числовую
функцию
(
)
.Nx,xxS
∈
+
=
1
Решение. Пусть внешним алфавитом данной МТ является множест -
во
{
}
1,A
Λ
=
. Число
N
x
∈
на ленте машины записывать в виде набора из
x
единиц:
126
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
q1 (начальная конфигурация)
↓
Λ b b Λ — 2-й шаг
q2
↓
Λ b b Λ — 3-й шаг
q2
↓
Λ b b Λ — 4-й шаг
q2
↓
Λ b b a — 5-й шаг
q0 (заключительная конфигу-
рация)
Работа МТ закончена.
Работу МТ можно описать следующим образом: она запоминает 1-ю
букву исходного слова (или при этом стирает его); головка движется впра-
во до первой пустой клетки, в которую и записывается первая буква ис-
ходного слова.
Замечание. Часто программу МТ записывают в другой, более ком-
пактной форме в виде таблицы. Например, программа примера 1 может
выглядеть следующим образом:
Λ a b
q1 Λ П q2
q2 a Н q0 b П q2
Пример 2. Построить машину Тьюринга, вычисляющую числовую
функцию
S ( x ) =x +1, x ∈N .
Решение. Пусть внешним алфавитом данной МТ является множест-
во A ={Λ , 1}. Число x ∈ N на ленте машины записывать в виде набора из
x единиц:
