Parciálisan rekurzív függvény

A parciálisan rekurzív függvények definíciója a bizonyításelmélet (matematikai logika), illetve a komplexitáselmélet egyik fontos fogalma. Bizonyos, a természetes számokból ugyanoda képező, egy- vagy többváltozós függvényekről van szó. Megengedjük, hogy egy függvény egyes helyeken ne legyen definiálva, azaz parciális függvény legyen.

Alapfüggvények

Alapfüggvényeknek nevezzük a következő függvényeket.

  • 0(x)=0, az azonosan nulla függvény.
  • S(x)=x+1, a rákövetkezés-függvény.
  • I m n ( x 1 , … , x n ) = x m {\displaystyle I_{m}^{n}(x_{1},\dots ,x_{n})=x_{m}} minden 1 ≤ m ≤ n {\displaystyle 1\leq m\leq n} értékre.

Operációk

  • (Kompozíció) A g ( x 1 , … , x m ) {\displaystyle g(x_{1},\dots ,x_{m})} , h 1 ( x 1 , … , x n ) , … , h m ( x 1 , … , x n ) {\displaystyle h_{1}(x_{1},\dots ,x_{n}),\dots ,h_{m}(x_{1},\dots ,x_{n})} parciális függvények kompozíciója az
f ( x 1 , … , x n ) = g ( h 1 ( x 1 , … , x n ) , … , h m ( x 1 , … , x n ) ) {\displaystyle f(x_{1},\dots ,x_{n})=g\left(h_{1}(x_{1},\dots ,x_{n}),\dots ,h_{m}(x_{1},\dots ,x_{n})\right)}

parciális függvény.

  • (Primitív rekurzió) Az f ( x 1 , … , x n , y ) {\displaystyle f(x_{1},\dots ,x_{n},y)} parciális függvény primitív rekurzióval keletkezik a g ( x 1 , … , x n ) {\displaystyle g(x_{1},\dots ,x_{n})} , h ( x 1 , … , x n , y , z ) {\displaystyle h(x_{1},\dots ,x_{n},y,z)} parciális függvényekből, ha a következők teljesülnek:
f ( x 1 , … , x n , 0 ) = g ( x 1 , … , x n ) {\displaystyle f(x_{1},\dots ,x_{n},0)=g(x_{1},\dots ,x_{n})} ,
f ( x 1 , … , x n , y + 1 ) = h ( x 1 , … , x n , y , f ( x 1 , … , x n , y ) ) {\displaystyle f(x_{1},\dots ,x_{n},y+1)=h\left(x_{1},\dots ,x_{n},y,f(x_{1},\dots ,x_{n},y)\right)}
  • (Minimalizáció, μ-operáció) Az f ( x 1 , … , x n ) {\displaystyle f(x_{1},\dots ,x_{n})} parciális függvény minimalizációval keletkezik a g ( x 1 , … , x n , y ) {\displaystyle g(x_{1},\dots ,x_{n},y)} parciális függvényből, ha
f ( x 1 , … , x n ) = μ y [ g ( x 1 , … , x n , y ) = 0 ] , {\displaystyle f(x_{1},\dots ,x_{n})=\mu y[g(x_{1},\dots ,x_{n},y)=0],}

azaz f ( x 1 , … , x n ) {\displaystyle f(x_{1},\dots ,x_{n})} a legkisebb olyan y érték amire g ( x 1 , … , x n , y ) = 0 {\displaystyle g(x_{1},\dots ,x_{n},y)=0} teljesül. Ez pontosan úgy értendő, hogy f ( x 1 , … , x n ) {\displaystyle f(x_{1},\dots ,x_{n})} az egyetlen olyan y, amire

g ( x 1 , … , x n , 0 ) , … , g ( x 1 , … , x n , y ) {\displaystyle g(x_{1},\dots ,x_{n},0),\dots ,g(x_{1},\dots ,x_{n},y)}

mind értelmezett és csak a legutolsó értéke 0, ha ilyen y van, ha pedig nincs ilyen y, akkor f ( x 1 , … , x n ) {\displaystyle f(x_{1},\dots ,x_{n})} nem értelmezett.

Parciálisan rekurzív függvények

Parciálisan rekurzív függvényeknek nevezzük azokat a (természetes számokból ugyanoda képező, egy- vagy többváltozós) parciális függvényeket, amelyek az alapfüggvényekből az operációk véges sok alkalmazásával megkaphatók. Ugyanazokat a parciális függvényeket kapjuk, ha az operációk közül kihagyjuk a primitív rekurziót.

Church–Turing-tézis

A Church-Turing-tézis, vagy Church-tézis az az állítás, hogy a parciálisan rekurzív függvények pontosan az (algoritmussal) kiszámítható függvények. Ez matematikailag ellenőrizhető állítássá válik, ha az algoritmussal kiszámíthatóság homályos fogalma helyett bármilyen más matematikailag precízen megadott függvényosztályt vizsgálunk, így igazolható például, hogy a parciálisan rekurzív és a Turing-géppel kiszámítható függvények egybeesnek.

Rekurzív függvények

Ha egy f ( x 1 , … , x n ) {\displaystyle f(x_{1},\dots ,x_{n})} parciálisan rekurzív függvény totális, azaz mindenütt értelmezett, akkor rekurzív függvénynek nevezzük.

Univerzális parciálisan rekurzív függvény

Van univerzális parciálisan rekurzív függvény. Ezen azt értjük, hogy van olyan kétváltozós ϕ ( x , y ) {\displaystyle \phi (x,y)} parciális függvény, ami maga parciálisan rekurzív és minden f ( y ) {\displaystyle f(y)} egyváltozós parciálisan rekurzív függvényhez van olyan e természetes szám, hogy minden y-ra f ( y ) = ϕ ( e , y ) {\displaystyle f(y)=\phi (e,y)} teljesül (úgy értve, hogy vagy mindkét oldal létezik és egyenlő, vagy egyik sem létezik).

Lásd még

  • primitív rekurzív függvények
  • rekurzív halmaz
  • rekurzívan felsorolható halmaz

További információk

  • Alice és Bob - 6. rész: Alice és Bob a kiszámíthatóság határán
  • Alice és Bob - 7. rész: Alice és Bob egymillió dolláros kérdése
  • Alice és Bob - 8. rész: Alice és Bob biztonsága