Универсальный алгорифм

Универсальный алгорифм.. 1

Изображение и запись нормального алгорифма. 1

Теорема об универсальном алгорифме. 2

Разрешимые и перечислимые множества. 3

Определения. 3

Проблема применимости как неразрешимая массовая проблема. 5

Универсальный алгорифм

Изображение и запись нормального алгорифма

Иногда бывает необходимо использовать одни алгорифмы в качестве исходных данных для других алгорифмов. Для этого необходимо алгорифм, используемый в качестве данного, превратить в конструктивный объект, т. е. представить словом в некотором алфавите. Существует два основных способа такой конструктивизации нормального алгогрфима: посредством изображения и посредством записи.

Пусть алгорифм является алгорифмом в алфавите . Изображение алгорифма есть слово в алфавите , где которое строится по схеме алгорифма следующим образом: выписываются в порядке следования их в схеме формулы подстановок, причем справа от каждой формулы пишется буква , каждая стрелка заменяется буквой , а каждая точка – буквой .

Например, алгорифм левого присоединения слова , заданный схемой

будет иметь такое изображение: .

Алгорифм правого присоединения слова , заданный схемой в алфавите , где , имеющей вид (в сокращенной записи)

,

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

В общем случае алгорифм, задаваемый схемой

в алфавите , будет иметь изображение в виде слова , где , если и , если .

Вместо изображения нормального алгорифма часто используют запись нормального алгорифма – слово в двухбуквенном алфавите , которое строится по изображению алгорифма согласно определению перевода буквы алфавита. Тем самым запись нормального алгорифма в алфавите есть перевод его изображения, причем буквы получают номера соответственно.

Так, запись алгорифма левого присоединения слова в алфавите будет иметь вид .

Запись нормального алгорифма обозначается .

Нетрудно понять, что как по изображению, так и по записи схема нормального алгорифма восстанавливается однозначно.

Теорема об универсальном алгорифме

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

Теорема 1 (об универсальном алогрифме). Может быть построен такой нормальный алгорифм над алфавитом , где ,что для любых нормального алгорифма и слова в алфавите имеет место условное равенство .

Алгорифм , построенный согласно данной теореме, называют универсальным нормальным алгорифмом.

Существует вариант формулировки теоремы об универсальном алгорифме, в которой вместо записи фигурирует изображение «объектного» алгорифма .

Содержательный смысл теоремы состоит в том, что универсальный алгорифм получает на вход пару «объектный алгорифм – слово», декодирует запись объектного алгорифма, восстанавливая тем самым его схему, и применяет эту схему согласно известным правилам ко входному слову. Тем самым заданный в определении нормального алгорифма алгоритм (определенный вне использования нормальных алгоримфов) применения схемы, согласно теореме об универсальном алгорифме сам может быть запрограммирован как нормальный алгорифм.

С программистской же точки зрения универсальный алгорифм есть не что иное как универсальный интерпретатор в классе программ, записанных в виде схем нормальных алгорифмов.

Разрешимые и перечислимые множества

Определения

Язык (множество слов) называют алгорифмически разрешимым, если существует нормальный алгорифм над алфавитом такой, что для каждого имеет место и .

Соответствующее определение разрешимого множества слов (более общо: множества конструктивных объектов) может быть сформулировано на основе любой другой точной модели алгоритма. В частности, если в качестве таковой выбрана машина Тьюринга, то говорят о языке, разрешимом по Тьюрингу. В общем же случае часто используют термин «алгоритмически разрешимое множество», понимая под этим, что используется та или иная точная модель алгоритма.

Алгорифм , фигурирующий в вышеприведенном определении, называют разрешающим алгорифмом для языка .

Разрешающий алгорифм может быть определен несколько иначе. Часто его определяют как алгорифм над алфавитом такой, что для каждого имеет место , причем .

Напомним, что под натуральным числом n мы понимаем слово в алфавите .

Язык (множество слов) называют алгорифмически перечислимым, если существует нормальный алгорифм над алфавитом такой, что для каждого натурального числа n имеет место , и для каждого осуществимо такое натуральное число , что .

Алгорифм называют при этом алгорифмом, перечисляющим множество L (или просто перечисляющим алгорифмом, если множество подразумевается). Говорят также, что алгорифм перечисляет множество L.

Важнейшим результатом теории алгоритмов является следующая теорема.

Теорема 2. Язык алгорифмически перечислим тогда и только тогда, когда он является областью применимости относительно алфавита V некоторого алгорифма.

Доказательство. 1) Докажем, что если множество перечислимо, то оно является областью применимости (относительно V) некоторого алгорифма .

Используя построенный ранее алгорифм, распознающий равенство двух слов в заданном алфавите, можно построить алгорифм так, что

,

где - алгорифм, перечисляющий множество L, а буква $ не принадлежит алфавиту V. Заметим, что для любых слова и натурального числа имеет место .

Построим теперь алгорифм так, что

,

где использовано известное обозначение: - «наименьшее натуральное число k, для которого истинно P(k)».

Этот алгорифм можно построить следующим образом.

Построим алгорифм как алгорифм правого присоединения слова | («палочки») к любому слову , т. е. . Определим алгорифм . Тогда для любого будем иметь . Действительно, если , то , и тогда . Если же , то алгорифм переработает слово слово , т. е. в слово . Далее алгорифм проверит равенство , и если оно выполняется, то , и тогда и т. д. Итак, алгорифм перерабатывает «пару слов» в «пару слов», в которой вторая компонента есть наименьшее натуральное число такое, что , т. е. наименьший из номеров элемента перечислимого множества . Очевидно, что используя один из проектирующих алгорифмов, можно из слова «вырезать» число . Точнее, сперва строим алгорифм так, что (это легко реализовать, присоединив к слову справа слово , а затем применив алгорифм . Тогда . Но ясно, что алгорифм применим к слову тогда и только тогда, когда . Это значит, что есть область применимости (относительно алфавита ) алгорифма , и, следовательно, этот алгорифм и есть искомый алгорифм .

2) Теперь докажем, что область применимости произвольного алгорифма есть перечислимое множество.

