Keresés

Részletes keresés

buki92 Creative Commons License 2011-01-24 23:34:59 76

Ha benne van, elég L-et generálni,

Igen, erre mondtam, hogy ebben a fogalmi rendszerben ilyet nem lehet.

 

Szerintem:

(1.) az érdekes lenne, ha 0-ás nyelvtanokhoz találsz olyan algoritmust, amely a mondatok nagy részére, elfogadható idő alatt talál levezetést.

(Mondjuk a 'mondatok nagy része' kifejezést te nem fogod érteni, mert azt mondod, hogy végtelen mondat van, ha ebből végesről nem dönti el, akkor ..., egyébként meg végtelen/végtelen. )

 

(2.) az is érdekes lenne, ha tudnál mondani a 0-ás nyelvtanokhoz egy olyan normálformát, amiről egyszerű eldönteni, hogy készíthető-e hozzájuk hatékony algoritmus a tartalmazás probléma eldöntésére.

 

Az, hogy létezik-e algoritmus az ABC problémára, nem érdekes. Az hogy minél hatékonyabb (idő,tár,pontosság)  algoritmust találj minél általánosabb feladatosztályra az érdekes.

 

Az egzisztenciális bizonyítások alapvetően nem érdekesek, azok csak határokat jelölik ki.

 

 

Nautilus_ Creative Commons License 2011-01-24 23:08:08 75

 

Az elütésekért elnézést. Frusztráló, hogy nincs nyelvhelyesség (azaz szintaxis)-ellenőrző program a szövegszerkesztőben, pedig régebben volt.

 

Mellesleg, a szintaxis ellenőrzése 0-adrendű nyelveknél algoritmikusan megoldhatatlan:))

 

De a természetes nyelv állítólag CS, tehát rekurzív, és akkor arra megoldható.

 

A hozzászólás:
Nautilus_ Creative Commons License 2011-01-24 23:01:33 74

Nem az a baj, hogy nincs igazad [nem tudom, lehet, igen, lehet, hogy nem], hanem az, hogy a téma szempontjából nem érdekes, amit mondasz.

 

Nem hiszem, hogy matematikai szempontból éredekes lenne egy olyan program, ami nagyon sok tétel bizonyítását rövid idő alatt megtalálja.

 

 

Az első mondatot értem, a másodikat nem értem, hogyan kapcsolódik ide.

Amúgy abban sincs igazad: fontos egy program, amely rövid idő alatt sok tétel bizonyítását megtalálja (gyorsabban, mint más programok). 

 

 

Ami az első mondatodat illeti.

 

- Még egyszer: legyen L 0-adrendű nyelv, sok ilyen van, programnyelvek is lehetnek akár. Legyen L nem-rekurzív.

 

Legyen most "xywwwxywx" egy szó, amelyről nem tudjuk, hogy benne van-e L-ben?

 

Ha nem, akkor ezt nem is lehet általánosan, algoritmusasal megoldani, HISZEN L komplementere nem generálható grammatikával.

Ezt a tételt nyilván Te is ismered: vannak nem-felsorolható, grammatikával generálhatatlan nyelvek (amelyek komplementere grammatikával generálható).

 

((Mondok egy ilyen nyelvet, jó? Vegyük azon CF grammatika-párokat, mint szavakat, amelyek ugyanazt a nyelvet generálják. Ez a nyelv sem generálható generatív grammatikával.

 

Vagy: azokat a CS grammatikákat, mint szavakat, amelyek CF nyelvet generálnak. Ez a nyelv sem 0-adrendű.))

 

Folytatva:

úgy szeretnénk valami választ kapni, xywwwxywx L-beliségére! Ha benne van, elég L-et generálni, de aha nincs benne: 

 

van bizonyos lehetőség, bár nem egyszerű (ezért lázadozol az igazolásom bonyolultsága miatt). 

 

Ez az állításom. A tétel különben még nem teljes, de mint mondtam, a Metamatematika topkba írom a végét.

 

Ez nem fontos nyelvelméletileg??

 

Persze a linked is fontos problémákat említ, azokat is tisztelem. Csakhogy én most nem azokkal foglalkoztam.

Van ez így:)

 

Előzmény:
buki92 Creative Commons License 2011-01-24 22:35:31 73

Nem az a baj, hogy nincs igazad [nem tudom, lehet, igen, lehet, hogy nem], hanem az, hogy a téma szempontjából nem érdekes, amit mondasz.

 

Nem hiszem, hogy matematikai szempontból éredekes lenne egy olyan program, ami nagyon sok tétel bizonyítását rövid idő alatt megtalálja.

 

De ezek például érdekes kérdések:

http://web.science.mq.edu.au/~tenjinno/download.html

Ha ezeket megválaszolod (akármilyen szóhasználattal), akkor az már formális nyelvészet.

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