Keresés

Részletes keresés

Nautilus_ Creative Commons License 2011-01-24 01:06:06 69

 

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.

 

helyett inkább: 

 

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észlete komplementerének véges sok elemét (szavát).

 

--------------------------------------

 

 

Néhány javítás, de a tétel jó volt.

 

Az alábbiak továbbra is formális nyelvelmélet; generatív grammatika helyett azonban mindenhol a generáló rekurzív függvényt, szavak helyett számokat veszünk.

 

Az igazság definiálhatatlansági tételből következik, hogy a Gammában, nemrekurzívan, a P{Ax}-okkal megadott M-igazsághalmaz, függvény, (Gödel-számok halmaza) nem definiálható egyetlen formulával, ha maradunk az adott nyelvben. Ami azt illeti, ha van egy konzisztens elméletünk, amelyből a Q rendszer levezethető, az elmélet típusának egyetlen modelljének igazsághalmaza sem definiálható az adott típusban (itt: az epsilon nyelvben).

(RfC viszont igen.)

 

Még akkor sem, ha ez úgysem lenne effektív, hiszen egy Truth(Gödel(fi)) formula ekvivalenciája fi-vel mindig Gamma más és más axiómáiból, összességében nemrekurzív elméletből lenne levezetve.

 

Másrészt létezik F(x,y) rekurzív függvény, melynek első változójának helyettesítjük Gödel(fi)-t, ahol fi igaz, a második változó (az értékkészlet eleme) pedig csakis RfC egy eleme lehet.

Gamma sajnos képtelen igazolni, hogy F tényleg jó: ez ugyanis azt jelentené, hogy ha F(a,b) igazolható Gammában, akkor "a" egy igaz fi Gödel-száma, ami definiálná az M modell igazságát.

 

Ezért folyamodhatunk egy olyan elmélethez, amely TruthM-et definiálni már képes. Ez lehet egy kifejezőképesebb halmazelmélet, például a Morse-Kelley, amelyben tetszőleges ZFC-modell igazsága definiálható. MK egy tetszőleges modelljének elméletében már a rekurzív F(x,y) meghatározható, és reprezentálható (egyébként, F persze Gammában is reprezentálható - ha benne F rekurzív!). Ekkor "tudni" fogjuk (persze az MK-orákulum ismeretében), hogy melyik rekurzív átszámolási függvény lesz jó F-nek. Van ugyanis olyan formula az MK-modell elméletében, amely F-ről azt mondja, hogy "én TruthM Gödel-számait számolom át f értékkészletének komplementerébe".

DF persze nem felsorolható az MK-modell elméletében sem!

 

Ekkortól tehát F-et nyugodtan használhatjuk Gammában is, RfC elemeinek meghatározására, ha F rekurzív (ezt elérhetjük megfelelő MK-elmélettel): a Morse-Kelley garantálja, hogy az F értékkészletének elemei éppen a nem-felsorolható halmaz elemei lesznek.

 

----------------------------------

 

 

Feltehető a kérdés, hogy erre a hosszas igazolásra miért van szükség, például arra, hogy a Morse-Kelley-modell elmélete és Gamma f értékkészletének komplementere feletti degree-n van?

 

Azért, mert ha nem így lenne, akkor azok az akár paramétermentes másodrendű számelméleti formulák a HYP hiperaritmetikai hierarchiában, és az Analitikus Hierarchiában, amelyek számhalmazokat definiálnak, átírva halmazelméletre, olyan paramétereket tartalmaznának, amelyek "transzcendensek", matematikai módon megfogalmazva: nem-effektívek.

 

És az az F, amely a degree "felettre" számol, nemcsak hogy nem lesz rekurzív, hanem a definiáló halmazelméleti formulájának paraméterei szintén nem-effektívek, vagyis semmilyen módon nem számíthatók ki -

máshogyan fogalmazva: sem halmazelméleti, sem másmilyen (pl. aritmetikai) formulával nem írható le a Church-tézisen belül.

 

------------------------------

 

Végül megjegyzem, hogy Shoenfield egy tétele (1959.) szerint, MINDEN Ax axiómarendszernek van teljes kiterjesztése 0"-n, vagy alatta (élesebben kimondva: alatta).

 

Gondoljuk meg: a sztenderd számelmélet igazsághalmaza 0{omega}! Óriási tehát a bonyolultságbeli különbség.

 

Hogyan lehet ez?

