Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Теорема о переводе

Читайте также:
  1. S231 П Сингл (Магнитное поле движущегося заряда, теорема о циркуляции)
  2. Анализ основных смысловых ошибок при переводе.
  3. Гармонический анализ периодических процессов. Теорема Фурье. Гармонический спектр сигнала.
  4. Глава 1. Теоретические основы темы «Теорема Менелая и теорема Чевы ».
  5. Занятия 3-4. Тема: Теорема Чевы и ее следствия. Применение теоремы Чевы и теоремы Менелая к задачам на доказательство.
  6. Изучение темы «Теорема Менелая и теорема Чевы» в курсе геометрии 10 класса.
  7. Интегральная теорема Муавра-Лапласа

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

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

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

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

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

.

 

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

Имеет место такая теорема:

Теорема (о переводе, А.А. Марков). Если - алгорифм в алфавите , а - его перевод, то для любого слова имеет место условное равенство .

Доказательство этой теоремы мы не приводим.

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

Следствие. Если - алгорифм в алфавите типа , то

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

 

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

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

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

 


Дата добавления: 2015-07-15; просмотров: 124 | Нарушение авторских прав


Читайте в этой же книге: Определение | Объединение | Разветвление | Повторение |
<== предыдущая страница | следующая страница ==>
Эквивалентность алгорифмов| Теоремы сочетания

mybiblioteka.su - 2015-2024 год. (0.006 сек.)