Vigyázat! Cookikat tolunk! Adatvédelem.
Egy elméleti cikk a számítástudomány alappillérének bemutatásáról. Egy másik posztom alá MJoe írta, hogy egy fájl tetszőleges módosításával szinte bármilyen programot elkészíthetünk. Csak szinte, vagy tényleg bármilyen program készíthető? Mik a számítógépek határai?

Az eredeti cikket egyik tanárom, Dr. Czirkos Zoltán írta, ezt néhol átdolgoztam, hogy érthetőbb legyen. Én az első egyetemi félévemben olvastam ezt az írást. Akkoriban még én se értettem sokat belőle, de számos más tárgyban előjött. Habár a példa életszerűtlennek tűnhet, a mögötte lévő elmélet nagyon fontos a számítástudományban, ezen alapulnak többek között a programozási nyelvek is, és az azokból felépített sok-sok szoftver helyessége is.

Vannak matematikai feladványok, amelyeknek a megoldása így kezdődik: „vegyük észre, hogy. ” Ezek legtöbbször jóval nehezebbek azoknál, mint amelyek megoldására általános eljárás, algoritmus adható: amely algoritmusnak a lépéseit bambán végrehajtva jutunk el a megoldáshoz, nem kell közben semmilyen ötlet.

1936-ban – jóval azelőtt, hogy az első igazi számítógépeket megépítették volna – egy angol matematikus, Alan Turing a képzeletbeli számítógépéről írt cikkében. Bebizonyította, hogy minden probléma, amely mechanikus lépésekkel megoldható, az megoldható az ő képzeletbeli, amúgy meglepően egyszerű felépítésű gépével is. Megmutatta azt is, hogy vannak olyan problémák is, amelyek nem oldhatóak meg algoritmikusan. Ez nem változott azóta. A mai számítógépek lelkük mélyén Turing-gépek, képességeiket tekintve egyenértékűek a cikkben bemutatott primitív géppel. Legfeljebb annyi a különbség, hogy gyorsabbak és könnyebb őket programozni.

Ez az írás az említett cikk keletkezésének előzményeiről, és ezen keresztül a programozásról mesél. A diofantoszi egyenletektől indulva eljutunk oda, hogy kitalálunk egy feladatot, amely bár teljesen korrektül van specifikálva, kiderül róla, hogy nem oldható meg programmal.

1. Das Entscheidungsproblem

Diofantosz, az ókori görög matematikus az általa kitalált feladatokról lett híres. Ezeknek a feladatoknak az érdekessége az, hogy bár sokszor megoldásuk közben kevesebb egyenletünk van, mint amennyi látszólag szükséges, mégis mindig megoldhatóak valamilyen trükkel. Főleg mert a megoldásokat az egész számok körében keressük. Egyik feladata így hangzik:

Osszunk egy számot két köb-részre úgy, hogy a kapott köbök oldalhosszainak összege egy adott szám legyen. Legyen a felosztandó szám 370, és az oldalhosszak összege 10.

A hatványozást akkoriban még nem ismerték külön műveletként. A köb-rész alatt Diofantosz olyan számot ért, amely egy egész szám harmadik hatványa, vagyis egy egész oldalhosszúságú kocka térfogata. Tehát tudjuk, hogy az oldalhosszak összege x+y=10, a térfogatoké meg x³+y³=370. Ezek az egyenletek viszonylag egyszerűnek tűnnek, Diofantosz azonban mindig csak egy változót használt. Úgy már sokkal nehezebb megoldani a feladatot. Hogy ezt a hiányosságot pótolni tudja valami mással, minden feladatnál előállt egy egyedi ötlettel. Itt azzal, hogy a kockák oldalhosszait 5+x-szel és 5-x-szel kell jelölni, mert akkor felírható az (5+x)³+(5-x)³=370 egyenlet. Ebből szerencsére a köbök kiesnek, és x²=4-hez jutunk, amiből kijön az is, hogy a kockák oldalai 7 és 3 egység hosszúak.

Egy másik, amúgy talán a legismertebb feladata így hangzik: „osszunk egy négyzetet két másik négyzetre. ” Vagyis hogy keressük meg az x²+y²=z² egyenlet megoldásait az egész számok körében. Ennek is van geometriai értelme: Pitagorasz tétele miatt ezek azok a derékszögű háromszögek, amelyeknek mindhárom oldala egész szám hosszúságú. Itt végtelen sok megoldás lehet, mert ha a (3;4;5) számhármas megoldás, akkor a (6;8;10) is. Ugyanaz a háromszög duplájára nagyítva. Egyébként végtelen számú, egészen más oldalarányú megoldások is vannak.

