Лекция 6

полу бесконечной ленты, считывающе - записывающей каретки, лентопротяжного механизма и

логического устройства, которое может находиться в одном из дискретных состояний Q{q0, q1,..., qs}.

Алфавит

Алфавит А ={ λ, a1,a2,…., an}

λ - пробел

L

R

S

пяти символов:
qi am qr ak sp , где 0

 i, r  s, 0  m, k  n,
sp {R,L,S}.

Оно означает, что находясь в состоянии qi и прочитав в обозреваемой ячейке символ am следует записать в обозреваемую ячейку символ ak, перейти в состояние qr и переместить ленту влево (sp=R), вправо (sp =L) или не сдвигать ленту (sp=S).

которые записывают символы заданного алфавита А ={а0,а1,…,ам}. а0

– пробел (также обозначим λ ).
Управляющее устройство, которое может находиться в одном из состояний Q = {q0,q1,…,qn}. q0,q1 – наз. заключительным и начальным состоянием соответственно.
Каретка обозревает ячейку, может перемещаться за один такт влево, вправо или стоять на месте (L,R,E).

положение головки называют конфигурацией машины.

λθ1θ2 … θm-1 qi θm … θk λ, где θiA.

Запись означает, что в слове из k символов в состоянии логического устройства qi обозревается ячейка с символом θm. Иначе конфигурацию машины можно представить в виде
θ’ qi θ’’.

заключительная конфигурация

конфигураций. Если она приводит к заключительной конфигурации, то говорят, что

машина применима к К0, иначе не применима

определения и областью значения, являющейся конечными словами в алфавите А.

F:

A* -> A*

A ={ _, 1}, Q = {q0,q1,q2}
q1 _

-> q2 1 S
q1 1 -> q1 1 R
q2 1 -> q2 1 L
q2 _ -> q0 _ R
Пусть К0 = q1 1x+1
q1 1x+1 -> 1 q1 1x -> … -> 1x+1 q1 _ -> 1x+1 q2 1 -> ... -> q2 1x+2 -> q2 _1x+2 ->q0 1x+2

1 E
q1 1 -> q1 1

R
q2 1 -> q2 1 L
q2 _ -> q0 _ R

q11111 ->1q1111 ->11q111 ->111q11
->1111q1 _ ->1111q21->111q211
->11q2111->1q21111->q211111 ->
q2 _ 11111->q0 11111

={ _, 1}, Q = {q0,q1,q2}
q1 _ -> q1

_ R
q1 1 -> q2 _ R
q2 1 -> q2 _ R
q2 _ -> q0 1 E
Пусть К0 = q1 1x+1
q1 1x+1 -> q2 1x -> ... -> q2 _ -> q01

N0 , A ={ _, 1, *}, Q = {q0,q1,q2,

q3}

q1 1 -> q2 _ R
q2 1 -> q2 1 R
q2 * -> q2 1 R
q2 _ -> q3 _ L
q3 1 -> q4 _ L
q4 _ -> q0 _ R
q4 1 -> q4 1 L
(основные значащие команды)

> q2 1x * 1y+1 -> … ->
1x q2

* 1y+1 > 1x+1 q2 1y+1 -> 1x+y+2 q2 -> 1x+y+1 q3 1 -> 1x+y q4 1 -> … -> q4 _1x+y+1 -> q0 1x+y+1

МТ f(p) = f2(f1(P)).

существует МТ которая начальную конфигурацию q1 P переводит в заключительную

q0 f1(P) * f2(P)).

которая начальную конфигурацию q1 e P переводит в заключительную

q0 f1(P) , если е =0 и в
q0 f2(P), если е=1.

по МТ?