Matematikai Lapok, 1993 (Új sorozat 3. évfolyam, 1-2. szám)

1993 / 1-2. szám

? Lobbit HILBERT TIZEDIK PROBLÉMÁJA CSIRMAZ LÁSZLÓ David Hilbert a századforulón a párizsi Nemzetközi Matematikai Kongresszuson 23 problémát sorolt fel, melyek megoldását az eljövendő századtól várta. Ezek közül a tizedik a következő volt: adjunk meg olyan eljárást (algoritmust), amely minden egész együtthatós (többváltozós) polinomról eldönti, van-e a polinomnak nem-negatív egészekből álló gyökrendszere. Ebben a jegyzetben azt mutatjuk meg, hogy Hilbert várakozásával ellentétben ilyen algoritmus nem létezik. Tekintsünk egy n­e­m-változós, egész együtthatós p(x,y) polinomot. Az x változókat paramétereknek tekintjük, és ezek rögzítése után megnézzük, hogy a polinomnak az x változókban van-e nem-negatív egészekből álló megoldása. Álljon Rp pontosan azokból az x paraméterekből, melyekre ilyen megoldás létezik. Ezzel Rz egy természetes számok m­eséiből álló halmaz, vagyis egy reláció lesz. Az ilyen típusú relációkat diphantikus relációknak nevezzük, s ezek vizsgálata vezetett végül is a fenti eredményhez. Egy természetes számokon értelmezett és természetes számot felvevő függvény rekurzív, ha kiszámítható, azaz ha létezik olyan Turing-gép, ami minden inputra megáll és éppen a függvény értékét számítja ki. A rekurzív függvények sok más ekvivalens definíciója közül mi a következőt fogjuk használni. Definíció. Rekurzív függvények az un­i► uim függvények legszűkebb részosztálya, mely egyrészt tartalmazza a következő függvényeket: másrészt zárt a kompozícióra és a p-operációra, azaz ha f(x, y) egy (n + l)-változós rekurzív függvény úgy hogy minden z-hez van olyan , amivel f(x, y) — 0, akkor f(x,y) f(x,y) = x + y f(x, y) = x ■ · f{x 1, • • •, xn ) — fi ha x · y, \ 0 egyébként összeadás szorzás projekciófüggvények a­l karakterisztikus függvénye g(x) = pu(f(x,u) =n\ def • 0) = mm{n 6 w /(*,y)= 0} 1

Next