A sokféle probléma megoldására Diofantosz mind egyedi módszert adott. Felmerült a matematikusokban a kérdés, hogy vajon létezik-e általános módszer ezeknek az egyenleteknek megoldására. Ez annyira fontosnak tűnt, hogy egy német matematikus, David Hilbert az 1900-as évek elején felvette ezt a problémát a matematika tíz legfontosabb, megoldatlan feladatát tartalmazó listára. Az eredeti, német szöveg eleje így hangzott: „Entscheidung der Lösbarkeit einer diophantischen Gleichung. ” Emiatt szinte mindenki Entscheidungsproblem néven említi ezt azóta is. A szöveg magyarul:

Egy diofantoszi egyenlet megoldhatóságának eldöntése. Adott egy diofantoszi egyenlet, tetszőlegesen sok ismeretlennel és racionális együtthatókkal. Adjunk meg egy eljárást, amellyel eldönthető véges számú lépésben az, hogy az egyenlet megoldható-e a racionális számok körében.

Mondhatjuk, hogy ezzel nem kért olyan sokat: nem olyan módszert akart Hilbert, amellyel a megoldások meghatározhatóak. Csupán egy olyat, amivel eldönthető, hogy egyáltalán létezik-e megoldás vagy nem. Viszont a kérés nem is kevés: a kidolgozott módszernek általánosnak kell lennie, és véges számú lépésben, mechanikusan végrehajthatónak kell lennie. Ma már úgy fogalmaznánk ezt meg, hogy Hilbert egy algoritmust várt. Tehát a kérdés ez: létezik-e olyan program, amely bármelyik diofantoszi egyenletet ki tudja elemezni megoldhatóság szempontjából. Bemenet: egyenletek együtthatói, kimenet: van-e megoldás.

Azóta már tudjuk, hogy nem létezik. A kérdést csak 1700 évvel Diofantosz művének megjelenése után sikerült megoldania Alan Turingnek és Alonzo Churchnek. Eltérő gondolatmenettel, de mindketten bebizonyították azt, hogy nem létezhet ilyen program, és hogy még van egy csomó másik megoldhatatlan feladat is. A programozás szempontjából Turing megoldási módszere igen nagy jelentőségű, mert képzeletbeli számítógépének leírásával megalapozta a programozást, a programozói gondolkodást is. Furcsának is tűnik visszatekintve, hogy ez gondolatmenetének csak egy mellékterméke volt.

2. Az egész vagy a tört számok vannak többen?

A bevezetőben említett lehetetlen feladat specifikálása előtt még elmélkedjünk kicsit a számok természetén!

Tudjuk azt, hogy a számok végtelen sokan vannak. Matematikailag a végtelen nehezen kezelhető fogalom. Nemcsak azért, mert a végtelen egy tulajdonság, nem pedig egy szám; hanem azért is, mert nem csak egyféle végtelen létezik. A pozitív egész számokra például azt szoktuk mondani, hogy megszámlálhatóan végtelen sokan vannak. Azért végtelen sokan, mert bármelyiknél tudunk mondani egy eggyel nagyobbat, és azért megszámlálhatóan, mert tudunk írni egy olyan (képzeletbeli) listát, amelyen az összes pozitív egész szám szerepel.

Ennek a listának az elemeit sorba tudjuk állítani és be tudjuk számozni. Minden elem annyiadik sorszámot kapja, mint az értéke. Bár úgy tűnik, hogy ehhez hozzávéve a nullát és a negatív számokat, egy sokkal hosszabb listát kell kapjunk, ez nincs így. Ha indulunk a nullától, és utána felváltva veszünk egy-egy pozitív és negatív számot, akkor a hiánytalan lista ebben az esetben is felírható. Mivel ezek alapján egy oda-vissza megfeleltetést tudunk adni egy pozitív egész szám és egy hozzá tartozó (nem feltétlenül pozitív) egész szám között, kénytelenek vagyunk kijelenteni: a pozitív és negatív számok együtt „nincsenek többen”, mint a csak pozitív számok. Ugyanannyian vannak.

