Составители:
Рубрика:
Конфигурация машины Тьюринга называется заключительной,
если головка машины Тьюринга находится в состоянии останова q
.
0
Работу машины Тьюринга можно описать как
последовательную смену ее конфигураций, причем машина
переходит от конфигурации K
t
к конфигурации K
t+1
в соответствии
со своей программой. Любая начальная конфигурация K
0
, которой
соответствует состояние q
1
, порождает последовательность
конфигураций K
, K , K , …, K
t
,… .
0 1 2
Эта последовательность обрывается, если машина оказывается
в заключительной конфигурации. В этом случае будем говорить, что
машина Тьюринга применима к конфигурации K
.
0
Если последовательность конфигураций K , K , K , …, K
t0 1 2
,…
никогда не обрывается, т.е. машина работает вечно
(“зацикливается”), будем говорить, что машина Тьюринга
неприменима к конфигурации K
.
0
Для решения задачи исходные данные должны быть
закодированы некоторым “естественным” образом символами
некоторого алфавита A и записаны в виде слова X на ленте машины,
причем головка в начальном состоянии q
1
∈Q обозревает самый
левый символ слова X, т.е. начальная конфигурация имеет вид q
1
X.
Результирующая конфигурация имеет вид q
0
f(X).
В этом случае будем говорить, что машина Тьюринга
вычисляет словарную функцию f(⋅), причем слово f(X) есть значение
этой функции для аргумента X. Числовые функции – это частный
случай словарных, поскольку конкретный вид символов, которыми
оперирует машина, несуществен, также как и тип данных: цифровых,
алфавитно-цифровых и т.д.
Примеры машин Тьюринга
Рассмотрим несколько примеров специализированных машин
Тьюринга с ленточным алфавитом A={Λ,+,1}, алфавитом состояний
{q
,q ,q , …, q } и алфавитом перемещений D∈{П,Л,Н}. Символ Λ
n0 1 2
145
Страницы
- « первая
- ‹ предыдущая
- …
- 59
- 60
- 61
- 62
- 63
- …
- следующая ›
- последняя »
