Egyváltozós rekurzív függvények

Csirmaz László

Az egyváltozós rekurzív függvények egy jellemzését adjuk meg. Az érdekes, és a Church–tézissel — mármint hogy minden egyátalán kiszámítható függvény rekurzív — összevetve különösen meglepő tétel Julia Robinsontól származik. Mivel kizárólag természetes számokon értelmezett függvényekkel foglalkozunk, ezt külön nem fogjuk hangsúlyozni.

A rekurzív függvények sok ekvivalens definíciója közül azt választottuk ki, ami az ELTE egyetemi előadásaiban is szerepel; a bizonyítást kis fáradsággal át lehet alakítani hogy tetszőleges más definícióval is működjön. A használt formális definíciót a bizonyítás során fel fogjuk írni.

A tétel kimondását néhány definícióval készítjük elő. Legyen I az (egyváltozós) indentitásfüggvény, S az, ami minden természetes számhoz annak rákövetkezőjét rendeli, végül E az excess (ráadás) függvény, ami azt mondja meg, hogy argumentuma mennyivel nagyobb az alatta levő legnagyobb négyzetszámnál:

I(a) = a,  S(a) = a + 1,  E(a) = a − [\sqrt{a}]^{2}  minden a ∈ ω-ra.

Tegyük fel, hogy az f : ω → ω függvényre Range(f) = ω. Ekkor beszélhetünk f inverzéről:

f^{−1}(a) = min {b ∈ ω : f(b) = a}.

Legyen S az egyváltozós f : ω → ω függvényeknek az a legszűkebb osztálya, amelyre

(i)az I, S valamint E függvények elemei S-nek;

(ii)ha f és g ∈ S, akkor összegük és kompozíciójuk is S-beli;

(iii)ha f ∈ S értékül minden természetes számot felvesz, akkor f^{−1} ∈ S.

1. Tétel(Julia Robinson tétele) S éppen az egyváltozós rekurzív függvények halmaza.

Bizonyítás. A tételnek az a felét, hogy az S-beli függvények rekurzívak, gyakorlatképpen az olvasóra hagyjuk, csak azt bizonyítjuk, hogy minden egyváltozós rekurzív függvény S-ben van.

A bizonyítás ötlete hogy a többváltozós rekurzív függvényeket egyváltozósakkal “kódoljuk,” és a rekurzív függvények felépítésére vonatkozó indukcióval megmutatjuk, hogy ezek a kódok mind S-beliek. A kódolás definícióját azzal kezdjük, hogy egy sor függvényről megmutatjuk, hogy eleme S-nek.

Először is vegyük észre, hogy ha f ∈ S és k ≥ 1 egész szám, akkor f-et k-szor önmagához adva az adódó k·f függvény ugyancsak S-beli. Ezt az észrevételünket a továbbiakban minden megjegyzés nélkül használjuk.

Mivel az E függvény értékkészlete ω, azért E^{−1} ∈ S, továbbá a ∈ ω-ra

E^{−1}(2a) = a^{2} + 2a és E^{−1}(2a − 1) = a^{2} + 2a − 1.

Az ESE^{−1}(I + I) függvény mint S-beli függvények összege és kompozíciója ugyancsak eleme S-nek és értéke az a ∈ ω helyen

E(1 + E^{−1}(2a)) = E(1 + a^{2} + 2a) = 0.

Így az azonosan nulla függvény is eleme S-nek jelöljük ezt F_{0}-lal. Ekkor S ∘ F_{0} azonosan 1, és általában S^{k} ∘ F_{0} az azonosan k értéket veszi fel, és persze ezek is S-beliek.

Tetszőleges a, b ∈ ω számokra

E^{−1}(2a + 2b) + 3a + b + 4 = (a + b)^{2} + (2a + 2b) + (3a + b + 4) =
= (a + b + 2)^{2} + a − b =
= (a + b + 1)^{2} + 3a + b + 3,

és ez mindig kisebb (a + b + 3)^{2}-nél. Így a ≥ b esetén

E(E^{−1}(2a + 2b) + 3a + b + 4) = a − b.

