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

®0q_s 0q_s Л

1q_s 1q_s Л 2q_s 2q_s Л ……… 7q_s 7q_s Л 8q_s 8q_s Л 9q_s 9q_s Л Lq_s L!Н

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

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

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