Машина Тьюринга

1 Вариант

1. Имеется машина Тьюринга с внешним алфавитом A={a₀,1}, алфавитом внутренних состояний Q={q₀,q₁}и функциональной схемой (программой)

	q0	q1
a0		q01П
1	q2a0Л	q11П

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

1. 1a₀11a₀a₀11 (обозревается ячейка 4, считая слева)

2. 11a₀111a₀1 (обозревается ячейка 2, считая слева)

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

2. Имеется машина Тьюринга с внешним алфавитом A={a₀,1}, алфавитом внутренних состояний Q={q_0,q₁,q_2,q₃,q_4,q₅,q_6,q₇}и функциональной схемой (программой)

	q1	q2	q3	q4	q5	q6	q7
a0	q4a0П	q6a0П	q6a0П	q01	q4a0П	q0a0	q6a0П
1	q21Л	q31Л	q11Л	q5a0	q5a0	q7a0	q7a0

Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина входное слово 11111, исходя из стандартного начального положения (машина находится в состоянии q_1, обозревается крайняя правая ячейка слова)

3. На ленте машины Тьюринга содержится последовательность символов «+». Напишите программу для машины Тьюринга, которая каждый второй символ «+» заменит на «-». Замена начинается с правого конца последовательности. Автомат в состоянии q_х обозревает один из символов указанной последовательности. После построения программы-таблицы опишите словами, что выполняется машиной в каждом состоянии.

2 Вариант

1. Имеется машина Тьюринга с внешним алфавитом A={a₀,1}, алфавитом внутренних состояний Q={q₀,q₁}и функциональной схемой (программой)

	q0	q1
a0		q01П
1	q2a0Л	q11П

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

1. 1a₀a₀111 (обозревается ячейка 3, считая слева)

2. 1111a₀11 (обозревается ячейка 4, считая слева)

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

2. Имеется машина Тьюринга с внешним алфавитом A={a₀,1}, алфавитом внутренних состояний Q={q_0,q₁,q_2,q₃,q_4,q₅,q_6,q₇}и функциональной схемой (программой)

	q1	q2	q3	q4	q5	q6	q7
a0	q4a0П	q6a0П	q6a0П	q01	q4a0П	q0a0	q6a0П
1	q21Л	q31Л	q11Л	q5a0	q5a0	q7a0	q7a0

Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина входное слово 1a₀111a₀a₀1111, исходя из стандартного начального положения (машина находится в состоянии q_1, обозревается крайняя правая ячейка слова)

3. На ленте машины Тьюринга содержится последовательность символов «+». Напишите программу для машины Тьюринга, которая каждый второй символ «+» заменит на «-». Замена начинается с правого конца последовательности. Автомат в состоянии q_х обозревает один из символов указанной последовательности. После построения программы-таблицы опишите словами, что выполняется машиной в каждом состоянии.

3 Вариант

1. Имеется машина Тьюринга с внешним алфавитом A={a₀,1}, алфавитом внутренних состояний Q={q₀,q₁}и функциональной схемой (программой)

	q0	q1
a0		q01П
1	q2a0Л	q11П

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

1. 11a₀1111 (обозревается ячейка 3, считая слева)

2. 1111111 (обозревается ячейка 4, считая слева)

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

2. Имеется машина Тьюринга с внешним алфавитом A={a₀,1}, алфавитом внутренних состояний Q={q_0,q₁,q_2,q₃,q_4,q₅,q_6,q₇}и функциональной схемой (программой)

	q1	q2	q3	q4	q5	q6	q7
a0	q4a0П	q6a0П	q6a0П	q01	q4a0П	q0a0	q6a0П
1	q21Л	q31Л	q11Л	q5a0	q5a0	q7a0	q7a0

Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина входное слово 11a₀a₀111111, исходя из стандартного начального положения (машина находится в состоянии q_1, обозревается крайняя правая ячейка слова)

3. На ленте машины Тьюринга содержится последовательность символов «+». Напишите программу для машины Тьюринга, которая каждый второй символ «+» заменит на «-». Замена начинается с правого конца последовательности. Автомат в состоянии q_х обозревает один из символов указанной последовательности. После построения программы-таблицы опишите словами, что выполняется машиной в каждом состоянии.

4 Вариант

1. Имеется машина Тьюринга с внешним алфавитом A={a₀,1}, алфавитом внутренних состояний Q={q₀,q₁}и функциональной схемой (программой)

	q0	q1
a0		q01П
1	q2a0Л	q11П

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

1. 1111111 (обозревается ячейка 3, считая слева)

2. 1a₀11a₀a₀11 (обозревается ячейка 4, считая слева)

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

2. Имеется машина Тьюринга с внешним алфавитом A={a₀,1}, алфавитом внутренних состояний Q={q_0,q₁,q_2,q₃,q_4,q₅,q_6,q₇}и функциональной схемой (программой)

	q1	q2	q3	q4	q5	q6	q7
a0	q4a0П	q6a0П	q6a0П	q01	q4a0П	q0a0	q6a0П
1	q21Л	q31Л	q11Л	q5a0	q5a0	q7a0	q7a0

Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина входное слово 11a₀111, исходя из стандартного начального положения (машина находится в состоянии q_1, обозревается крайняя правая ячейка слова)

3. На ленте машины Тьюринга содержится последовательность символов «+». Напишите программу для машины Тьюринга, которая каждый второй символ «+» заменит на «-». Замена начинается с правого конца последовательности. Автомат в состоянии q_х обозревает один из символов указанной последовательности. После построения программы-таблицы опишите словами, что выполняется машиной в каждом состоянии.