Реферат: Существование универсальных вычислителей. Алгоритмические проблемы и взаимосвязь алгоритмических систем.

®0qs 0qs Л

1qs 1qs Л 2qs 2qs Л ……… 7qs 7qs Л 8qs 8qs Л 9qs 9qs Л Lqs L!Н

Рис. 4.1. Линейная запись функциональной схемы МТ, вычисляющей U1 (n).

Такое представление программы обеспечивает взаимнооднозначное соответствие с табличной формой записи, а стало быть ничего из таблицы при этом не теряется и ничего не добавляется.

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

Будем записывать символы исходного слова на ленте через ячейку. В образовавшиеся пустые ячейки ленты будем записывать справа от обозреваемого символа текущее состояние каретки.

Теперь рассмотрим проблему алфавита. Напомним, эта проблема состоит в том, что УМТ должна иметь определенный алфавит, который не может изменяться. В то же время мы не можем знать заранее, с какими алфавитами будут работать МТ, которые будет интерпретировать наша УМТ. Решение этой проблемы - кодирование символов из алфавита МТ символами алфавита УМТ. При этом важно позаботиться о том, чтобы:

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

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

В качестве алфавита УМТ выберем алфавит {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 примут следующий вид:

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

Для каждого шага интерпретирующего алгоритма надо построить МТ с алфавитом {0,1}, после чего объединить их должным образом, с помощью операций o, ||, if-then-else, while-do.

Обоснование закончено.

Разрешимость алгоритмических проблем.

В этом разделе мы дадим примеры доказательства неразрешимости конкретной алгоритмической проблемы - проблемы самоприменимости.

Определение 4.1: Алгоритмической проблемой называется проблема построения алгоритма для решения класса задач.

Естественно возникает вопрос: Всякая ли алгоритмическая проблема разрешима? Вплоть до начала ХХ века среди математиков существовала уверенность в разрешимости любой математической проблемы. Как уже отмечалось во введении, Лейбниц был один из первых, кто пришёл к идее исчисления. Он считал, что решение математической проблемы сводится к манипуляции с символами с помощью специальным образом подобранными правилами вывода (замены одних комбинаций символов на другие). Проблема, по мнению Лейбница, состояла лишь в том, чтобы построить надлежащим образом систему этих правил. Более того - он считал, что можно построить универсальный набор правил для решения любой математической проблемы. Джонатан Свифт в своей книге “Приключения Гулливера” подшутил над этой идеей Лейбница в образе мудреца, вращающего колёса с табличками в поисках нужного решения.

Английский математик Чёрч первым дал пример неразрешимой поблемы, известной как проблема выводимости.

К-во Просмотров: 222
Бесплатно скачать Реферат: Существование универсальных вычислителей. Алгоритмические проблемы и взаимосвязь алгоритмических систем.