From Wikipedia, the free encyclopedia
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ényeknek nevezzük a következő függvényeket.
parciális függvény.
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é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.
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.
Ha egy parciálisan rekurzív függvény totális, azaz mindenütt értelmezett, akkor rekurzív függvénynek nevezzük.
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).
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.