Машина Тьюринга
Машина Тьюринга
– это математическая модель ЭВМ. Она
состоит из: 1) бесконечной в обе стороны
ленты, разбитой на ячейки. В каждой
ячейке записан один из символов алфавита:
a
,
a
,
… , a
.
В алфавите всегда существует пустой
символ (или пробел), например, a
.
Для своей задачи каждый берёт свой
алфавит.
2) внутренней памяти
q
,
q
,
… , q
- внутренних состояний машины. Какое-то
из внутренних состояний конечное
(например, q
),
какое-то – начальное (например, q
).
Для каждой задачи берётся свой набор
внутренних состояний, но начальное и
конечное состояния существуют всегда.
Эти состояния могут и совпасть.
3) управляющей головки, двигающейся в обе стороны вдоль ленты в дискретные моменты времени. Головка читает символы алфавита, анализирует их, записывает новые символы и двигается по ленте по программе. В зависимости от внутреннего состояния в данный момент и от символа на воспринимаемой ячейке, в следующий момент машина переходит в новое состояние, записывает на ячейку новый символ. Попав в конечное состояние, машина прекращает работу.
Конфигурация
на ленте состоит из: 1) последовательности
a
,
a
,
… , a
символов алфавита на ленте. Считается,
что в обе стороны ленты бесконечное
количество пустых символов и их писать
не обязательно. 2) внутреннего состояния
q
.
3) номера воспринимаемой ячейки.
Если, находясь
в данный момент во внутреннем состоянии
q
и читая с ячейки a
,
в следующий момент машина переходит в
состояние q
,
пишет на ленте a
и двигается по ленте, то это будет
команда: q
a
q
a
S,
где S={L,
R,
C}
(влево, вправо, стоп). При этом машина
одну конфигурацию переводит в другую.
Программа –
это совокупность всех команд, выполняемых
машиной. Каждая программа должна
содержать не более одной команды для
каждого набора q
a
,
начинающуюся словами q
a
.
Если известно, что какой-то набор q
a
никогда
не реализуется, то команду с ним можно
не писать. Порядок команд в программе
произволен.
Машина Тьюринга – это набор из алфавита, внутренних состояний и программы. Кроме того, надо указать конфигурацию в начальный момент времени.
Если машина, начав работать с некоторым словом на ленте, придёт в конечное состояние и остановится, то она называется применимой к этому слову. Результат её работы – конечное слово на ленте. Если она не придёт в конечное состояние и не остановится, то она не применима к данному слову и результат её работы не существует. Пример: начальное состояние – на самом правом не пустом символе, если он существует, алфавит – {0, /}. В этом алфавите 0 – пустой символ, а / (палка) записывает положительные числа. Например, число пять – это пять палок.
q
/
q
/ R
q
- начальное состояние
q
0
q
0 R
q
- память о сдвиге (вправо) с начального
символа
q
0
q
/ C
q
- конечное состояние.
q
/
q
/ C
Это программа. В
неё нет команд для наборов q
/ и q
0, команд с этими левыми частями, так как
машина в таких состояниях не оказывается.
Это реализована функция f(x)=x+1.
Здесь x
– число палок {/} на ленте. Эту же функцию
реализует и такая программа:
q
/
q
/
R
q
- начальное состояние и память о сдвиге
(вправо)
q
0
q
/ C
q
- конечное состояние.
q
/
q
/ C
Эта машина применима к любому слову из алфавита {0, /} при начальном состоянии на самом правом не пустом символе, если он есть.
Пример: функция
f(x)=2
x.
Ставим головку на самый левый не пустой
символ, если он есть. Числа x
ограничены сверху числом t
(x<=t).
q
/
q
/ R
q
- память о 1 (единице)
q
0
q
0 C 2
0=0
q
0
q
0 C
стоп
q
/
q
/ R
q
-
память о 2 (двойке)
……………..
q
/
q
/ R
q
-
память о t
q
0
q
/ R
q
-
память, что надо дописать ещё (t-1)
палок
q
0
q
/ R
q
- память, что надо дописать ещё (t-2)
палок
……………..
q
0
q
/
R
q
- память, что надо дописать ещё одну
палку
q
0
q
/ C
всё дописано
q
/
q
/ C
стоп
q
0
q
/ R
q
0
q
/ R
……………..
q
0
q
/
R
q
0
q
/ C
Команда с левой
частью q
/ отсутствует, так как числа x
не превышают числа t.
Команда может находиться в любом месте программы. Для каждого алгоритма существует множество программ, и, значит, множество машин Тьюринга. Машины бывают конечные и бесконечные. Два вышеприведённых примера – это конечные машины Тьюринга. Три бесконечные машины Тьюринга:
q
/
q
/ R q
/
q
/ R q
/
q
0 C
q
0
q
0 R q
0
q
0 L q
0
q
/ C
Программы верны, так как конечное состояние может совпасть с начальным. Такое совпадение есть в программе обнуления, где начальная конфигурация – на самом левом не пустом символе, если он есть:
q
0
q
0 C
q
/
q
0 R
Это конечная программа с одним внутренним состоянием.