1610906280-c80d8404f2eaa01776b47d41b0f18e85 (824375), страница 12

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 12)

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

Нам предстоит закодировать натуральными числами команды, программы, наборы входных данных, состояния счетчика команд, состояния регистров и,наконец, вычисления на машинах Шёнфилда.Существует много различных способов кодирования объектов натуральными числами. Мы остановимся на способе, в основе которого лежит возможность представления любого положительного числа x ∈ ω в виде x = pa00 · pa11 · . . . · pann (каноническоеразложение).

Прежде всего укажем способ кодирования произвольных конечных последовательностей натуральных чисел.Определение. Кодом последовательности натуральных чисел x0 , . . . , xk−1 назоxk−1 +1, которое будем обозначать черезвем натуральное число px0 0 +1 · px1 1 +1 · . . . · pk−1< x0 , . . . , xk−1 >. Кодом пустой последовательности ∅ будем считать число 1.Замечание. Если x =< x0 , . . . , xk−1 > — код последовательности, то длина этойпоследовательности вычисляется с помощью примитивно рекурсивной функцииlh(x) = µi 6 x[ex(i, x) = 0],а i-ая координата в последовательности, т. е. xi , вычисляется с помощью примитивнорекурсивной функции¦(x)i = ex(i, x)−1.Лемма 27.

Предикат Seq(x), истинный тогда и только тогда, когда x — код последовательности, является примитивно рекурсивным.Доказательство. Произвольное ненулевое число x является кодом последовательности тогда и только тогда, когда в каноническом разложении x на простые множители все простые числа «идут подряд», т. е. если pi входит в разложение с ненулевымпоказателем, то все числа p0 , . . . , pi−1 тоже входят в разложение с ненулевыми показателями. Таким образом, окончательно получаем³´Seq(x) ⇐⇒ (x 6= 0) & ∀i 6 x ex(i, x) 6= 0 −→ ∀j 6 i(ex(j, x) 6= 0) .Предикат, находящийся справа в этой эквивалентности, примитивно рекурсивен.Следовательно, предикат Seq(x) тоже примитивно рекурсивен.Определение.

Определим код команды машины Шёнфилда следующим образом:код(INC i) =< 0, i >код(DEC i, j) =< 1, i, j >Определим код программы, состоящей из команд c0 , . . . , ck−1 , как следующее натуральное число:< код(c0 ), . . . , код(ck−1 ) >§ 13. Кодирование машин Шёнфилда49Лемма 28. Предикат Com(x), истинный тогда и только тогда, когда x — кодкоманды, является примитивно рекурсивным.³´Доказательство. Com(x) ⇐⇒ Seq(x) & ((x)0 =0 & lh(x)=2) ∨ ((x)0 =1 & lh(x)=3) .Последний предикат является примитивно рекурсивным. Следовательно, предикатCom(x) тоже примитивно рекурсивен.Лемма 29.

