|
|
 |
Nautilus_
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_
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_
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!
|