Keresés

Részletes keresés

Nautilus_ Creative Commons License 2011-01-25 00:14:55 77

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.

 

 

 

Ha jól értem, Te komplexitáselméleti problémákat kötsz össze formális nyelvelméleti problémákkal.

A megközelítésed alkalmazás-jellegű, ez nem baj, csak nem legyen kizárólagos. Túl biztos vagy magadban.

 

Persze, nagyon érdekes, ha igazoljuk (ZFC-ben:)), hogy P-ben van mondjuk egy kanonikusan PSPACE-beli eldöntési algoritmust használó nyelv. Ez erős eredmény. Vagy lineáris idejű algoritmussal oldható meg egy 0-adrendű grammatikával generált, de rekurzív nyelv szóproblémája.

 

Ugyanígy ez a témakör az approximáció, közelítő algoritmusok kérdése. Ez nem klasszikus formális nyelvelmélet.

 

Én nagyon szeretem a komplexitáselméletet, a P?=NP-problémát, és hasonlókat. Ezekre külön van topik.

 

Valójában MINDEN komplexitáselméleti probléma átfogalmazható nyelvészetivé, hiszen automaták különböző tárral, és időben döntenek el (ha eldöntenek) nyelveket.

 

Ez azonban már két matematikai ág, az algoritmikus komplexitáselmélet, és a formális nyelvészet összekapcsolódása.

 

A formális nyelvészet azonban ennél több.

 

Az, hogy létezik-e algoritmus az ABC problémára, nem érdekes

 

 

Ha tudod, hogy nem létezik algoritmus, keresel lineáris idejűt?:)

 

Az egzisztenciális bizonyítások alapvetően nem érdekesek

 

Jó, hogy ezt Te így tudod. Jó konstruktivista matematikus lennél: ott ugyanis egy egzisztencia-bizonyításhoz mindig van konstruktív is.:)

 

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

 

 

Előzmény:
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:)

 

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