Keresés

Részletes keresé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.

 

Nautilus_ Creative Commons License 2011-01-22 00:31:55 63

W* hosszabb, mint W.

 

A gondolatmenetet úgy kell érteni, hogy W* előbb van (a grammatikából való levezetésben), mint W. A rövidülés éppen itt játszik szerepet: hosszú szóból kiindulva, bármikor jöhet egy rövid, 0-adrendű esetben. Más, CS esetben viszont nem: W*-ből csak hosszabb szó jöhet.

 

A Chomsky-hierarchia CS osztálya nyelveinek rekurzivitása éppen ezen múlik: ott ugyanis W* után NEM jöhet rövidebb szó.

 

 

Ezért aztán például a klasszikus logikát nem is tudjuk CS-nyelvvel modellezni.

 

A hozzászólás:
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.

 

Előzmény:
Nautilus_ Creative Commons License 2011-01-17 17:40:28 57

a rekurzív nyelvek nagyon széles kategória: ugye ennek valódi részhalmaza a környezetfüggő nyelvek, annak is a valódi részhalmaza a környezetfüggetlen nyelvek és még annak a részhalmaza a reguláris nyelvek.

 

 

Ehhez két megjegyzés. Egyrészt, a Chomsky-hierarchiában a rekurzív nyelvek nincsenek benne. Nem találtak olyan grammatikai szerkezet-kritériumot, amely definiálná a rekurzív nyelveket.

 

A másik, hogy általában nem egy legalább rekurzív, sőt, CS nyelv szóproblémájának eldöntése a feladat a matematikában, hanem olyan szavaké, amelyek e rekurzív nyelvekről szólnak. Például véges (és ezáltal reguláris-e)? Üres-e? Ezek a problémák szintén szavak, de sajnos általában nulladrendű, nemrekurzív nyelv szavai, például a ZFC-tételeké, vagy ZFC-független (grammatikával nem is generálható) formulák nyelvéé.

 

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).

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? Végtlen-e egy rekurzív nyelv?

 

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