1610906280-c80d8404f2eaa01776b47d41b0f18e85 (824375), страница 11
Текст из файла (страница 11)
а) Для функции f (x, y) = x + y имеет место следующая схемапримитивной рекурсии:(f (x, 0) = x,f (x, y + 1) = (x + y) + 1 = s(f (x, y)) = s(I33 (x, y, f (x, y))),т. е. f (x, y) получена с помощью оператора R из п.р.ф. g(x) = x = I11 (x) и п.р.ф.h(x, y, z) = s(I33 (x, y, z)), которая, в свою очередь, получена из простейших функцийs и I33 с помощью оператора S.б) Для функции f (x, y) = x · y имеет место следующая схема примитивной рекурсии:(f (x, 0) = 0,f (x, y + 1) = xy + x = ϕ(xy, x) = ϕ(I33 (x, y, f (x, y)), I13 (x, y, f (x, y))),где ϕ(u, v) = u + v — п.р.ф.
из предыдущего пункта, т. е. f (x, y) получена с помощьюоператора R из п.р.ф. g(x) = 0 = o(x) и п.р.ф. h(x, y, z)=ϕ(I33 (x, y, z), I13 (x, y, z)),которая, в свою очередь, получена из п.р.ф. ϕ, I33 , I13 с помощью оператора S.в) Доказывается аналогично путем выписывания соответствующей схемы примитивной рекурсии.г) Выписываем схему примитивной рекурсии:(sg(0) = 0,sg(x + 1) = 1 = s(0) = s(o(I12 (x, sg(x)))).Другими словами, sg(x) получена с помощью оператора R из 0-местной функции 0,которая является простейшей, и 2-местной функции s(o(I12 (x, y))), которая являетсяп.р.ф., поскольку получена суперпозициями из простейших.д) Выписываем схему примитивной рекурсии:(sg(0) = 1,sg(x + 1) = 0 = o(I12 (x, sg(x))).Таким образом, sg(x) получена с помощью оператора R из 0-местной функции 1,которая является п.р.ф.
в силу предыдущей леммы, и 2-местной функции o(I12 (x, y)),которая является п.р.ф., так как получена суперпозициями из простейших функций.44Глава III. Формализации понятия вычислимой функциие) Доказывается аналогично.¦ж) Обозначим f (x, y) = x−y. Тогда имеет место схема примитивной рекурсии:(f (x, 0) = x = I11 (x),¦¦¦f (x, y + 1) = x−(y + 1) = (x−y)−1 = ψ(f (x, y)),¦где ψ(u) = u−1 — п.р.ф. из предыдущего пункта.
Выше мы воспользовались тожд妦¦ством x−(y + 1) = (x−y)−1, которое верно для любых x, y ∈ ω.¦¦з) Заметим, что |x − y| = (x−y) + (y−x) — суперпозиция примитивно рекурсивныхфункций.Лемма 19. Если функция g(x, y) является ч.р.ф. (п.р.ф.), то функции f (x, y) =yyPQg(x, i) и h(x, y) =g(x, i) тоже являются ч.р.ф. (п.р.ф.).i=0i=0Доказательство. Частичная (примитивная) рекурсивность функции f вытекает изпункта (а) леммы 18 и следующей схемы примитивной рекурсии:(f (x, 0) = g(x, 0),f (x, y + 1) = f (x, y) + g(x, y + 1).Утверждение для функции h доказывается аналогично с использованием пункта (б)леммы 18.Определение. Говорят, что функция f (x) получается с помощью ограниченной минимизации из всюду определенных функций g(x, y) и h(x), и обозначается f (x) =µy 6 h(x)[g(x, y) = 0], если для любых значений x выполняется:(y,если g(x, i) 6= 0 для всех i < y, и g(x, y) = 0, и y 6 h(x),f (x) =h(x) + 1, в противном случае.Предложение 20 (об ограниченной минимизации).
Если функции g и h примитивно рекурсивны и функция f получена из g и h с помощью ограниченной минимизации, то f тоже примитивно рекурсивна.Доказательство. Следует из лемм 18, 19 и тождества f (x) =h(x)Pi=0sg³Qi´g(x, j) .j=0Распространим понятие рекурсивности на класс всех отношений, заданных на ω.Для этого достаточно связать с каждым отношением некоторую частичную функцию, которая однозначно его задает, и назвать отношение рекурсивным, если таковойявляется данная функция.Определение. Отношение (предикат) R ⊆ ω n называется рекурсивным (примитивно рекурсивным), если его характеристическая функция(1, если hx1 , . .
. , xn i ∈ R,XR (x1 , . . . , xn ) =0, если hx1 , . . . , xn i ∈/Rявляется рекурсивной (примитивно рекурсивной).§ 12. Рекурсивность некоторых функций и отношений45Напомним, что вместо hx1 , . . . , xn i ∈ R иногда пишут R(x1 , . . . , xn ) и говорят, чтопредикат R истиннен на элементах x1 , . . . , xn . Если же hx1 , . . . , xn i ∈/ R, то пишут¬R(x1 , .
. . , xn ) и говорят, что предикат R ложен на элементах x1 , . . . , xn .Определение. Для P, Q ⊆ ω n введем следующие обозначения для n-местных отношений:P &Q = {x ∈ ω n | P (x) истинно, и Q(x) истинно},P ∨ Q = {x ∈ ω n | P (x) истинно, или Q(x) истинно},P → Q = {x ∈ ω n | если P (x) истинно, то Q(x) истинно},¬P = {x ∈ ω n | P (x) ложно}.Кроме этого, для R ⊆ ω n+1 введем следующие обозначения для (n + 1)-местныхотношений:∃i 6 y R(x, i) = {hx, yi ∈ ω n+1∀i 6 y R(x, i) = {hx, yi ∈ ω n+1∃i < y R(x, i) = {hx, yi ∈ ω n+1∀i < y R(x, i) = {hx, yi ∈ ω n+1||||существует i 6 y такой, что R(x, i) истинно},для всех i 6 y отношение R(x, i) истинно},существует i < y такой, что R(x, i) истинно},для всех i < y отношение R(x, i) истинно}.Замечание. С теоретико-множественной точки зрения отношение P &Q совпадает спересечением P ∩ Q, отношение P ∨ Q совпадает с объединением P ∪ Q, а отношение¬P совпадает с дополнением ω n \ P .
Кроме этого, имеет место тождество P → Q =¬P ∨ Q.Предложение 21. Если отношения P (x) и Q(x) рекурсивны (примитивно рекурсивны), то отношения P (x)&Q(x), P (x) ∨ Q(x), ¬P (x), P (x) → Q(x) тоже рекурсивны (примитивно рекурсивны).Доказательство. Следует из леммы 18 и следующих тождеств:XP &Q (x) = XP (x) · XQ (x),XP ∨Q (x) = sg(XP (x) + XQ (x)),X¬P (x) = sg(XP (x)),XP →Q (x) = X¬P ∨Q (x) = sg(sg(XP (x)) + XQ (x)).Предложение 22. Бинарные отношения =, 6=, <, >, 6, > являются примитивнорекурсивными.Доказательство.
Примитивная рекурсивность данных отношений следует из леммы18 и тождествX= (x, y) = sg|x − y|,¦X< (x, y) = sg(y−x),¦X6 (x, y) = sg(x−y),X6= (x, y) = sg|x − y|,¦X> (x, y) = sg(x−y),¦X> (x, y) = sg(y−x).Предложение 23. Если отношение R(x, i) рекурсивно (примитивно рекурсивно),то отношения ∃i 6 y R(x, i), ∀i 6 y R(x, i), ∃i < y R(x, i), ∀i < y R(x, i) тожерекурсивны (примитивно рекурсивны).46Глава III.
Формализации понятия вычислимой функцииДоказательство. Утверждение для отношения P (x, y) = ∃i 6 y R(x, i) следует излеммы 19 и тождестваy³X´XP (x, y) = sgXR (x, i) .i=0Утверждение для остальных отношений вытекает из предложений 21, 22 и эквивалентностей∀i 6 y R(x, i) ⇐⇒ ¬∃i 6 y ¬R(x, i),∃i < y R(x, i) ⇐⇒ ∃i 6 y(R(x, i) & i 6= y),∀i < y R(x, i) ⇐⇒ ¬∃i < y ¬R(x, i).Предложение 24 (о кусочном задании функции). Пусть R0 , . .
. , Rk ⊆ ω n — рекурсивные (примитивно рекурсивные) отношения, такие, что R0 ∪ . . . ∪ Rk = ω n иRi ∩ Rj = ∅ при i 6= j. Пусть далее f0 (x1 , . . . , xn ), . . . , fk (x1 , . . . , xn ) — рекурсивные(примитивно рекурсивные) функции. Тогда функцияf0 (x), если R0 (x),F (x) = · · ····fk (x), если Rk (x)тоже рекурсивна (примитивно рекурсивна).Доказательство.
Достаточно заметить, что F (x) = f0 (x)·XR0 (x)+. . .+fk (x)·XRk (x).Определение. Пусть R(x, y) — отношение, h(x) — всюду определенная функция.Обозначим через µy[R(x, y)] функцию µy[|XR (x, y)−1| = 0], а через µy 6 h(x)[R(x, y)]обозначим функцию µy 6 h(x)[|XR (x, y) − 1| = 0]. Ясно, что если R(x, y) рекурсивно,то µy[R(x, y)] — ч.р.ф. Кроме этого, из предложения 20 следует, что если R(x, y) иh(x) примитивно рекурсивны, то µy 6 h(x)[R(x, y)] — п.р.ф.Лемма 25.
а) Функция [ xy ], равная целой части от частного xy , примитивно рекурсивна (по определению считаем, что [ x0 ] = x).б) Отношение Div(x, y), истинное тогда и только тогда, когда x делит y, примитивно рекурсивно.в) Отношение Prime(x), истинное тогда и только тогда, когда x — простоечисло, примитивно рекурсивно.Доказательство. Докажем утверждение пункта (а). Имеет место цепочка эквивалентностей [x/y] = z ⇐⇒ (y = 0 & x = z) ∨ (y 6= 0 & z 6 x/y < z + 1) ⇐⇒(y = 0 & x = z) ∨ (y 6= 0 & zy 6 x < (z + 1)y) ⇐⇒ (y = 0 & x = z) ∨ (y 6=0 & z – наименьшее, такое, что x < (z + 1)y).
Кроме этого, ясно, что [x/y] 6 x. Отсюда получаем:hi[x/y] = µz 6 x (y = 0 & x = z) ∨ (y 6= 0 & x < (z + 1)y) .§ 12. Рекурсивность некоторых функций и отношений47Таким образом, функция [x/y] получена ограниченной минимизацией из примитивнорекурсивных функций, а значит, является п.р.ф.Утверждения пунктов (б) и (в) следуют из эквивалентностей:Div(x, y) ⇐⇒ ∃z 6 y(xz = y)³´Prime(x) ⇐⇒ (x > 2) & ∀y 6 x Div(y, x) −→ (y = 1 ∨ y = x) .Лемма 26. а) Функция f (x) = px , где p0 = 2, p1 = 3, p2 = 5, . . .
— перечислениевсех простых чисел в порядке возрастания, является примитивно рекурсивной.б) Функция ex(i, x), равная показателю степени pi в каноническом разложениичисла x на простые множители, является примитивно рекурсивной (здесьex(i, 0) = 0).nДоказательство. а) Сначала индукцией по n ∈ ω докажем, что pn 6 22 . Действиiтельно, пусть для всех i 6 n уже доказано, что pi 6 22 . Тогда имеет место цепочканеравенств01nnp0 p1 . . .
pn + 1 6 22 · 22 · . . . · 22 + 1 = 21+2+...+2 + 1 =n+1 −1= 22n+1 −1+ 1 6 22n+1 −1+ 22n+1= 22.n+1Таким образом, число N = p0 p1 . . . pn +1 не превосходит 22и, очевидно, не делитсяна простые числа p0 , p1 , . . . , pn . Следовательно, N должно делиться на некотороеn+1простое число pk для k > n + 1. Но тогда, очевидно, pn+1 6 pk 6 N 6 22 . Что итребовалось доказать.Отсюда следует, что функцию f (x) = px можно получить по схеме примитивнойрекурсии(p0 = 2,¤x+1 £px+1 = µy 6 22Prime(y) & y > px .¤x+1 £Так как участвующие в схеме функции g = 2 и h(x, z) = µy 6 22Prime(y) & y > zпримитивно рекурсивны, то f (x) является п.р.ф.б) Функция ex(i, x) получается с помощью ограниченной минимизацииex(i, x) = µy 6 x[¬Div(py+1, x) ∨ x = 0].iЗамечание.
В доказательстве пункта (а) предыдущей леммы было использованоxнеравенство px 6 22 . Используя теорему Чебышева, утверждающую, что для любогоn > 1 среди чисел n + 1, n + 2, . . . , 2n найдется хотя бы одно простое, можно доказатьболее точную оценку px 6 2x+1 . Однако для нас точность оценки не имеет никакогозначения. Достаточно было найти любую п.р.ф. ϕ(x) со свойством px 6 ϕ(x).48§ 13.Глава III. Формализации понятия вычислимой функцииКодирование машин ШёнфилдаМы постепенно приближаемся к доказательству теоремы о том, что любая функция, вычислимая на машине Шёнфилда, является частично рекурсивной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