Elsőre azt hihetnénk, hogy racionális törtből sokkal többnek kell lennie, mégpedig azért, mert bármely két szomszédos egész szám között végtelen sok törtet találunk. 0 és 1 között például ott van az 1/2, 1/3, 1/4 stb. Ha minden egymás melletti számpár közé végtelen sok tört kerül, akkor végtelenszer végtelen számú törtnek kell lennie. De ez sincs így! A racionális törtek is megszámlálhatóan végtelen sokan vannak. Ha felírjuk őket egy táblázatban, amelyben az oszlopok a számlálót, a sorok a nevezőt határozzák meg, és utána átlósan, oda-vissza megyünk végig ezen, akkor meg tudjuk számozni az elemeket, és semelyik nem marad ki.

Na jó. Akkor a valós számok aztán már tényleg többen vannak, mert azok nem diszkrét helyeken vannak a számegyenesen, hanem folytonosan! Bár mintha ez igaz lehetne a racionális számokra is, mert a számegyenes egy pontját tetszőleges pontossággal meg tudjuk közelíteni racionális törttel is. (De nem mindegyiket. ) Bizonyítsuk hát be a valósakról is, hogy megszámlálhatóak!

Fog menni? Nem. Ebbe most beletörik a bicskánk. Ez végül is jó hír, mert legalább kiderül, hogy ez esetben helyes az intuíciónk. Meg lehet mutatni ugyanis, hogy nem lehet listát csinálni a valós számokból. Ez egy indirekt bizonyítás lesz (reductio ad absurdum). Az ilyennek a lényege az, hogy feltételezünk valamit, amit aztán tényként kezelünk. Kiindulunk belőle egy levezetéssel, amely közben egyszer csak egy ellentmondáshoz jutunk. Olyan ez, mint amikor egy nyomozó a gyanúsítottjától alibit kér. Megkérdezi, hogy hol volt a bűntény idején. Ha bizonyítani tudja, hogy máshol, akkor ez ellentmondásban lesz azzal a feltételezéssel, hogy ő követte el a bűntényt.

Kövessük Georg Cantor, a német matematikus gondolatmenetét! Mit akarunk bebizonyítani? Hogy nem lehet a valós számokból listát csinálni. Akkor tételezzük fel ennek az ellenkezőjét: azt, hogy mégis csak lehet. A feltételezett listán szerepelnek az egész, a racionális és az irracionális számok is. Rajta van a 2, rajta van az 1/7 és a √2 is, meg a π is. Írjuk le ezeket tizedes törtként is a táblázatunk harmadik oszlopában!

Ezek után pedig tekintsük azt a 0 és 1 közötti számot, amelyet a következőképpen kapunk. A tizedesjegyeinek első számjegyének azt a számjegyet választjuk, ami a listán szereplő első szám tizedesvessző utáni első tizedesjegye (a1), de megnöveljük azt eggyel. Ha ott 9 volt, akkor pedig 0-t veszünk helyette. A századok helyére a második szám második jegyét (b2 plusz egy). A harmadik helyre a harmadik számjegyét, c3-at növelve eggyel, és így tovább. Átlósan haladva a fenti táblázatban, és minden jegyet növelve, ezt kapjuk: 0,15561…, és folyatódik valahogyan.

Namármost, a helyzet a kapott a számmal az, hogy nincs rajta a listánkon. Pedig azt mondtuk, azon minden valós szám rajta van! Hogyhogy nincs rajta? Úgy, hogy ez nem lehet ugyanaz, mint a lista első száma: attól eltér a tizedesvessző utáni első számjegyben. Nem lehet a második sem, mert attól meg biztosan eltér a másodikban. Nem lehet a harmadik sem, és semelyik sem, mert az n-edik elemtől mindig eltér az n-edik számjegyben. A nagy műgonddal összeállított listánk hiányos! A valós számok ellenállnak a felsorolási kísérletünknek: megszámlálhatatlanul végtelen sokan vannak.

A lenti szakasz programozással kapcsolatos írás. A szakaszban klasszikus parancssori programokról van szó. Ezek eltérnek a grafikus programoktól (pl. egy böngészőtől) abban, hogy céljuk néhány bemenetként adott adat alapján egy kimenet meghatározása, így többnyire elég hamar befejezik futásukat.

Kommentnek nevezzük a forrásfájlba írt olyan szövegeket, amik a számítógépek számára nem hordoznak információt, csak azért írjuk oda, hogy az embereket tájékoztatni tudjuk, amikor elolvassák azt.

3. Hány program van?

Programozzunk! A számokat megvizsgálva felmerülhet a kérdés, hogy vajon mi a helyzet a programokkal, azok hányan vannak. Azt tudjuk, hogy végtelen sokan kell lenniük, mert ha egy forráskódba beírunk egy tetszőleges szövegből álló kommentet, akkor az egyből egy másik forráskód lesz. Már egyetlen feladatra (pl. két szám összeadásának elvégzése) is végtelen sok megoldás van (hiszen pl. bármilyen hosszú szöveget írhatunk kommentként mellé), hát még többre. Az igazi kérdés az, hogy vajon megszámlálhatóan vagy megszámlálhatatlanul végtelen sokan vannak.

