05. Эквивалентность нормальных алгорифмов. Теорема о переводе

НА и типа над алфавитом называют Вполне Эквивалентными относительно алфавита , если для всякого слова имеет место и если выполняется , то .

В теории нормальных алгорифмов используется выражение ,

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

Рассмотрим теперь некоторые преобразования схем НА, которые дают НА, вполне эквивалентный исходному относительно заданного алфавита.

1) Замыкание нормального алгорифма

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

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

2) Естественное и формальное распространение

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

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

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

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

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

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

.

Перевод пустого слова естественно определить как пустое слово. Например, если , и , то . Здесь предполагается, что буквы исходного алфавита нумеруются, как 1-я, 2-я и 3-я.

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

Сформулируем теперь без доказательства теорему, которая в данном контексте называется теоремой о переводе, хотя она на самом деле является одним из следствий более общего утверждения, принадлежащего А. А. Маркову и названной им теоремой о переводе [7].

Теорема 1. Каков бы ни был нормальный алгорифм типа над алфавитом , может быть построен нормальный алгорифм в алфавите , вполне эквивалентный Относительно алфавита , то есть для любого слова имеет место условное равенство .

Идея доказательства состоит в том, что все буквы из исходного расширения алфавита Заменяются их переводами в алфавит , соответственно преобразуется схема исходного НА и все слова его процесса работы с исходным словом, после чего доказывается полная эквивалентность полученного НА и исходного.

< Предыдущая		Следующая >