Предыдущая страница реферата | 1  2  3  4  5  6  7  8 | Следующая страница реферата

один и тот же символ из алфавита МТ всегда изображался одной и той же последовательностью символов из алфавита УМТ;

разные символы из алфавита МТ всегда изображались разными последовательностями символов из алфавита УМТ.

В качестве алфавита УМТ выберем алфавит {0,1}, расширенный небольшим количеством вспомогательных символов. Пусть нам надо закодировать символы МТ, у которой  |DМТ|=k;   |QМТ|=m.

Возьмем 3+k+m слов вида  1000……01,  т.е. последовательность нулей между единицами. Эти слова мы будем называть кодовыми группами (КП). На рисунке 4.2 показаны кодовые КП для символов из D, Q, и {Л, Н, П}

Л	101
Н	1001
П	10001
	100001          Здесь число нулей всегда четно. M нулей
	1000001         Здесь всегда нечетное число нулей M   нулей

Рис. 4.2  Кодовые КП для символов из D, Q, и {Л, Н, П}

Теперь для доказательства теоремы надо интерпретирующий алгоритм записать в терминах кодовых групп, шифра программы и шифра конфигурации. Например, шаг 1 будет звучать теперь так:

Обозревай в шифре конфигурации КП, расположенную левее КП, с нечётным числом нулей, т.е. код текущего состояния каретки (заметим, что такая КП в шифре конфигурации всегда одна. Убедитесь в этом).

Шаги 2 и 3 примут следующий вид:

Отыщем в шифре функциональной схемы пару соседних КП, совпадающих с парой КП в шифре конфигурации, в которой первая КП - обозреваемая и т. д.

Рекомендуем скачать другие рефераты по теме: сочинения по русскому языку, контрольные работы по алгебре.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8 | Следующая страница реферата