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

UptoLike

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

Тьюринга, способную выполнять любой алгоритм, а значит работу любой машины
Тьюринга. В ней входное слово должно включать изображение программы и входное слово
интерпретируемой машины.
Чтобы получить изображение программы интерпретируемой машины, нужно
последовательно, строка за строкой, закодировать эту программу в алфавите универсальной
машины. Универсальная машина Тьюринга должна иметь фиксированный внешний
алфавит, используемый при записи программы, включая и алфавит интерпретируемой
машины.
Она должна быть приспособлена к приему в качестве исходной информации
всевозможных состояний устройства управления и конфигураций, в которых могут
встречаться буквы из разнообразных алфавитов со сколь угодно большим числом различных
букв.
Это достигается путем кодирования конфигурации и программы любой заданной
машины Тьюринга в символах входного алфавита универсальной машины. Само
кодирование должно выполняться следующим образом:
1) различные буквы должны заменяться различными кодовыми группами, но одна и та
же буква должна заменяться всюду, где бы она не встречалась, одной и той же кодовой
группой;
2) строки кодовых записей должны однозначным образом разбиваться на отдельные
кодовые группы;
3) должна существовать возможность распознать, какие кодовые группы соответствуют
различным сдвигам управляющей головки (R, L, E), и различать кодовые группы,
соответствующие буквам внутреннего алфавита и буквам внешнего алфавита.
Рассмотрим пример такого кодирования для машины Тьюринга Т, имеющей внешний
алфавит A = {a
1
, a
2
, ... , a
k
} и внутренний алфавит Q = {q
1
, q
2
, ... , q
z
}. Если внешний алфавит
состоит из символов А = {0, 1}, то условия кодирования будут соблюдены при следующем
способе кодирования.
1. В качестве кодовых групп возьмем 3+k+m различных слов вида 100...01, где между
единицами проставляются нули; k - число символов внешнего алфавита; m - число
состояний устройства управления.
Тогда разбивка строк на кодовые группы производится путем выделения
последовательностей нулей, заключенных между двумя единицами.
2. Сопоставление кодовых групп исходным символам внешнего и внутреннего
алфавитов осуществляется согласно следующей таблице кодирования:
Буква К одовая группа
R
E
L
101
1001
10001
a
1
a
2
a
k
100001
10000001
1 0 ...........0 1
.................................
Внешний
алфавит
- 6 нулей
2(k + 1) нулей
- 4 нуля
Четное
число
нулей,
больш ее
чем 2
q
1
q
2
1000001
100000001
q
m
1 0 ................0 1
.................................
Внутренний
алфавит
( со сто ян и я)
- 5 нулей
- 7 нулей
2(m + 1)+ 1 нулей
Нечетное
число
нулей,
больш ее
чем 3
Например, для машины Тьюринга, которая перерабатывает слово bcad в слово bccd,
входное слово в универсальной машине Тьюринга с данным кодом будет представлено
следующей строкой:
10000001 1000000001 100001 100000000001,