Kissé felületes voltam, mert az írásom hibákat tartalmaz, de lehet javítani.
Elnézést, de amit írtam viszonylag bonyolult.
Másrészt igazolni szeretnék egy alapvető tételt.
--------------------------
Pontosítás: természetesen, a nyelv szavai rekurzív nyelv (Kleene's *)
Ezt úgy kell érteni, hogy adott véges abc-ből képzett nyelv szavai természetesen rekurzív nyelvet alkotnak. Ez a Kleene's star. (Ez a nyelv is szétesik persze eldönthetetlenekre, gondoljunk a Peano-ban eldönthető, és eldönthetetlen aritmetikai formulákra).
Mi ennek az oka? Ha van egy W véges szavunk, a {0,1} abc-ből (ez az általánosságot nem szorítja meg), akkor olyan W* szóhóz is van véges ág, amely sokkal hosszabb, mint W, de W* non-computable W-ből.
Ez egy hibás állítás, át kell fogalmazni.
W* nem lehet non-computable W-ből, hiszen véges sok szó van közöttük. Csak végtelen ág lehet az.
ZFC valamely rekurzív, konzisztens, bővített axiómarendszerében biztosan el lehet dönteni, ha egy adott nyelv L, akkor egy W szó benne van-e, HA nincs benne? W* feltétel szerint benne van L-ben, W-hez pedig rekurzív ágak végtelen(!) sokasága vezet a gráfban. Ugyanakkor az L nyelvet is egy f rekurzív függvény generálja.
Mármost azt kellene igazolni, hogy nincs olyan véges ág, amely f szerinti szavakon keresztül W-t generálja W*-ből. (Ha van ilyen f, akkor f értékkészletének "dummy" generálása választ ad. Gond akkor van, ha nincs.)
f értékkészletének komplementere nem-felsorolható, nem generálja grammatika, így a feladat nagyon nehéz - másrészt csak egyetlen szóról van szó.
Azt kellene tudnunk, hogy a W*|-W ágak végtelen sokaságából egy benne van-e az L nyelvben, azaz f értékkészletében (ha egyébként nincs benne).
A válasz: igen, azaz (sajnos, nem biztos, hogy igaz) választ kaphatunk a kérdésre.
Bizonyítás. Azok a rekurzív függvények, amelyek értékkészletének komplementere nem felsorolható, reprezentálhatók ZFC-ben. Vegyük ZFC egy konzisztens, teljes bővítését: ilyen a Lindenbaum-tétel értelmében (AC-vel, tehát nemkonstruktívan, de) lehetséges.
Legyen ez a Gamma elmélet! Vizsgáljuk meg, hogy Gamma milyen függvényeket képes reprezentálni! Világos, hogy nemcsak rekurzívakat, hiszen önmaga nem az. Például tudja reprezentálni egy ZFC-modellen igaz formulák Gödel számainak halmazát (ami persze nem-felsorolható), ugyanis ha Ax egy ZFC-t tartalmazó, rekurzív része Gammának, akkor van P{Ax} bizonyíthatóság-predikátuma, amely generálja a tételeket. Vehetjük ezeknek a predikátumoknak egy egyre erősebb sorozatát, így definiálva, reprezentált nem-rekurzív függvényt.
Ha most f tetszőleges rekurzív (Gamma szerint), RfC nem-felsorolható, utóbbit Gamma tudni fogja reprezentálni, mert az a degree, amelyen az előbbi, ZFC-modellben igaz tételek Gödel-számai vannak, magasabban degree-n van, mint a Gamma szerint rekurzív függvények értékkészletének komplementerei közöl bármelyik.
Ez azért van így, mert a mondott M ZFC-modellbeli igaz állítások komplementer-nyelve szintén nem felsorolható, és ezért M igazsághalmaza bonyolultabb, mint tetszőleges olyan nyelv, amely komplementere felsorolható (ez Post tétele alapján könnyen belátható).
Vagyis az összes többi RfC pedig vagy ott, vagy alatta lévő degree-n lesz - vagyis "effektíven" kiszámítható az M modell igazsághalmazának (orákulum!) ismeretében, ahogyan ezt a degree-hierarchiából tudjuk.
Mivel Gamma teljes, adott RfC esetén "tudni" is fogjuk, hogy mi a jó rekurzív átszámolás, mert ha F ilyen (tehát M elméletét átszámolja RfC-vé), akkor az erről szóló formulát a teljes Gamma definíció szerint eldönti.
Következmény. Ha Gamma eldönti f értékkészletének komplementerét, akkor, mivel minden igazolás véges, Gamma egy véges részéből is eldönthetjük a rekurzív f értékkészletének véges sok elemét.
Felhívom a figyelmet, hogy a tétel Chaitin tételének nagymértékű élesítése.
Q.E.D.
---------------------------------------------
Ha a nyelv komplementerében van non-computable ág-részhalmaz a szó-fában, hosszú W* szavakkal, akkor a nyelv nem lehet rekurzív
Csak egy kis javítás:
"Ha a nyelv komplementere non-computable ág-részhalmaz a szó-fában, hosszú W* szavakkal, akkor a nyelv nem lehet rekurzív"
Nyilván, nemrekurzív ág-részhalmaz lehet része rekurzívnak, ahogyan nemrekurzív nyelv rekurzívnak.
