Főmenü megnyitása

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.

Tartalomjegyzék

AlapfüggvényekSzerkesztés

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.
  •   minden   értékre.

OperációkSzerkesztés

  • (Kompozíció) A  ,   parciális függvények kompozíciója az
 

parciális függvény.

  • (Primitív rekurzió) Az   parciális függvény primitív rekurzióval keletkezik a  ,   parciális függvényekből, ha a következők teljesülnek:
 ,
 
  • (Minimalizáció, μ-operáció) Az   parciális függvény minimalizációval keletkezik a   parciális függvényből, ha
 

azaz   a legkisebb olyan y érték amire   teljesül. Ez pontosan úgy értendő, hogy   az egyetlen olyan y, amire

 

mind értelmezett és csak a legutolsó értéke 0, ha ilyen y van, ha pedig nincs ilyen y, akkor   nem értelmezett.

Parciálisan rekurzív függvényekSzerkesztés

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ézisSzerkesztés

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ényekSzerkesztés

Ha egy   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énySzerkesztés

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

Lásd mégSzerkesztés