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

5.3. Машина Тьюринга определяется следующей функцио­нальной схемой:

А Q	q1	q2	q3
а0		q31П	q1а0Л
1	q2 а0Л	q21Л	q31П
*	q0 а0	q2*Л	q3*П

Определите, в какое слово перерабатывает машина каждое из следующих слов, исходя из начального стандартного состояния (определение которого см. в задаче 5.2). После этого постарайтесь усмотреть общую закономерность в работе ма­шины:

а) 111 * 111; б)1111 * 11; в) 111 * 1; г) 1 * 11;

д) 11 * 111; е) 11111 * ; ж) * 1111.

5.4. Машина Тьюринга определяется следующей функцио­нальной схемой:

А Q	q1	q2	q3	q4
а0	q1а0П	q3а0П	q3а0Л	q1а0Л
1	q2а0Л	q21Л	q4а0П	q41П
*	q0а0	q3*Л		q4*П

Определите, в какое слово перерабатывает машина каждое из следующих слов, исходя из стандартного начального состоя­ния:

а) 111 * 11; б) 11 * 11; в) 1111 * 1; г) 11111 * 111; д) 11111 * 1111.

Постарайтесь выявить общую закономерность в работе машины.

5.5. Для машины Тьюринга, определяемой следующей функциональной схемой:

А Q	q1	q2	q3	q4
а0	q4а0П	q3а0Л	q1а0П	q0а0Л
1	q2a	q1b	q11П	q11Л
a	q1aЛ	q2aП	q31Л	q4а0П
b	q1bЛ	q2bП	q3а0Л	q41П

и для следующих слов определите, в какое слово переработа­ется каждое из них данной машиной, исходя из начального положения, при котором машина находится в состоянии q1 и обозревается указываемая ячейка:

а) 11111 (обозревается ячейка 2, считая слева);

б) 111 (обозревается ячейка 1);

в) (обозревается ячейка 4);

г) 111111 (обозревается ячейка 2);

д) (обозревается ячейка 6).
Какова общая закономерность работы машины?

5.6. Машина Тьюринга с внешним алфавитом А = {а0, 1} определяется следующей программой:

А Q	q1	q2	q3
а0	q2 а0П	q2 а0П	q0а0
1	q11П	q31П	q31П

Остановится ли когда-нибудь эта машина, если она начнет перерабатывать следующее слово (в начальный момент; в состоянии q1, машина обозревает ячейку, в которой записана самая левая буква перерабатываемого слова):

а) 111а0а01;

б) 11а0а011а01;

в) 111111?

Если остановка происходит, то какое слово получается в ре­зультате, какая ячейка и в каком (перед остановкой) состоя­нии обозревается?

5.7. Остановится ли когда-нибудь машина Тьюринга, заданная следующей программой:

А Q	q1	q2	q3
а0	q1П	q3а0Л	q0а0
1	q21П	q1а0П	q21Л

если она начнет перерабатывать следующее слово, начав в состоянии q1 обозревать ячейку, в которой записана самая левая буква перерабатываемого слова:

а) 1111а01;

б) 11111;

в) 1а01а01?

Если машина остановится, то какова ее заключительная кон­фигурация?

5.8. Останавливается ли когда-нибудь машина Тьюрин­га с внешним алфавитом А={а0,1} и функциональной схе­мой:

А Q	q1	q2	q3	q4
а0	q2а0П	q3а0Л	q11Л	q0а0
1	q21П	q4а0П	q01	q2а0

при переработке следующих слов (в начальный момент головка машины обозревает ячейку ленты, в которой запи­сана самая левая буква перерабатываемого слова):

а) 111а01 а01;

б) 1111;

в) 1а01а01 а01?

Если машина останавливается, то какое слово получается в результате, какая ячейка и в каком состоянии обозревается?

КОМПОЗИЦИЯ, ИТТЕРАЦИЯ, РАЗВЕТВЛЕНИЕ

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

5.9. Построить композицию машины Т1Т2 по паре состояний (q10,q21) и найти результат применения композиции к слову Р (q20 – заключительное состояние машины T2)

1)

		q11	q12			q21	q22
T1	0	q12 0 R	q10 1 L	T2	0	q22 1 R	q22 1 R
	1	q12 1 R	q11 0 R		1	q21 0 L	q20 1 S

a) P=130212 б) Р=1401

2)

		q11	q12	q13			q21	q22
T1	0	q10 0 L	q13 0 R	q11 0 R	T2	0	q22 1 L	q20 0 R
	1	q12 1 R	q13 1 R	q11 0 R		1	q22 1 L	q21 0 L

а) Р= , б) Р=1201013

3)

		q11	q12	q13			q21	q22	q23
T1	0	q12 0 R	q13 0 R	q10 1 L	T2	0	q22 0 L	q23 0 L	q20 0 R
	1	q11 1 R	q11 1 R	-		1	q21 1 L	q22 1 L	q23 1 L

a) P=, б) Р=