Применение машин Тьюринга к словам (стр. 3 )

Пусть - некоторое заключительное состояние машины Т, а - какое-либо состояние машины Т, не являющееся заключительным. Заменим всюду в программе П машины Т символ на . Получим программу , определяющую машину (,). Машина называется итерацией машины Т (по паре состояний (,)).

5.10. Найти результат применения итерации машины Т к слову Р по паре состояний (q0,qi) (заключительными состояниями являются q0 и q0’ )

1)  i=1,

a) P=13k, b) P=13k+1, c) P=13k+2, k>=1

	q1	q2	q3	q4	q5
0	q0 0 S	q4 0 S	q5 0 S	q4 1 R	q0’ 0 R
1	q2 0 R	q3 0 R	q1 0 R	-	-

2)  i=1,

a) P=12k, b) P=12k+1 , k>=1

	q1	q2	q3	q4	q5	q6
0	q0’ 0 R	q0’ 0 R	q4 0 R	q5 1 L	q6 0 L	q0 0 R
1	q2 0 R	q3 0 R	q3 1 R	q4 1 R	q5 1 L	q6 1 L

3)  i=3,

a) P=1x01y , x, y>=1

	q1	q2	q3	q4	q5	q6
0	q0 0 L	-	q4 0 R	q5 1 L	q6 0 L	q0’ 0 R
1	q1 2 R	q2 1 R	-	q4 1 R	q5 1 L	q6 1 L
2	-	q3 1 R	-	-	-	q0 1 R

Пусть машины Т1 , Т2, Т3 имеют соответственно программы П 1, П2, П3. Предположим, что внутренние алфавиты этих машин не пересекаются. Пусть и - некоторые различные заключительные состояния машины Т1. Заменим всюду в программе П1 состояние некоторым начальным состоянием машины Т2, а состояние - некоторым начальным состоянием машины Т3. Затем новую программу объединим с программами П2 и П3. Полученная программа П определяет машину Т= Т(Т1(,),Т2(,),Т3), называемую разветвлением машин Т2 и Т3, управляемым машиной Т1 .

5.11. Найти результат применения разветвления машины Т= Т(Т1(,),Т2(,),Т3), к слову Р (q20 – заключительное состояние машины T2, а q30 – заключительное состояние машины T3).

1) a) P=1013, b) P=1301

		q11	q12			q21			q31	q32
T1	0	q12 0 R	q’10 0 R	T2	0	q20 1 S	T3	0	q32 1 L	q30 1 L
	1	q12 1 R	q’’10 1 L		1	q21 0 R		1	q31 1 L	-

2) a) P=1x021, x>=1, b) P=1x0101y01z, x, y,z>=1

q11

q12

q13

q21

q22

q31

q32

T1

0

q12 0 R

q’10 0 L

q’’10 0 R

T2

0

q22 0 L

q20 0 R

T3

0

q32 0 R

q30 1 S

1

q11 1 R

q13 1 R

q13 1 R

1

q21 1 L

q22 1 L

1

q31 1 R

q31 1 R

5.12По программе МТ написать аналитическое выражение для функций f(x) и f(x, y), вычисляемых МТ.

1) 2)

	q1	q2					q1	q2	q3	q4	q5
0	q21L	q00R				0	q30R	q10L	q40L	q40L	q00R
1	q11R	q 21L				1	q11R	q30R	q30R	q51L	q51L

3)

	q1	q2	q3	q4	q5	q6	q7	q8	q9
0	q20R	q30R	q01S	q50R	q30L	q70L	-	q90L	q10R
1	q20R	q41R	q81L	q41R	q61R	q61R	q80L	q81L	q91R

4)  f(x)-? В начальной конфигурации обозревается крайняя правая единица ленты