Matematikai Lapok, 1993 (Új sorozat 3. évfolyam, 1-2. szám)
1993 / 1-2. szám
szintén rekurzív. Csakúgy mint itt, a későbbiekben is ш jelöli a természetes számok halmazát. Egy w'-en értelmezett R reláció rekurzív, ha karakterisztikus függvénye, azaz Xr(x) = 1 ha x ^ R és xr(x) = 0 ha x ^ R, rekurzív. R rekurzívan felsorolható, ha R éppen egy rekurzív függvény értékkészlete. Megjegyezzük, hogy minden rekurzív reláció egyúttal rekurzívan felsorolható is, de fordítva nem: van-nak rekurzívan felsorolható, de nem rekurzív részhalmaza. Egy függvény parciálisan rekurzív, ha értelmezési tartománya van valamely részhalmaza, és előáll egy rekurzív függvényből a /r-operáció alkalmazásával, ahol is nem követeljük meg, hogy minden x inputra létezzen megfelelő érték. A nevezetes Church-tézis azt mondja ki, hogy minden (elvben) kiszámítható függvény rekurzív. A tézis számos következménye közül az egyik legnevezetesebb, hogy nincs algoritmus (vagyis kiszámítási eljárás), ami minden Turing-gépre megmondaná, hogy az véges sok lépésen belül megáll-e vagy sem (megállási probléma). Visszatérve Hilbert 10. problémájához, az 50-es évek elejére Julia Robinson bizonyította, hogy amennyiben az f(n, t) i nk kétváltozós függvény diophantikus, akkor minden rekurzív függvény is az. Ebből viszont már következik, hogy a Hibert által keresett algoritmus nem létezik , amit úgy szokás kifejezni, hogy Hilbert tizedik problémája megoldhatatlan (lásd 7. Következmény). Annak igazolása, hogy nk valóban diophantikus, további 20 évet váratott magára, ez J. Matijasevics tétele. A bizonyításhoz elsőként néhány definíciót vezetünk be, majd pár egyszerű állítást igazolunk. Definíció. Az R C w” reláció diophantikus, ha van olyan n + m-változós egész együtthatós p(x,J) polinom, hogy minden xi,...,x„ nem-negatív egész számra x = (xi,... ,xn) . R akkor és csak akkor, ha vannak olyan nem-negatív egész zi,..., zm számok, hogy p(x, z) = 0. Definíció. Az függvény diophantikus, ha az ((x, y) Gwn+1 : f(x) = y} reláció diophantikus. 1. Állítás. Az —, ф, ·, · diophantikus relációk, a +, -, id diophantikus függvények. Bizonyítás. Az alábbi átírások alkalmazásával: X = yо x — у = 0 (3z >0)z-|-z — у = 0 хфу <£► (Зл > 0)(z - у)2 - 1 - л = X < уо (Зл >0)г + л + 1 — у = 0 X + y - Zх + у - л = 0 xy - zо н 1к» II О X < у 2