Во-первых, заметим, что, как можно показать, множество всех слов в любом заданном алфавите перечислимо[1].

Пусть теперь есть алгорифм над алфавитом , и - его область применимости (относительно ). Пусть алгорифм перечисляет множество всех слов в алфавите , а алгорифм аннулирует любое слово в алфавите алгорифма (этот алгорифм можно задать схемой , где ).

Определим алгорифм так, что для любого натурального выполняется .

Покажем, что алгорифм обладает следующими свойствами: а) ; б) если , то ; в) если то для некоторого .

Свойство (а) очевидно. При тогда , но так как , то , т. е. имеет место свойство (б). Если же , то при некотором , и , но тогда .

Алгорифм не является априори алгорифмом, перечисляющим множество , так как он применим, вообще говоря, не к любому натуральному числу. Однако доказывается, что его можно определенным образом «достроить» до перечисляющего алгорифма[2].

Без доказательства отметим следующий важный факт.

Теорема 3. Всякое алгорифмически разрешимое множество алгорифмически перечислимо. #

Проблема применимости как неразрешимая массовая проблема

Проблема применимости для нормальных алгорифмов формулируется следующим образом: можно ли построить нормальный алгорифм над алфавитом такой, что для любых нормального алгорифма в алфавите и слова выполнялось и , где буква $ не принадлежит алфавиту .

Мы докажем здесь, что проблема применимости не разрешима, т. е. указанный выше алгорифм невозможен.

Для этого рассмотрим сначала другую проблему, которая называется проблемой самоприменимости и формулируется следующим образом: можно ли построить такой алгорифм над алфавитом , что для любого алгорифма в алфавите , где имеет место , причем . Заметим, что согласно теореме о переводе в алфавите может быть задан любой алгорифм типа .

Таким образом, алгорифм должен аннулировать записи тех и только тех алгорифмов в алфавите , которые не применимы к собственной записи. Такие алгорифмы называют несамоприменимыми.

Пример. Естественное распространение алгорифма правого присоединения фиксированного слова в алфавите V самоприменимо, а формальное – нет.

Лемма 1. Невозможен алгорифм в алфавите , применимый к записи алгорифма в этом алфавите тогда и только тогда, когда этот алгорифм несамоприменим.

Доказательство. Пусть такой алгорифм построен. Так как он является алгорифмом в алфавите , то может быть поставлен вопрос о его самоприменимости. Если , то поскольку должен быть применим только к записям несамоприменимых алгорифмов, имеет место . Но тогда, так как несамоприменимый алгорифм, должно быть . Итак, для алгорифма имеет место . Полученное противоречие доказывает, что алгорифм не может быть построен.

Теорема 4. Невозможен алгорифм над алфавитом , применимый к записям тех и только тех алгорифмов в алфавите , которые несамоприменимы.

Доказательство. Пусть построен алгорифм над алфавитом так, что для всякого алгорифма в алфавите имеет место

.

По теореме о переводе тогда может быть построен алгорифм в алфавите так, что для любого слова

.

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

,

что невозможно в силу доказанной леммы.

(Заметим, что алфавит есть объединение алфавита с алфавитом . Тогда разрешимость проблемы самоприменимости в этом алфавите есть не что иное, как разрешимость ее в алфавите - см. лемму 1 – при рассмотрении произвольного алфавита как алфавита .)

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

Действительно, если бы указанный в формулировке этой проблемы алгорифм мог бы быть построен, то было бы осуществимо разветвление , где - алгорифм со схемой , не применимый ни к одному слову в алфавите , и тогда для всякого слова выполнялось бы

.

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

,

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

Итак, получаем утверждение:

Теорема (о неразрешимости проблемы самоприменимости). Невозможен алгорифм над алфавитом такой, что для любого алгорифма в алфавите , где имеет место , причем .

Опираясь на этот результат, можно доказать и неразрешимость проблемы применимости.

А именно, доказывается, что может быть построен нормальный алгорифм, для которого проблема применимости неразрешима, а раз удается показать, что существует частный случай массовой проблемы, который неразрешим, то и проблема в целом также неразрешима.

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

для любого слова .

Доказательство. Пусть . По теореме об универсальном алгорифме построим алгорифм над алфавитом так, что для любого алгорифма в алфавите и любого слова имеет место

.

Теперь построим алгорифм над алфавитом так, что для любого слова

.

(Это можно сделать в виде композиции алгорифма, перерабатывающего всякое слово в слово и алгорифма ).

Далее, согласно теореме о переводе построим алгорифм в алфавите , т. е. только лишь в двухбуквенном расширении алфавита так, что

.

Утверждается, что это и есть искомый и указанный в условии теоремы алгорифм.

Действительно, пусть построен алгорифм над так, что . Тогда для любого алгорифма в алфавите будем иметь , что невозможно в силу предыдущих результатов по проблеме самоприменимости[3].

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

Теорема 5. Существует алгорифмически перечислимое множество, не являющееся алгорифмически разрешимым.

Эта теорема является следствием доказанной неразрешимости проблемы применимости. Действительно, в качестве такого множества можно взять область применимости (относительно соответствующего алфавита) любого алгорифма с неразрешимой проблемой применимости.

[1] Для этого нужно задать в виде нормального алгорифма любую нумерацию множества слов, скажем, лексикографическую.

[2] См. Кушнер, с. 102-103.

[3] Алгорифм решает проблему самоприменимости в алфавите