Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 23 стр.

UptoLike

Составители: 

самоприменимости машин Тьюринга, имея в виду их применение к своим линейным
изображениям.
Таким образом, возникает задача: как узнать, является ли самоприменимым тот или
иной алгоритм.
Проблема распознавания самоприменимости алгоритмов состоит в том, чтобы найти
единый конструктивный прием, позволяющий за конечное число шагов по схеме любого
данного алгоритма узнать, является алгоритм самоприменимым или несамоприменимым.
Доказательство того, что общего алгоритма распознавания самоприменимости не
существует, можно проводить, используя алгоритмические системы Тьюринга. На основе
этого доказательства было показано, что проблема распознавания самоприменимости
алгоритмически неразрешима.
3.11. Задания для самостоятельной работы
1. Построить машину Тьюринга, выполняющую операцию конкатенации двух цепочек,
заданных во входном алфавите А = {0, 1, *, ε}.
2. Построить машину Тьюринга, выполняющую операцию копирования входной
цепочки, заданной в алфавите А = {1, *, ε }, где символ “*” используется в качестве
разделителя двух цепочек.
3. Построить машину Тьюринга в алфавите А={0, 1}, которая, начав работу с последней
единицы массива из единиц, сдвигает его на одну ячейку влево, не изменяя остального
содержимого ленты. Головка останавливается на первой единице перенесенного массива.
4. По заданной совокупности команд машины Тьюринга Т и начальной конфигурации К
найти заключительную конфигурацию.
4.1.
q
0
1 q
0
1R, q
1
0 q
z
1E,
q
0
0 q
1
1R, q
1
1 q
1
1L,
а) К = 1101q
0
01; б) К = 101q
0
010.
4.2.
q
0
0 q
0
1L, q
1
1 q
0
0R,
q
0
1 q
1
1R, q
1
0 q
z
0L,
а) K = 1q
1
0111; б) K = 1q
1
1111.
4.3.
q
0
0 q
1
0L, q
1
0 q
1
1L,
q
0
1 q
0
0R, q
1
1 q
z
0R,
а) K = 1000q
1
01; б) K = 11q
1
11101.
5. Построить машину Тьюринга, которая во входной цепочке, заданной в алфавите А =
{0, 1, ε}, переставляет единицы и нули так, чтобы все единицы были в начале, а нули в конце
цепочки.
6. Построить композицию Т
1
Т
2
машин Тьюринга Т
1
и Т
2
по паре состояний (q
1z
, q
20
) и
найти результат применения композиции Т
1
Т
2
к слову D.
6.1. Машины Т
1
и Т
2
заданы таблицами соответствия:
q
10
q
11
q
12
T
1
: 0 q
1z
0L q
12
0R q
10
0R
1 q
11
1R q
12
1R q
10
0R
q
20
q
21