Keresés

Részletes keresés

buki92 Creative Commons License 2011-01-25 09:45:53 79

[Akkor nekifutok mégegyszer:]

Érdekes és lehetőleg minél általánosabb feladatosztályokra keresek konkrét algoritmusokat.

Te meg érdekes és minél általánosabb állításokra hozol konkrét bizonyításokat.

 

Ez két teljesen különböző hozzáállás. Még akkor ha a vizsgált területben vannak is fogalmi átfedések.

Az algoritmusokról szóló tételek sem játszanak. A komplexitáselmélet hasznos ugyan, de kb. csak annyira, mint számelméletben az alternatív logikai rendszerek.

 

(Megjegyzem, hogy az algoritmusok keresése kb. olyan viszonyban van a programozással, mint a matematika a számolással. Csak persze jóval fejletlenebb terület.)

 

Abba meg végképp nem szertnék belemenni, hogy mit értünk formális nyelvészet alatt. A tételeidet meg a bizonyításaidat nyolvancanhat másik topikba írhatod; ide algoritmusokat please.

Nautilus_ Creative Commons License 2011-01-25 02:08:14 78

hogy P-ben van mondjuk egy kanonikusan PSPACE-beli eldöntési algoritmust használó nyelv. Ez erős eredmény.

 

 

buki,

 

közben eszembe jutott egy szép tétel, ami érdekelhet: a CS nyelvek szóproblémája PSPACE-teljes.

 

Így, ha polinom algoritmust találnánk a CS nyelvek szóproblémájának eldöntésére, az P=NP-t is jelentené.

 

Egyúttal az is igaz, hogy IP=PSPACE, vagyis interaktív prokotokollal eldönthetőek a CS nyelvek (Shamir tétele).

 

Végül igaz Savitch tétele: PSPACE=NPSPACE, vagyis a nemdeterminnizmus ebben nem számít. 

 

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

 

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

 

 

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