Теория алгоритмов и формальных языков. Мелихов А.Н - 23 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

2) 111111111 ++ ; 9) 111111111
+
+
;
3)
111111111 ++ ; 10) 111111111
+
+
;
4)
111111111 ++ ; 11) 111111111
+
+
;
5)
111111111++
; 12)
111111111
+
;
6)
111111111 ++ ; 13) 111111111;
7)
111111111++
; 14)
111111111
.
Процедура окончена. Применена заключительная подстановка
11 → .
Гипотеза Маркова. Всякий алгоритм в алфавите А эквивалентен
некоторому нормальному алгоритму в том же алфавите.
Эта гипотеза позволяет строго проводить доказательство
алгоритмической неразрешимости того или иного круга проблем. В качестве
примера приведем доказательство алгоритмической неразрешимости
проблемы самоприменимости алгоритма.
Пусть в некотором алфавите
},...,,{
21 n
aaaА
=
задан нормальный
алгоритм Г. В записи подстановок, кроме букв алфавита А, содержатся
символы → и , (запятая). Обозначив эти символы буквами а
n+1
и а
n+2
,
получим возможность изображать алгоритм Г словом в расширенном
алфавите
},,,...,,{
2121 ++
=
nnn
aаaaaА . Применим теперь алгоритм Г к слову,
которое его изображает.
Если алгоритм Г перерабатывает это слово в некоторое иное слово,
после чего наступает остановка, то это означает, что алгоритм Г применим к
собственной записи. Такой алгоритм назовем самоприменимым. В
противном случае алгоритм будем называть несамоприменимым.
Естественно, возникает задача распознавания самоприменимости: по
записи
данного алгоритма определить, самоприменим этот алгоритм или нет.
Решение этой задачи можно представить в виде построения некоторого
нормального алгоритма Δ, который, будучи применим ко всякой записи
самоприменимого алгоритма Г, перерабатывает эту запись в некоторое слово
М, а применяемый ко всякой записи несамоприменимого алгоритма Г,
перерабатывает эту запись в некоторое
иное слово L. В этом случае по

Страницы