Az f és g egyváltozós függények “különbségének” nevezzük, és f ⊖ g-vel jelöljük a következő függvényt:

E(E^{−1}(2f + 2g) + 3f + g + 4).

A korábban mondottak alapján az azonosan 4 értéket felvevő függvény eleme S-nek, tehát ha f és g is S-beli, akkor f ⊖ g is az. Ennek a “különbség” függvénynek az értéke az a ∈ ω helyen persze csak akkor lesz az f(a) és g(a) értékek különbsége, ha f(a) ≥ g(a), egyébként valamilyen más értéket vesz fel.

Mivel a^{2} + 2a ≥ 2a minden a ∈ ω-ra, azért az S-beli E^{−1}(I + I) és (I + I) függvények “különbségének” értéke az a helyen a^{2}, s mivel a “különbség” is S-ben van, a négyzetfüggvény eleme S-nek. Innen adódik, hogy S-ben van az alábbi előjel függvény is:

sgn(x) = E(S(x^{2})) = \{ \begin{matrix}0 & ha x = 0, \\ 1 & egyébként. \end{matrix}

Az E^{−1} függvény értékét ismerjük, ebből könnyű látni, hogy

ESSE^{−1}(a) = \{ \begin{matrix}0 & ha a páratlan, \\ 1 & ha a páros. \end{matrix}

Következésképp minden természetes szám előáll 2E(b) + ESSE^{−1}(b) alakban, így ennek a függvénynek inverze ugyancsak S-beli, és

[\frac{x}{2}] = E^{−1}(2E + ESSE^{−1})^{−1} ∈ S.

Ebből már közvetlenül adódik, hogy S zárt a szorzásra: ha f, g ∈ S, akkor

f·g = [\frac{(f + g)^{2} − f^{2} − g^{2}}{2} ] ∈ S.

Legyen a − . b értéke a − b ha a ≥ b, és 0 ha a < b. A korábban definiált I ⊖ 1 ∈ S függvény értéke minden a ≥ 1 helyen a − 1, ám a = 0-ra

0 ⊖ 1 = E(E^{−1}(0 + 2) + 0 + 1 + 4) = E(8) = 4,

ezért x ⊖ 1 és x − . 1 különböző függvények. De (x ⊖ 1)-ből megkaphatjuk (x − . 1)-et, ha az előbbit sgn(x)-szel szorozzuk:

x − . 1 = sgn(x)·(x ⊖ 1),

tehát ez is S-beli. Ha most x ∈ ω négyzetszám, akkor az S-beli

sq(x) = [\frac{E(x − . 1)}{2}] + sgn(x)

függvény értéke éppen x négyzetgyöke, tehát

[\sqrt{x}] = sq(x − E(x)) ∈ S.

A többváltozós függvények kódolásához szükségünk lesz a “rendezett pár” fogalmára. A π “párzó” függvény ω és ω^{2} között egy olyan izomorfizmus, melyre π és mindkét inverze “könnyen” számítható. Ennek a követelménynek megfelel a

π(a, b) = \frac{(a + b)(a + b + 1)}{2} + a

függvény. π ráadásul monoton: ha a ≤ c és b ≤ d, akkor π(a, b) ≤ π(c, d). A korábbiak szerint f, g ∈ S esetén π(f, g) ∈ S is fennáll, hiszen π(f, g)-t f-ből és g-ből összeadással, szorzással és az [x/2] függvénnyel kaphatjuk meg.

Jelölje K azt a függvényt, ami a π(a, b) értékhez a-t, L pedig azt, ami π(a, b)-hez b-t rendeli. Mivel π izomorfizmus ω^{2} és ω között, ez egyértelműen definiálja K-t és L-et. Egy kis számolással adódik, hogy

K(a) = a − [\frac{[\sqrt{8a + 1}]^{2} − 1}{8}], L(a) = [\frac{[\sqrt{8a + 1}] − 1}{2}] − K(a).

Mivel [x/8] = [[[x/2]/2]/2], azért K S-beli függvényekből kompozíció és különbség képzéssel áll elő, tehát maga is S-beli, s természetesen ugyanez áll L-re.

Definiáljuk most n ≥ 1-re az ω^{n} és ω közötti π_{n} izomorfizmust a következőképpen. Legyen π_{1} az identitás, n ≥ 1-re pedig

π_{n+1}(x_{0}, …, x_{n}) = π(π_{n}(x_{0}, …, x_{n−1}), x_{n}).

Így például π_{2} = π és π_{3}(a, b, c) = π(π(a, b), c). Legyen még i < n-re K_{i}^{n} a π_{n}-nek az i-edik koordinátára vonatkozó inverze, azaz minden x ∈ ω-ra

x = π_{n}(K_{0}^{n}(x), …, K_{n−1}^{n}(x)).

Persze K_{0}^{1} az identitás, K_{0}^{2} és K_{1}^{2} pedig a fent definiált K és L függvényekkel esik egybe. n-re vonatkozó indukcióval könnyen adódik, hogy egyrészt f_{0}, …, f_{n−1} ∈ S esetén π_{n}(f_{0}, …, f_{n−1}) ∈ S, másrészt hogy az összes K_{i}^{n} függvény S-beli. Valóban, ez utóbbihoz megjegyezzük, hogy K_{n}^{n+1} = L ∈ S és i < n-re K_{i}^{n+1} = K_{i}^{n} ∘ K.

Most már megadhatjuk a bizonyítás elején igért kódolást. n ≥ 1-re az n-változós f függvény kódja legyen az

F (x) = f(K_{0}^{n}(x), …, K_{n−1}^{n}(x))

egyváltozós függvény. Persze egyváltozós függvény kódja saját maga. A tétel bizonyítandó fele azonnal következik az alábbi állításból.

2. ÁllításMinden rekurzív függvény kódja S-beli.

Ennek bizonyítását természetesen a rekurzív függvények felépítésére vonatkozó indukcióval végezzük a következő definíciót használva.

Definíció A rekurzív függvények R halmaza a természetes számokon értelmezett függvények legszűkebb osztálya, ami teljesíti a következő feltételeket:

(i)A következő függvények elemei R-nek: az összeadás és szorzás (mint kétváltozós függvények), az nváltozós I_{i}^{n}(x_{0}, …, x_{n−1}) = x_{i} projekciófüggvény, végül az alábbi K_{<} függvény:

K_{<}(a, b) = \{ \begin{matrix}0 & ha a < b, \\ 1 & egyébként. \end{matrix}

(ii)R zárt a kompozícióra, azaz ha g ∈ R és i < n-re h_{i} ∈ R, akkor f(x) = g(h_{0}(x), …, h_{n−1}(x)) ∈ R.

(iii)R zárt a μ-operációra, azaz ha az n + 1-változós g(x, u) R-beli és minden x ∈ ω^{n}-hez van olyan u ∈ ω, amivel g(x, u) = 0, akkor μu g(x, u) = 0 =^{def} min {u ∈ ω : g(x, u) = 0} szintén R-beli.

Elsőként az kell látnunk, hogy a 2. állítás igaz az alapfüggvényekre. Az I_{i}^{n} projekciófüggvényekre ez azzal ekvivalens, hogy K_{i}^{n} ∈ S. Az összeadás és szorzás esetén a megfelelő egyváltozós függvények K(x) + L(x) illetve K(x) · L(x). Ezek S-beliek, mivel K, L ∈ S és S zárt az összeadásra és szorzásra. A hiányzó K_{<} esethez vegyük észre, hogy

[\sqrt{E^{−1}(2a + 2b) + 3a + b + 4}] = \{ \begin{matrix}a + b + 2 & ha a ≥ b, \\ a + b + 1 & ha a < b, \end{matrix}

ahogyan azt a függvények “különbségének” definiálásakor láttuk. Ezért

[\sqrt{E^{−1}(2a + 2b) + 3a + b + 4}] − (a + b + 1) = \{ \begin{matrix}0 & ha a < b, \\ 1 & egyébként. \end{matrix}

Itt a, b helyébe K(x)-et, L(x)-et írva éppen a K_{<}(K(x), L(x)) függvényt állítottuk elő.

Másodjára azt kell látnunk, hogy ha a 2. állítás teljesül az m-változós g-re és i < m esetén az n-változós h_{i}-re, akkor ez a belőlük helyettesítéssel kapható n-változós

f(x) =^{def} g(h_{0}(x), …, h_{m−1}(x))

függvényre is áll. Jelöljük a függvényekhez tartozó egyváltozós kódokat a megfelelő nagybetűvel. Az indukciós feltevés folytán G és i < m-re H_{i} is S-beli, és ekkor

F (x) = f(K_{0}^{n}(x), …, K_{n−1}^{n}(x)) = g(H_{0}(x), …, H_{m−1}(x)) = G (π_{m} (H_{0}(x), …, H_{m−1}(x)))

valóban S-beli a π_{m}-ről tett korábbi megállapításunk alapján.

Végül legyen g : ω^{n+1} → ω olyan függvény, hogy minden x ∈ ω^{n}-hez van u ∈ ω, amivel g(x, u) = 0. Legyen még G a g-nek, F pedig az f(x) =^{def} μu g(x, u) = 0 függvénynek kódja. Ha x = π_{n}(x_{0}, …, x_{n−1}), akkor a g-re tett kikötésünk éppen azt jelenti, hogy van u ∈ ω, amivel G(π(x, u)) = 0. A π_{n} bijekció ω^{n} és ω között, ezért minden x ∈ ω-hoz található u ∈ ω, hogy G(π(x, u)) = 0, és persze

F (x) = μu G(π(x, u)) = 0.

Így a 2. állításhoz azt kell belátnunk, hogy G ∈ S esetén F ∈ S. Ehhez nézzük az ⟨x, G(π(x, u))⟩ alakú párokat, amint x és u egymástól függetlenül átfut ω elemein. A párok között az összes olyan előfordul, ahol a második tag 0, így az y = π(x, u) jelöléssel a H(y) =^{def} π(K(y), G(y)) függvény értékkészlete tartalmazza az összes π(x, 0) alakú számot. Mivel π még monoton is, azért rögzített x ∈ ω-ra a π(x, u) értékek közül a minimális olyan, amire G(π(x, u)) = 0 teljesül, megegyezik a

π(x, min {u ∈ ω : G(π(x, u)) = 0}) = π(x, F (x))

értékkel. Következésképp

min {y ∈ ω : H(y) = π(x, 0)} = min {π(x, u) : u ∈ ω és G(π(x, u)) = 0} = π(x, F (x)),

tehát

F (x) = K(π(x, F (x))) = KH^{−1}(π(x, 0)).

Tudjuk, hogy H S-beli, azért ennek alapján F is S-beli volna, ha tudnánk, hogy H^{−1} ∈ S. Ennek feltétele, hogy H értékkészlete az összes számot tartalmazza. Ez azonban nem feltétlenül van így, mindössze azt tudjuk garantálni, hogy a π(x, 0) alakú számok elemei Range(H)-nak. Ezért legyen

H′(π(y, z)) =^{def} \{ \begin{matrix}H(y) & ha z = 0, \\ π(y, z) & egyébként. \end{matrix}

A π bijekció ω^{2} és ω között, tehát ez egyértelműen definiálja a H′ függvényt, ráadásul Range(H′) = ω. A H′ a π(x, 0) értéket csak úgy veheti fel, ha argumentuma π(y, 0) alakú és még H(y) = π(x, 0). Vagyis H^{′−1}(π(x, 0)) = π(y, 0) és y = H^{−1}(π(x, 0)). Tehát H^{−1}(π(x, 0)) = KH^{′−1}(π(x, 0)), ezért

F (x) = KH^{−1}(π(x, 0)) = KKH^{′−1}(π(x, 0)).

Így annak bizonyítására, hogy F ∈ S elég látni, hogy H′ ∈ S. Ez pedig például H′-nek az alábbi felírásából következik:

H′(x) = x· sgn(L(x)) + (1 − sgn(L(x)))·H(K(x)).

Ezzel a 2. állítást és így Julia Robinson tételét is igazoltuk.