A választ erre nagyon könnyű megadni. A programozási nyelveken írt, fájlokban tárolt forráskódok fix, véges méretű jelkészletből álló szövegek: pl. egy C nyelven írt program forrásfájljában lehetnek kisbetűk, nagybetűk, számok, néhány írásjel és szóköz jellegű karakterek. Ha ezeket a jeleket, karaktereket megszámozzuk, akkor az ilyen karakterekből felépített végtelenül sok darab, tetszőlegesen hosszú szövegeket növekvő sorba állíthatjuk. A rövidebbektől indulunk a hosszabbak felé; ha egyforma hosszúak, akkor pedig amelyik előrébb van az „ábécében”, az kerül előre. Ahogyan az egész számoknál is.

A szövegek valahogy így néznek ki: a, b, c, … 0, 1, … +, #, … aa, ab, ac … a+, a# … és így tovább. Ezekből aztán ki tudjuk választani a futtatható, hibát nem okozó (szintaktikailag helyes) programokat. Erre a feladatra léteznek kész, helyesen működő másik programok. Még ha egy program kinézetre, a nyelv szabályai szerint helyes is, lehet, hogy számunkra semmi hasznosat nem csinál, de ez most nem lényeges. Ezeket tesszük a listára. A listán lesznek olyan programkódok, amik véges ideig futnak, azaz megállnak valamikor, mintha azt mondanák, "készen vagyok, kiszámoltam az eredményt, több teendőm nincs". Elképzelhető olyan is, amelyik sosem áll le, mert úgy lett megírva, hogy örökké ismételje ugyanazt a műveletet, és olyan is, amelyiknek a kimenete végtelen hosszú. A végtelen ideig futó programokat nem szoktuk szeretni, de ha az a feladatunk, hogy írjuk ki az 1/7 tört tizedesjegyeit, akkor ilyet kell készítenünk.

A lényeg tehát: látjuk azt, hogy a programok egy listában felsorolhatók. Létezik első, második, harmadik, akárhányadik helyes program. Ez azt jelenti, hogy ezek is megszámlálhatóan végtelen sokan vannak.

4. A lehetetlen feladat

A programok megírása előtt mindig specifikáljuk azt, hogy a programnak mit kell csinálnia. Ez egyszerűen annyit jelent, hogy megadjuk, mi kell legyen a program kimenete. Lássunk most egy furcsa, de mégis teljesen korrekt specifikációt.

Írjunk egy olyan programot, amely végtelen sok karaktert ír ki a kimenetére, mégpedig a következőképpen. Az első karakter legyen az előbb említett lista első programja kimenetének első karaktere. A második pedig a második programé, a harmadik a harmadiké és így tovább. Vagyis használjuk ugyanazt az átlós módszert, amit a valós számoknál Cantor: legyen az új programunk kimenetének n-edik karaktere a lista n-edik programja kimenetének n-edik karaktere. Hogy ez működjön, ahhoz persze az is kell, hogy a listában csak olyan programok szerepeljenek, amiknek mindig legalább a várt számú karakterből áll a kimenete. Ennek biztosítása érdekében dobjuk el a listából a véges ideig futó, vagy véges hosszú kimenetet generáló programokat, és foglalkozzunk csak azokkal, amelyek végtelen hosszú kimenetet generálnak. Ezt megtehetjük, és még mindig végtelen sok elemű lesz a listánk, viszont a listán lévő programoknak mindig ki tudjuk keresni a kimenetük n-edik karakterét.

Az eljárás tehát a következő. Generáljuk sorban az egyre hosszabb szövegeket. Kiválasztjuk ezek közül a szintaktikailag helyes programokat. A szintaktikailag helyesek közül kiválasztjuk azokat, amelyek végtelen ideig futnak, és végtelen hosszú kimenetet generálnak. Nekünk most csak ezek kellenek. Minden ilyen programot lefuttatunk, amíg meg nem adja az n-edik karaktert, utána pedig pl. az operációs rendszer segítségével leállítjuk őket (így bár a program önmagától végtelen ideig futhatott volna, mi csak véges ideig futtattuk). A kimenetéből kivesszük csak ezt az n-edik karaktert (a legutolsót, amit kiírt, mert pont utána megállítottuk), és kiírjuk azt az új programunk kimenetére. Legyen ennek a programnak a neve „átlós karakterek”!