Предикат Prog(x), истинный тогда и только тогда, когда x — кодпрограммы, является примитивно рекурсивным.Доказательство. Число x является кодом программы тогда и только тогда, когда x— код последовательности натуральных чисел, каждое из которых является кодомкоманды. Следовательно,¡¢Prog(x) ⇐⇒ Seq(x) & ∀i < lh(x) Com((x)i ) .Последний предикат, в силу леммы 27 и леммы 28, является примитивно рекурсивным.Лемма 30 (о совместной рекурсии). Пусть функции f0 (x, y), f1 (x, y) определены посхеме совместной рекурсии:f0 (x, 0) = g0 (x)f (x, 0) = g (x)11f0 (x, y + 1) = h0 (x, y, f0 (x, y), f1 (x, y))f1 (x, y + 1) = h1 (x, y, f0 (x, y), f1 (x, y)).Если функции gi (x), hi (x, y, z0 , z1 ), где i = 0, 1, примитивно рекурсивны, то функцииf0 (x, y), f1 (x, y) тоже примитивно рекурсивны.Доказательство. Закодируем значения функций f0 (x, y) и f1 (x, y) одним числом,определив функциюF (x, y) =< f0 (x, y), f1 (x, y) >= 2f0 (x,y)+1 · 3f1 (x,y)+1 .Если мы докажем, что F (x, y) — п.р.ф., то, очевидно, функции f0 (x, y) = (F (x, y))0 ,f1 (x, y) = (F (x, y))1 тоже будут п.р.ф.Докажем, что F (x, y) — п.р.ф., выписав для нее схему примитивной рекурсии:(F (x, 0) =< g0 (x), g1 (x) >F (x, y + 1) =< h0 (x, y, (F (x, y))0 , (F (x, y))1 ), h1 (x, y, (F (x, y))0 , (F (x, y))1 ) >В этой схеме участвуют только примитивно рекурсивные функции.

Следовательно,F (x, y) — п.р.ф. Что и требовалось доказать.Замечание. Если в формулировке леммы о совместной рекурсии заменить всюдуслова «примитивно рекурсивны» на слова «частично рекурсивны» (или на слова «рекурсивны»), то утверждение по-прежнему будет верным. Однако нам понадобитсятолько случай примитивно рекурсивных функций.50Глава III. Формализации понятия вычислимой функцииТеперь мы введем две важные функции, кодирующие полностью всю информацию о ходе вычисления на машине Шёнфилда. Чтобы целиком охватить поток данных, изменяющихся в ходе такого вычисления, необходимо знать на каждом шагесодержимое счетчика команд и содержимые всех регистров, которые влияют на ходвычислений. Оценим, насколько большим может быть номер регистра, существенновлияющего на ход работы заданной машины Шёнфилда.

Для этого заметим, что длялюбого x ∈ ω справедливо неравенство (x)i < x. Действительно, имеет место цепочканеравенств:ex(i,x)¦6 x.(x)i = ex(i, x)−1 6 ex(i, x) < 2ex(i,x) 6 piОтсюда следует, что если e — код программы, m — номер упомянутого в этой программе регистра, то e больше кода любой команды из этой программы, и тем болееe > m.

Кроме этого, ход вычислений по программе с кодом e зависит от входных данных, которые могут быть записаны в регистрах с 1-го по k-й, где k, вообще говоря,— произвольное натуральное число.Таким образом, можно утверждать, что на ход вычислений по программе с кодомe, начатых с входными данными, записанными в регистрах с 1-го по k-й, могут влиятьтолько регистры, номера которых не превосходят e + k. По крайней мере, регистры сномерами большими, чем e + k, не оказывают никакого влияния на работу машины,а их содержимое остается неизменным.Определение. Определим две 3-местные частичные функции:y, если выполняются следующие условия:(a) e — код некоторой программы P,(б) x =< x1 , . . .

, xk > — код некоторойпоследовательности натуральных чисел,ct(e, x, n) =(в) y — содержимое счетчика команд послеn шагов выполнения программы P, начатой ссодержимыми регистров 0, x1 , . . . , xk , 0, 0, . . . ,0 в противном случае.< r0 , . . . , re+k >, если выполняются следующие условия:(a) e — код некоторой программы P,(б) x =< x1 , . . . , xk > — код некоторойпоследовательности натуральных чисел,(в) ri (0 6 i 6 e + k) — содержимое i-гоrg(e, x, n) =регистра после n шагов выполненияпрограммы P, начатой с содержимымирегистров 0, x1 , . .

. , xk , 0, 0, . . . ,0в противном случае.Функция ct(e, x, n) называется содержимым счетчика команд после n шагов вычислений, а функция rg(e, x, n) называется кодом состояния регистров после n шаговвычислений.§ 13. Кодирование машин Шёнфилда51Лемма 31. Функции ct(e, x, n) и rg(e, x, n) являются примитивно рекурсивными.Доказательство. Достаточно показать, что ct(e, x, n) и rg(e, x, n) получается по схеме совместной рекурсии из некоторых п.р.ф. Совместная рекурсия будет производиться по переменной n, т. е.

по количеству уже выполненных шагов в вычислении,упомянутом в определении выше.При n = 0 очевидно ct(e, x, 0) = 0, а значение rg(e, x, 0) можно вычислить последующей неформальной схеме:< 0, x1 , . . . , xk , 0 . . . , 0 >, если e — код некоторой программы, иx =< x1 , . . . , xk > — код некоторойrg(e, x, 0) =последовательности натуральных чисел,0в противном случае.Определим вспомогательную примитивно рекурсивную функцию:(α(i, x) =¦ex(i−1, x), если 1 6 i 6 lh(x),1иначе.Тогда формальная схема для вычисления rg(e, x, 0) (т. е.

схема, использующая толькопримитивно рекурсивные функции от e и x) имеет вид:e+lh(x) Qrg(e, x, 0) =i=00,α(i,x)pi, если Prog(e) & Seq(x),если ¬Prog(e) ∨ ¬Seq(x).Предположим, что значения ct(e, x, n) и rg(e, x, n) уже вычислены. Обозначимy = ct(e, x, n). Тогда значение ct(e, x, n + 1) можно вычислить с помощью следующейнеформальной схемы:y + 1,j,ct(e, x, n + 1) = y + 1,y,0если Prog(e), Seq(x), и команда сномером ct(e, x, n) имеет вид INC i,если Prog(e), Seq(x), команда сномером ct(e, x, n) имеет вид DEC i, jи содержимое i-го регистра в данный момент > 0,если Prog(e), Seq(x), команда сномером ct(e, x, n) имеет вид DEC i, jи содержимое i-го регистра в данный момент = 0,если Prog(e), Seq(x), и в программенет команды с номером ct(e, x, n),во всех остальных случаях.Теперь перепишем эту схему формально, используя только примитивно рекурсивныефункции, зависящие от e, x, ct(e, x, n) и rg(e, x, n):52Глава III.

Формализации понятия вычислимой функцииct(e, x, n) + 1,³´(e)ct(e,x,n) ,2ct(e, x, n + 1) =ct(e, x, n) + 1,ct(e, x, n),0если³ Prog(e),´Seq(x), ct(e, x, n) < lh(e),и (e)ct(e,x,n) = 0,0если Prog(e), Seq(x), ct(e, x, n) < lh(e),³´´ > 0,(e)ct(e,x,n) = 1 и (rg(e, x, n))³0(e)ct(e,x,n)1еслиProg(e),³´ Seq(x), ct(e, x, n) < lh(e),´ = 0,(e)ct(e,x,n) = 1 и (rg(e, x, n))³0(e)ct(e,x,n)1если Prog(e), Seq(x) и ct(e, x, n) > lh(e),в остальных случаях.В данной схеме если e — код программы, x — код последовательности, то условиеct(e, x, n) < lh(e) равносильно тому, что в указанной программе существует командас номером ct(e, x, n), и в этом случае (e)ct(e,x,n) — это код³ команды,´ исполняемой на(n + 1)-ом шаге.

Характеристики

Список файлов лекций