Существование универсальных вычислителей. Алгоритмические проблемы и взаимосвязь алгоритмических систем.
Категория реферата: Рефераты по информатике, программированию
Теги реферата: шпоры бесплатно, реферат россия скачать
Добавил(а) на сайт: Снаткин.
Предыдущая страница реферата | 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 | Следующая страница реферата