Úgy, hogy Ax, ha lényegesen nemteljes is, független formuláinak halmaza 0", vagy alatti degree-n van, hiszen Sigma_1-halmaz komplementere. Vegyük ezt a halmazt, és adjuk minden formulájának igazságértéket, úgy, hogy a  bonyolultságot nem növeljük, hiszen rekurzív átalakítás. 

 

A következő módon. Ha már adtunk egy Fi formulának igazságértéket, vegyük hozzá Ax-hoz, és a következő Fi* formula, ha ellentmondásos Ax+Fi-vel, akkor legyen hamis (~Fi*), ha igaz, akkor ez persze bizonyíthatatlan.

 

Csakhogy használjuk 0' orákulumát, és azzal a konzisztencia-probléma eldöntjető. Ekkor Fi legyen igaz. Mivel legfeljebb 0' orákulumát használtuk, maradtunk legfeljebb 0"-nél. Q.E.D.

 

 

Felhívom a figyelmet, hogy elképesztően bonyolult Ax-teljes elméletek is vannak, még 0{omega_1CK} felett is!

 

A hozzászólás:
Nautilus_ Creative Commons License 2011-01-22 23:09:12 67

 

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.

 

Előzmény:
Nautilus_ Creative Commons License 2011-01-21 23:56:24 62

Ha jól emlékszem, a CS nyelvekről ilyen az a kérdés, hogy ha L1, L2 CS nyelvek, akkor az uniójuk is az-e?

 

 

De rosszul emlékeztem: a CS nyelvek zártak az unióra, metszetre, komplementerre(!) is.

 

Helyette egy eldönthetetlen probléma CF-nyelvekről: ha van két CF-grammatika, akkor ugyanazt a nyelvet generálják-e?

 

 

Példa bonyolult rekurzív nyelvre, a prímszámok nyelve. Gondoljunk bele, hány nyitott probléma merült fel: Goldbach-sejtés, Mersenne-prímek például.

 

-----------------------

Ha egy probléma általánosságban ezekről a nyelvekről eldönthetetlen, az azt is jelenti, hogy grammatikával nem generálható nyelv szavai (mint formulák, mondjuk).

 

 

Pontosítás: természetesen, a nyelv szavai rekurzív nyelv (Kleene's *): minden adott nyelvre egy szó, amely azt mondja például: "ez az L rekurzív nyelv üres/véges" (v.ö. Mersenne-prímek nyelve).

A rekurzív, CS, CF, reguláris nyelvek megadhatók mondjuk grammatikájukkal.

 

Ha azonban csak az igaz állításokat kívánjuk a nyelvbe venni, akkor az már felsorolhatatlan nyelvet eredményez.

 

Másik értelmezésben, a nyelv két komponenesre esik szét: egy L1 résznyelvre, amelyet ZFC felsorol (amit felsorol, egyúttal el is dönt, mint formulát), és egy másikra, amely nem feltétlenül igaz állításokból áll, mégis felsorolhatatlan.

 

Érdekes tény, hogy a két interpretáció különböző bonyolultságú. Az igaz állítások nyelve bonyolultabb formulával definiálható, mint a második, felsorolhatatlan résznyelvé.

 

--------------------------

 

A Context Sensitive nyelvek pontosan a nem-rövidülő nyelvek! Ez talán a legfontosabb állítások egyike az egész formális nyelvelméletben.

 

Ha egy nyelv rövidülő ugyanakkor, lehet rekurzív.

 

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.

Nyilván, ez egy végtelen fa, amelyen a szavak ülnek (végtelen hosszú ággal, König-lemma).

 

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, hiszen W* nyelvbe-tartozásának eldöntésére algoritmus nem lehet.

Gondoljunk arra, hogy a szavak fáját sokféleképpen lehet particionálni, ahogyan a formulákat is: úgy is, hogy kér rekurzív, úgy is, hogy egy felsorolható, és egy felsorolhatatlan, és úgy is, hogy két felsorolhatatlan részhalmazt kapjunk.

 

Nota Bene: W* hosszabb, mint W.

Ha a nyelvtan egyre csak hosszabb szavakat generál, akkor nincs gond: adott >length hosszúságú szóhoz úgyis eljutunk véges időben.

 

 

Véleményem szerint az egy nagyon bonyolult kérdés, hogy a rövidülő (tehát nem CS) grammatikáknak milyen strukturális kritériumát kell adnunk, hogy rekurzív nyelvet kapjunk. A problémakör egyik legfontosabb kérdése.

 

Ha kedveled azért, ha nem azért nyomj egy lájkot a Fórumért!