Egy ilyen feladatot ellátó program elkészítésénél tulajdonképp három szűrést teszünk egymás után. Az első és harmadik szűrő (itt nem részletezett módon, de) könnyedén megvalósítható, ám a középső szűrőről, amely ellenőrzi egy programnál, hogy végtelen hosszú kimenetet generál-e, nem tudunk semmit. Tételezzük fel ezért, hogy van egy olyan algoritmus, amely képes ilyesmire: megkapja egy program forráskódját, és kielemezve azt megmondja, hogy megfelelő-e. Sajnos ez nem megy csak úgy, hogy elindítjuk a programot, és majd meglátjuk közben. Ugyanis ha egy program már kiírt egymillió karaktert, az még nem jelenti azt, hogy nem fog befejeződni vagy elnémulni később. Szóval itt valami bonyolultabb eljárásról van szó. Mindenesetre tegyük fel, hogy van egy ilyen.

Az „átlós karakterek” programunknak megvan az a tulajdonsága, hogy a három szűrön maga is átjut: megírhatjuk szintaktikailag helyesen, a specifikáció alapján végtelen hosszú kimenetet várunk tőle, így véges sok idő után ki tudjuk választani a kimenetének akárhányadik karakterét. Ez alapján a középső szűrő az „átlós karakterek” forráskódját is megfelelőnek tartja.

A probléma csak az, hogy logikusan ki tudjuk következtetni azt is, hogy nem megfelelő. Miért? Azért, mert ha ez is egy program, akkor valahol ennek is kell szerepelnie az összes program listájában. Sokára ugyan, de előbb-utóbb meg fogja találni a saját forráskódját. Legyen ennek a sorszáma N. Ez helyes szintaktikailag, továbbá a „végtelen” nevű algoritmusunk azt fogja mondani rá, hogy a program megfelelő. A programot elindítjuk, hogy ki tudjuk keresni kimenetének N-edik karakterét. Teker, teker, teker, megkeresi az első helyes és megfelelő programszöveget, lefuttatja azt a programot, és kitalálja az első karaktert. Aztán kitalálja a másodikat, a harmadikat stb. De addig kell futnia, amíg meg nem mondja az N-ediket. Szóval végül eljut az N-edik sorszámú programhoz a listán, ami megint saját maga. Ezért ő is csinál egy új példányt magából, amelyik immár a harmadik iker, és kezdi elölről az egészet.

Itt aztán beragad a folyamat, és soha nem fog tudni túljutni ezen a karakteren. Az első program nem kapja meg az N-edik karaktert, mert arra vár, hogy a második előállítsa azt. A második nem kapja meg, mert a harmadikra vár, és így tovább. Mindegyik ugyanazért képtelen eljutni az N-edikig, amiért már a legelső is képtelen volt rá. Kiderül, hogy a programunk nem megfelelő: nem képes végtelen hosszú kimenetet generálni.

Felmerülhet ötletként, hogy az N-edik programot egyszerűen hagyjuk ki a listáról. Vagy hogy úgy írjuk meg a programot, hogy a saját maga kódját ismerje fel és hagyja ki. De láttuk, a legegyszerűbb feladat is végtelen sokféleképpen megoldható a kommentek és nyelvi elemek variálásával. A program ki kellene hagyja a saját maga kódján kívül az összes többi olyan változatot is, ami saját magával ekvivalens. Ilyen program újra és újra lesz, végtelen sokáig szűrve a listát is ugyan ott tartana, a beragadást nem tudja feloldani.

Tehát van egy programunk, amiről be tudjuk bizonyítani, hogy végtelen hosszú kimenetet gyárt (megfelelő). Be tudjuk azt is róla bizonyítani, hogy mégsem, mert egy bizonyos számú karakter után elakad (nem megfelelő). Ezek egymásnak ellentmondanak! Hol a hiba?! Ott, hogy feltételeztük egy olyan algoritmusnak a létezését, amelyik egy forráskód elemzésével, annak lefuttatása nélkül meg tudja mondani, hogy végtelen kimenetet generál-e, vagy nem (középső szűrő). Ha ilyet feltételezünk, ellentmondásra jutunk. Ilyen algoritmus egyszerűen nem létezhet. Képtelenség megírni ezt a programot.

