Математическая логика и теория алгоритмов. Галуев Г.А. - 59 стр.

UptoLike

ВУЗ: 

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

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

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 59 из 64
© 2003 Галуев Геннадий Анатольевич
имела место в МТz до применения команды, к конфигурации в которую переходит МТz
после применения команды. Здесь P и Q некоторые слова (контекст). Команде q
i
x
j
rq
l
соответствует подстановка Px
k
q
i
x
j
Q→Pq
l
x
k
x
j
Q. Команде q
i
x
j
lq
j
соответствует подстанов-
ка Pq
i
x
j
Q→Px
j
q
l
x
l
Q.
Кроме того введем в систему П дополнительные подстановки, которые не соот-
ветствуют никаким командам МТz и применяются только тогда, когда МТz переходит
в заключительную конфигурацию и останавливаются (в этом случае МТz встретилась
с ситуацией q
i
x
j
, которой нет ни в одной команде или выполнила команду q
i
x
j
sq
0
).
Подстановки hPq
i
x
j
Qh→hPq
j
x
j
Qh, которые для всех пар (q
i
x
j
), не встречающихся в ле-
вых частях команд МТz, заменяют символ состояния q
i
маркером q. Подстановки
hPqx
j
Qh→hPqQh стирающие все символы (кроме h) справа от q. Подстановки
hPqh→hPsh вводит символ S слева от правого h. Подстановки hPx
j
sh→hPsh стирают
все символы между левым h и s. И наконец подстановки hx
0
...x
0sh
→ hsh, которые пе-
ремещают левый маркер h в позицию предшествующую символу S.
Пока МТz выполнит вычисления над числами n в соответствии с командами, на-
чиная с аксиомой h
nq
0
h , формируется вывод в полутуэвской системе П по принципу:
одна применяемая команда МТz один шаг вывода в системе П. Как только МТz остано-
вилась, к полученной формуле системы П применяются дополнительные (введенные
выше) подстановки, которые в конечном итоге приводят к формуле hsh. Таким обра-
зом теорема доказана.
Заметим что в системе П
от числа n зависит только аксиома n nq
0
h, алфавит
подстановки не зависит от n. Если n принимает значение из множества целых не от-
рицательных чисел, то действуя таким образом как указано в доказательстве теоре-
мы, мы получим семейство полутуэвских систем П, с помощью этого семейства мно-
жеству тех чисел n, с которым применима МТz , ставиться в соответствие единст-
венная формула hsh. Это
позволяет построить систему П, которая, исходя из аксиомы
hsh, выдавала бы в качестве заключительных формул все целые числа к которым
применима МТz. Для этого необходимо в качестве аксиомы выбрать hsh, а в качестве
системы подстановок взять подстановки обратные, обратные подстановкам системы
П. Тогда, если объединить системы П и
Ï
′
(при этом в качестве аксиомы такой объе-
диненной системы взять hsh), то легко видеть, что МТz будет соответствовать туэв-
ская система Т. Построенные комбинаторные системы П,
Ï
′
и Т, соответствующая
МТz, сопоставляют входным словам машины Z формулы в указанных системах. Вы-
брав в качестве МТz такую машину для которой неразрешима проблема остановки,
мы приходи к выводу что в соответствующих полутуэвской и туэвской системах не-
разрешима проблема доказуемости. Это же справедливо для нормальных постовских
систем, что еще раз доказывает
справедливость тезиса Черча об эквивалентности
различных утонченных понятий алгоритма.
Как уже отмечалось раннее теория алгоритмов явилась основой для создания
современной вычислительной математики и во многом обусловило появление ЭВМ и
алгоритмических языков для их программирования. Рассмотрим более подробно со-
временные понятия алгоритмов, алгоритмического языка и программы и покажем их
связь с рассмотренными
нами на протяжении ряда лекций основами теорий алгорит-
мов.
Лекция 11.
Взаимосвязь теории алгоритмов и современной информати-
ки
Современное понятие алгоритма. Свойства алгоритмов.
Основные результаты, полученные в рамках рассмотренной нами теории алго-
ритмов, позволяет перейти от интуитивного понятия алгоритма к его полному опреде-

Страницы