1610906280-c80d8404f2eaa01776b47d41b0f18e85 (824375), страница 9
Текст из файла (страница 9)
Однако неисключены ситуации, в которых машина работает бесконечно, т. е. не останавливается.Для наших дальнейших рассуждений будет удобно расширить язык машин Шёнфилда и ввести дополнительные команды, отличные от команд типа INC i и DEC i, n.Чтобы вычислительные возможности исходных машин не изменились, мы будем добавлять только те команды, которые допускают реализацию в виде программы, использующей только команды типа INC i и DEC i, n. Любую дополнительную команду,обладающую таким свойством, будем называть макросом.Таким образом, любой макрос получается по следующему принципу: если P —обычная программа, то ей сопоставляется оператор P ∗ , который называется макросом и который может исполняться как отдельная команда. Программы, содержащиемакросы, будем называть макропрограммами.Исполнение макроса P ∗ , находящегося в макропрограмме в строке под номеромm, происходит следующим образом:1) Если в счетчике команд находится m, то в машину (в качестве подпрограммы)вызывается программа P .2) P исполняется с теми данными в регистрах, которые там содержались в данныймомент.3) Если работа программы P закончилась, то в счетчик команд заносится m + 1и исполнение макроса на этом заканчивается.
Если же P работает бесконечно,то макропрограмма также не останавливается.Любой макрос может использовать конечный набор параметров, каждый из которых является номером некоторого регистра (эти номера обычно присутствуют вимени макроса). Макросы не могут использовать в качестве своих параметров номера строк программы.36Глава III.
Формализации понятия вычислимой функцииПример. Исполнение последовательной пары команд 0 : INC 0 и 1 : DEC 0, n простозаносит n в счетчик команд, при этом содержимые регистров не меняются. Однакомы не можем сопоставить этой короткой программе макрос, использующий параметрn, поскольку n здесь является номером строки.Пример. Программа с простейшим циклом 0 : DEC i, 0 обнуляет содержимое i-горегистра. Обозначим макрос, соответствующий этой программе, через ZERO i.Пример.
Пусть i, j, k — фиксированные натуральные числа такие, что i 6= k и j 6= k.Обозначим через [i] → [j], (k) макрос, который копирует содержимое i-го регистра вj-й регистр, используя k-й регистр как вспомогательный. Содержимое i-го регистране изменяется. Программа, реализующая данный макрос при i 6= j, имеет следующийвид:0:1:2:3:4:5:6:7:8:9:10 :DEC j, 0DEC k, 1INC 0DEC 0, 6INC jINC kDEC i, 4INC 0DEC 0, 10INC iDEC k, 9При i = j можно взять любую программу, которая ничего не меняет, например0:1:INC 0DEC 0, 2Определение. Макропрограммы P и Q называются эквивалентными, если запуски машин Шёнфилда с этими макропрограммами на одних и тех же начальныхсодержимых регистров либо приведут к остановке обеих машин с одинаковыми содержимыми всех регистров, либо обе машины никогда не остановятся.Следующая теорема показывает, что введение макросов не расширяет класс алгоритмических задач, которые допускают решение на машинах Шёнфилда.
Такимобразом, макросы — это лишь удобный инструмент для сокращения текстов программ.Теорема 15 (об элиминации макросов). Любая макропрограмма эквивалентна программе, не содержащей макросы.Доказательство. Опишем, как следует преобразовать произвольную макропрограмму Q в эквивалентную ей макропрограмму Q0 , содержащую на один макрос меньше,чем в Q.
Повторяя эту процедуру необходимое число раз, мы в конце концов получимпрограмму без макросов, эквивалентную исходной.Пусть P ∗ — некоторый макрос в Q. Чтобы получить искомую макропрограммуQ0 , заменим вхождение P ∗ на список команд P , которые реализуют данный макрос,при этом необходимо проделать следующее:§ 10. Машины Шёнфилда37а) заново перенумеровать все команды полученной макропрограммы, начиная сномера 0;б) если DEC i, n — старая команда из Q или P , n — номер существующей командыC из Q или P соответственно, то заменить ее на DEC i, m, где m — новый номеркоманды C;в) если DEC i, n — старая команда из Q, n — номер несуществующей в Q команды,то заменить ее на DEC i, m, где m больше, чем число команд новой макропрограммы;г) если DEC i, n — старая команда из P , n — номер несуществующей в P команды,то заменить ее на DEC i, m, где m — номер команды, следующей после спискакоманд P в новой макропрограмме.Пример.
Обозначим через ADD [1] TO [0], (3) макрос, при исполнении которого содержимое 1-го регистра прибавляется к содержимому 0-го регистра. При этом содержимое 1-го регистра сохраняется, а 3-й регистр используется как вспомогательный.Программа, реализующая данный макрос, имеет следующий вид:0:1:2:3:4:5:6:7:8:9:DEC 3, 0INC 0DEC 0, 5INC 0INC 3DEC 1, 3INC 0DEC 0, 9INC 1DEC 3, 8Запишем теперь с помощью введенного макроса макропрограмму, перемножающую содержимые 1-го и 2-го регистров и записывающую полученное произведение в0-й регистр:0:1:2:3:4:DEC 0, 0INC 0DEC 0, 4ADD [1] TO [0], (3)DEC 2, 3Если применить к данной макропрограмме процедуру преобразования, описанную в доказательстве теоремы об элиминации макросов, то получим эквивалентнуюей программу без макросов:38Глава III.
Формализации понятия вычислимой функции0:1:2:3:4:5:6:7:8:9:10 :11 :12 :13 :DEC 0, 0INC 0DEC 0, 13DEC 3, 3INC 0DEC 0, 8INC 0INC 3DEC 1, 6INC 0DEC 0, 12INC 1DEC 3, 11DEC 2, 3Определение. k-местная частичная функция f : M ⊆ ω k −→ ω называется вычислимой на машине Шёнфилда, если существует машина Шёнфилда с программой Pтакая, что для любых x1 , . . . , xk ∈ ω выполняется:а) если f (x1 , .
. . , xk ) определено, то после запуска машины с начальными значениями x1 , . . . , xk в регистрах 1, . . . , k соответственно и с нулями в остальныхрегистрах машина после конечного числа шагов останавливается, и после остановки в 0-ом регистре находится f (x1 , . . . , xk );б) если f (x1 , . . . , xk ) не определено, то после запуска машины с начальными значениями x1 , .
. . , xk в регистрах 1, . . . , k соответственно и с нулями в остальныхрегистрах машина никогда не останавливается и работает бесконечно.Замечание. Если в определении выше f — нульместная функция, то входные данные x1 , . . . , xk отсутствуют, а результат вычислений по программе P не зависит отначальных содержимых регистров.Определение. Пусть f — k-местная частичная функция, вычислимая на машинеШёнфилда с программой P .
Обозначим черезf ([i1 ], . . . , [ik ]) → [j], sмакрос, который вычисляет значение функции f от содержимых регистров с номерами i1 , . . . , ik , записывает его в j-й регистр и при этом не изменяет содержимоевсех регистров до s-го включительно, кроме j-го регистра. Если упомянутое значение функции не определено, то исполнение данного макроса приводит к бесконечнойработе программы.Нам необходимо построить макропрограмму, реализующую введенный выше макрос f ([i1 ], . .
. , [ik ]) → [j], s. Обозначим, как обычно, через P ∗ макрос, соответствующий программе P . Пусть m — произвольное число, превосходящее числа i1 , . . . , ik , j, sи номера всех регистров, входящих в программу P . Отсюда, в частности, следует,что результат исполнения макроса P ∗ не зависит от содержимых регистров, номеракоторых больше, чем m−1. Тогда искомая макропрограмма имеет вид (номера строкопущены):§ 11.
Частично рекурсивные функции[0] → [m + 1], (m)···[m − 1] → [m + m], (m)[m + 1 + i1 ] → [1], (m)···[m + 1 + ik ] → [k], (m)ZERO 0ZERO k + 1···ZERO m − 1P∗[m + 2] → [1], (m)···[m + m] → [m − 1], (m)[0] → [j], (m)[m + 1] → [0], (m)39сохраняем содержимое регистров с 0-годо (m − 1)-го в регистрах с номерами отm + 1 до 2mподготавливаем входные данные дляисполнения макроса P ∗вычисляем необходимое значение функции fвосстанавливаем содержимые регистров сномерами от 1 до m − 1заносим результат вычислений в j-й регистресли j 6= 0, то восстанавливаемсодержимое 0-го регистра (если j = 0, тоэта срока не включается в программу!)В дальнейшем мы будем опускать параметр s, поскольку его всегда можно заранеевыбрать достаточно большим, чтобы не влиять на работу внешней макропрограммы.§ 11.Частично рекурсивные функцииВ этом параграфе мы рассмотрим другой подход к формализации понятия вычислимой функции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