Ugyancsak lehetetlen azt is megmondani általában, hogy ki fog-e egy program valaha írni egy bizonyos betűt, vagy nem. Azt is lehetetlen megmondani egy programkódról általánosságban, hogy le fog-e állni valaha az általa vezérelt folyamat, vagy nem. Hasonló okok miatt lehetetlen általános módszert adni a diofantoszi egyenletek megoldására is. (Ennek bizonyításával végződik Turing cikke. ) Olyan programot sem lehet írni, amely kitalál egy adott specifikációt megvalósító algoritmust. A programok soha nem fogják tudni helyettesíteni a programozókat, sőt arra is örökké képtelenek lesznek, hogy megtalálják azokat a hibákat, amelyeket elkövetnek algoritmizálás közben. Miért? Mert olyan algoritmust sem lehet csinálni, amely egy tetszőleges programról megmondja, helyes-e szemantikailag, vagy nem.

Fellélegezhetünk: a programozóknak a világ végezetéig lesz munkája!

12 hozzászólás

  • kléni február 20. 00:08

    1
    Hát ezek a képek nem akkora méretűek, mint beállítottam a szerkesztőben. Még egy dolog, amire Cad programja nem képes. xD
  • yust február 20. 02:53

    2
    Hú, ez érdekes volt, köszi!
    Lehet, (biztos?) hogy hülyeségeket mondok, de:

    -Ezt nem értem, hogy a pozitív, és a pozitív+negatív végtelen miért ugyanannyi? Pusztán csak azért mert mindkettő végtelen?

    -És lett egy érdekes gondolatom: Ebből az egészből annak kellett volna következnie, hogy a számítógépes programok képességeinek megvannak a határai. De nekem az ellenkezője is lejött: A számítógépes programozóknak is megvannak a határai (hiszen ők sem tudnak olyan programot készíteni, ami erre képes). Tehát tulajdonképpen ez nem a számítógépek korlátja, hanem a valamiféle magasabb rendű korlát, hiszen mi is korlátolva vagyunk ebben.

    -Tehát a programozók csak nyugodtan aggódhatnak?! :D
  • blaise21 február 20. 07:31

    3
    Mondanám, hogy értettem, de... XD
  • Cíke február 20. 10:30

    4
    A drog rossz, állj le ratyi! rotfl
  • aSaca-Hun február 20. 11:34

    5
    Este elkezdtem csak az a fránya álom manó.Igy ma olvastam végig. grat
  • kléni #2 február 20. 12:13

    6
    @yust:Itt nem pozitív és negatív végtelenről volt szó. Azoknak másféle jelentésük van, és többnyire határérték számításnál használják, ami egy másik témakör. Itt arról van szó, hogy a halmazok elemszáma végtelenül sok. A halmazban lehet akármi, példának okáért pozitív és negatív SZÁMOK is. A fent említett két lista elemszáma nem azért "egyenlő", mert mindkettő végtelen. Két végtelen nem lehet egyenlő, mert ez nincs is értelmezve úgy, mint a 2*3 = 4+2 egyenletnél. Csak a végtelen sok darab fogalma jelent számunkra valamit. A halmazelmélet nem arra keresi a választ, hogy egyenlő-e két végtelen, hanem hogy ugyanolyan tulajdonsága van-e annak a két végtelennek? Abból a szempontból, hogy a csak pozitív, és pozitív+negatív számokról is készíthető egy lista, és minden listabejegyzést sorszámmal tudunk ellátni, ugyanolyan. Ezért is tartják annyira fontosnak a halmazelméletet: nehéz megérteni, hogy nem a végtelenek egyenlőségét firtatja, hanem csak másféle, elvont tulajdonságokat vizsgál.

    A számítógép egy Turing-gép, és így igen, neki vannak korlátai. Az ember viszont nem. Eltérően működik, az agy még rengeteg dologra képes. Emiatt mi képesek lehetnénk olyasmire, amire a gép nem (igazából egy programra ránézve én meg tudnám mondani, az végtelen ideig futna-e), de persze a gondolkodás korlátai miatt ez fordítva is igaz lehet (legalábbis időben), sok dolog számunkra "lehetetlennek" tűnik, és a gyakorlatban annyira bonyolult, hogy nem is igen próbálkozna vele senki. Az emberek képesek algoritmikusan gondolkodni, de másféleképpen is, a gépek viszont nem, nekik csak az algoritmusok jutottak. A cikk elején írták, hogy ami mechanikusan lépésenként elvégezhető, az programokkal, a Turing-géppel is. Célszerűen ez fordítva is igaz, nekem volt is olyan tárgyam, ahol papíron dolgoztunk ilyenekkel. Az emberek próbálkozhatnának évezredekig keresni egy olyan, egyszerű lépésekből álló ellenőrző eljárást, mint a középső szűrő. Tegyük fel, sikerül is találnia ilyet valakinek. Ez ugye azt kéne jelentse (mert bebizonyították róla), hogy a pontos mását is elkészíthetjük, amit egy Turing-gép tud futtatni. Erről viszont be tudtuk bizonyítani, hogy nem lehetséges. A logika szabályai szerint ez csak akkor lehet, ha a feltételezésünk hamis: hiába próbálnánk rengeteg munkát beleölni, mi emberek se lennénk képesek megalkotni az algoritmust. Ha pedig létezne egy program, ami képes a feladatra, de nem a korlátozott emberek hozták létre, akkor az mechanikusan, emberek által is végrehajtható kéne legyen, mert az ember képes algoritmusokat végrehajtani, de ez az előzőek szerint nem lehetséges.

    Inkább azt mondhatnánk, hogy az algoritmusok elméletére adtunk egy korlátot. Amíg a gépek algoritmikusan működnek, addig lesznek korlátaik (és jelenleg semmi esély nincs arra, hogy másképpen működjenek a jövőben), az elmélet korlátait pedig az emberek se képesen megszüntetni - éppen ők határozták meg a korlátokat. Nyilván ha másféle elméletet tudnánk felállítani, és arra alapozva építünk gépeket, akkor lehetséges, de a jelen technológiánk, tudásunk erre nem képes, és talán sose lesz az.
  • yust #6 február 20. 13:12

    7
    @kléni: Hú! Én szerelmes lettem beléd! :D

    A végtelenes dolgot így már értem.

    Viszont a számítógép korlátosságát... Oké, értem, elismerem, de arról nem sokat tudok, hogy ezek az új "neurális hálózatós" meg "AI"-s dolgok hogy működnek. Az oké, hogy hagyományos algoritmusokban gondolkodva szépen ki lehet logikázni mindent, de ezekben a technológiákban van még egyáltalán értelme hagyományos algoritmusokról beszélni? Van-e még egyértelmű igen-nem kimenete egy programnak? És van-e még ember aki ésszel felbírja az egészet?
  • kléni #7 február 20. 13:56

    8
    @yust: Minden mesterséges intelligenciát is hagyományos számítógépen futtatnak, tehát a korlátokat az se tudja átlépni. A mesterséges intelligencia, a sok reklámmal ellentétben nem valami újféle életforma, egy egyszerű program az is, csak más dolgokat csinál meg. Önmagától semmit nem tud a program előteremteni, csak úgy kitalálni, megjósolni, valamilyen adatot fel kell használnia. Az AI annyit jelenthetne, hogy jóval hatékonyabban dolgozza fel az adatokat. Na de a fenti feladatot nézve, mit is kéne csinálnia? Kitalálni az N-edik karaktert csak úgy magától nem tudja, mert az bármi lehetne. A beragadó programokat se tudja teljes pontossággal eldobni, ezekből ugyanis végtelen sok van, ő se fog végezni vele gyorsabban. Lásd a "Felmerülhet ötletként, hogy az N-edik programot egyszerűen hagyjuk ki a listáról" kezdetű bekezdést.
    Ehhez a kérdésedhez azt kell látni, hogy a cikk nagyon elméleti dolgokat taglal. A valóságban még a Turing-gépnek sincs igazán haszna, csiga lassú, nem tud semmit. Ezzel szemben az AI a hétköznapokban tűnik hasznosnak, hiszen egyre jobban helytáll a gyakorlati, emberek számára is nehéz feladatok elvégzésében. Szóval csak mert az AI hasznos nekünk, attól az elmélet még szilárd marad.
  • yust #8 február 20. 14:10

    9
    @kléni: És ez a neurális hálózatos AI-s valami? Az sem egy valódi új technológia? Próbáltam utánaolvasni, de... amikor soronként van egy idegen szó, aminek megértéséhez 8 egyetemet kéne először kijárni, akkor elmegy a kedvem...
  • kléni #9 február 20. 16:13

    10
    @yust: Hát ez attól függ, hogy tekintünk az újra. :D
    Egyfelől nem új, mert valójában a neurális hálók, és egyéb hasonló módszerek elmélete majdhogynem egyidős a számítógépek feltalálásával. Csak akkoriban még nem tudták kihasználni hatékonyan ezt a módszert, mivel lassú volt, nem foglalkoztak vele. Azóta fejlődött a számítási teljesítmény, a számítógépek felhasználási területe is drasztikusan megváltozott, az utóbbi évtized kutatásai révén pedig az elméletet is csiszolgatták, ezért lett annyira jó.
    Másfelől újdonság, hiszen ennyire okos, önfejlesztő, általános problémákat kis hibával megoldani képes programokat mostanában kezdtek el fejleszteni, ezért mostanában érezzük a hatását, hasznát.
    Viszont a neurális hálózat csupán matematika. Mármint szó szerint az. :D Nem áll másból, mint összeadásokat, szorzásokat meg még 1-2 műveletet hajt végre sokszor egymás után, valamilyen szabályrendszer szerint. A felhasznált matematikai módszerek már nagyon régóta rendelkezésre állnak. Van nálunk egy neurális hálózatok nevű szabadon válaszható tárgy, aminek azt a mottót adtuk: ha nem vagy képes éjjel-nappal matekozni, akkor ne vedd fel a tárgyat. Sajnos ez tényleg igaz, maga az elmélet unalmas is, és mivel a hálózatban nem is igen tudunk mit csinálni, mert ott csak összeadások meg szorzások vannak, nehéz átlátni is a folyamatot. Én is jobban szeretem nézegetni az eredményről a videókat, mint előállítani a programot. :D
    A fenti cikk tekintetében újdonságot jelent-e a mesterséges intelligencia? Nem igazán. A neurális hálók néhány típusú feladatot nagyon jól meg tudnak oldani, másokban katasztrófálisan gyenge a teljesítményük. Most úgy tűnhet, hogy az AI-k mennyire okosak, mert kitalálják maguktól a dolgokat, de ez igazából nincs így. Bemeneti adatokat használnak fel más adatok értékeinek megbecsülésére. Ha nincs adat, amit fel tudna használni, vagy nincs összefüggés az adatok között, akkor ez a módszer nem ér semmit. Ezért tud hatékony lenni, hogyha betanítjuk, hogy 10000 képen milyen nevű virágok vannak, aztán találd ki magadtól a 10001. képen lévő virág nevét, de ha azt kérnénk, hogy egy kockadobás következő számát találja ki, akkor se fog tudni a 6 szám közüli tippelésen kívül mást tenni, ha tudja az előző egymillió kockadobás eredményét.
    Képzelj el egy olyan világot, ahogy csak pozitív számok léteznek. Ebben a világban a klasszikus programok valahogy úgy néznének ki, mint egy iskolás matematikai munkafüzet feladatai: határozd meg két szám összegét, melyik az a szám, amire igaz hogy XYZ, hány darab 5 jegyű, 7-tel osztható szám létezik, stb. Habár ezek is lehetnek hasznos feladatok, éreznünk kell, hogy egy általános iskolás, akinek ezek a feladatok szólnak, nem képes akármire, nem bírná el a nagyon bonyolult feladatokat, nem is gond ez. Na és akkor jött a mesterséges intelligencia, aki tételezzük fel, meg tudja mondani melyik az a 300 millió számjegyes prímszám, ami tartalmazza a te telefonszámodat is... Amikor csak az általános iskolás matekkal foglalkoztunk, elképzelhetetlen volt számunkra, hogy ugyan mégis hogyan mondhatnánk meg, melyik ez a bizonyos prímszám? De figyeld csak meg: habár az AI kiadja a 300 millió számjegyes prímszámot, ő se lesz képes soha se negatív számokkal dolgozni! Egyszerűen azért, mert abban a világban nem léteznek negatív számok, és ő egy ilyen világban kényszerül működni. Csinálhat akármilyen okos dolgokat, akkor se tudja a -1-et előállítani... Ez az, amit a fenti cikk leír. A számítástechnikában rengeteg lehetőség van, a legtöbbjét nem is ismerjük még, a problémák köre végtelen sok, a módszerekből is Dunát lehet rekeszteni. A klasszikus programozás is egy ilyen módszer, ami az egyik területen hatékony. A mesterséges intelligencia egy másik módszer, ami másik területen hatékony. De mindkét módszer elméletének gyökerei ugyan azon alapszanak.
  • yust #10 február 20. 17:35

    11
    @kléni: Hmmm... én azt hittem, a neurális hálózat az hardveresen is alapvetően más. Ilyen buta vagyok. :(
  • kléni #11 június 17. 23:01

    12
    @yust: Csekkold a két új videómat, ott megismerheted a neurális hálókat. :D
A hozzászóláshoz be kell jelentkezned.
Belépés, vagy ingyenes regisztráció!