Furcsa dolog úgy vitatkozni, ha az ember szájába olyan kijelentéseket adnak, amiket nem mondott. Én egy szóval sem állítottam, hogy a megállási problémának köze van az ember számítógép viszonyhoz. Azt sem mondtam, hogy Mariska néni nem ember, mert nem tudja a Fermat sejtést bizonyítani. Egy példát adtam arra, amire az ember képes, a számítógép pedig nem. Nem azt mondtam, hogy minden ember képes erre, csak azt, hogy van olyan ember, nevezetesen Andrew Wiles.
Az általad adott programpéldával kapcsolatban is úgy tűnik teljesen félreértettél. Én is tudok olyan példákat mondani, ahol a megállás megállapítható. Egy üres program megállását megállapító program egy konstans igaz értéket visszadó program. Nem ez a lényeg, hanem az, hogy általában nem megoldható a dolog. Az, hogy a háromtest probléma bizonyos esetekben egzakt módon megoldható, nem jelenti azt, hogy van rá általános megoldás. A megállási problémában pontosan az általános megoldás hiánya a lényeg.
A megallasi problemanak semmi koze az ember-szamitogep viszonyahoz, mivel nincs olyan ember sem, amelyik minden szamitogepprogramrol megmondja, hogy megall-e vagy sem.
"Arra a programra pedig kíváncsi lennék, amelyik nemcsak azt tudná eldönteni, hogy az általa generált algoritmus megáll-e..."
Pl. generalja a program a kovetkezokeppen a masik programot a standard outputjara:
"Az ember és számítógép viszonyát illetően pedig csak akkor fog megváltozni a véleményem, ha megszületik az a számítógépprogram, amely bizonyítást ad a nagy Fermat sejtésre."
Ezek szerint Mariska nenit nem tekinted embernek, mert nem tudja bebizonyitani a nagy Fermat sejtest???
A megállási problémában pontosan az a lényeg, hogy minden programról el akarjuk dönteni, hogy megáll-e. Ha csak azokról akarnánk dönteni, amelyekről már tudjuk, hogy megállnak-e, annak nem lenne értelme. Pont az a lényeg, hogy tetszőleges algoritmusról szeretnénk egy másik algoritmussal eldönteni, hogy az megáll-e. Ez pedig lehetetlen. Arra a programra pedig kíváncsi lennék, amelyik nemcsak azt tudná eldönteni, hogy az általa generált algoritmus megáll-e, hanem még azt is, hogy ennek bizonyítása könnyű-e vagy sem.
Az ember és számítógép viszonyát illetően pedig csak akkor fog megváltozni a véleményem, ha megszületik az a számítógépprogram, amely bizonyítást ad a nagy Fermat sejtésre. Ha a bizonyítás a Wiles-étól eltérő, az még jobb.
Az igazán érdekes probléma, hogyan is lehetne bővíteni a kiszámíthatóságot. Azt már írtam, hogy elvben konstruálható olyan fraktális számítógép, amely bármely programról eldönti, hogy az az adott Turing-gépen megáll-e vagy sem, a baj csak az, hogy a valóságban nem építhető meg. Ahogy itt is elhangzott, mesterséges neuronhálók ekvivalensek a Turing-gépekkel, így nem látszik kiút. Pedig van két érdekes továbbfejlesztése is a hálóknak. Az egyik a sztohasztikus hálókon alapuló neuronhálós számítógépek, a második bővítés a kvantummechanikai hálókon alapulók. Sajnos a sztohasztikus hálókról is bebizonyítható, hogy a velük alkotott neuronhálózat is csak azt tudja kiszámolni, amit a Turing-gépek. A kvantummechanikai hálók azonban igen ígéretesek. Már csak azért is, mert egy olyan kvatummechanika rendszernek, amely egynél több elemet tartalmaz, egzaktul nem igen tudjuk kiszámítani a viselkedését. Emitatt egy sokelemű kvantumos hálót sem tudunk egzaktul modellezni számítógépen. Ha tehát csak körülbelül számolhatjuk, lehet, hogy egy valóságosan működő kvantumos hálón való számítások sokkal többre lesznek képesek, mint a Turing-gépek. A baj csak az, hogy pl. a kimondottan kvantumszámítógép modellek (nem hálózatok!), ugyan elveben sokkal gyorsabban számolnának, mint a mai számítógépek, de ezek megint csak ekvivalensek lennének a Turing-gépekkel. Szóval ez még egy nyitott probléma, hogy végül is a kvantumhálókon alapuló számítógépek mire lennének képesek, meg persze az is, hogyan tudnánk megípíteni ezeket.
> most rágtam át magam egy 10 oldalas tanulmányon, amely bebizonyította, hogy a neur.hálók (speciel > egy primitív perceptronos rekurrens háló) ekvivalensek a T-géppel
A tiz oldalbol 9,5 hogy a minden Turing gep reprezentalhato neuronhaloval. Ket sor megjegyzes, hogy termeszetesen minden neuronhalo szamolhato Turing-geppel :)
A cikket nem ismerem, de azt tudom hogy az egyik irany trivialis, a masik (A Turing gepek leirhatok perceptronnal) korantsem...
Hi consciousless! Örülök, hogy újra találkoztunk. :-) Sajna a kapcsolatfelvétellel a KFKInél még nem állok túl jól, mert sok dolog bekavart s teljesen el voltam havazva (még mindig kevés az időm, de már sokkal jobb a helyzet :-). Viszont még mindig érdekelne a dolog. Esetleg tudsz írni vmi infót - e-mailben - a pécsi csapatról?
KoporShow: Hmm, igazat kell adnom neked, mert most rágtam át magam egy 10 oldalas tanulmányon, amely bebizonyította, hogy a neur.hálók (speciel egy primitív perceptronos rekurrens háló) ekvivalensek a T-géppel (s a kiszámíthatóság-elmélet jelenlegi állása szerint ennek a legnagyobb a megoldóereje). :-)
Hmm, a Church-tézis meg "csak" azt modja ki, hogy egy feladathoz akkor és csak akkor létezik algoritmus, ha Turing-géppel megoldható. Ennek csak az egyik irányát lehet bebizonyítani, mégpedig a Turing-gép -> algoritmus irányt. Viszont nem mondhatod, hogy nincs olyan folyamat, ami nem lenne leírható Turing-géppel, hisz nem láthatod előre a megoldandó problémákat. (Más dolog, hogy a jelenlegi tapasztalataink alátámasztják a másik irányt is :-).
Mind az onmodosito kodok mind az a neuronhalok, az osszes heurisztikak az egyetemen tanitott algoritmusfogalom ala tartoznak. Az onmodosito kod algoritmikussaga peldaul az univerzalis Turing gep letezesenek kovetkezmenye.
Nem ismert a termeszetben olyan folyamat, amely diszkret inputbol diszkret outputot generalna es nem lenne leirhato Turing geppel. A Church tezis azt allitja, hogy nincs ilyen, es ha ezt megcafoltak volna, az egy kolosszalis eredmeny lenne, amitol harsogna a szakirodalom...
regen mas nicken valtottunk par levelet. Hogy allsz a kapcsolatfelvetellel a KFKInal? Ha hosszabb tavon erdekel a dolog, a pszichologiai kutatointezetben a Molnar Mark es egy pecsi csapat is elkezdett a dologgal kiserletesen foglalkozni, jo lenne kooperalni egy programozoval is.
Elfelejted, hogy egy számítógép egy problémát nemcsak algoritmikus úton tud (próbálhat) megoldani. (De ha csak az algoritmusokat vizsgájuk, akkor sem tudjuk, hogy van-e olyan probléma, amely algoritmikusan megoldhatatlan, hisz ehhez definiálni kéne, hogy mi is az az algoritmus.) Az egyetemeken úgy tanítják (de ez nem definició!), hogy az algoritmus egy véges ábécével leírt véges hosszúságú szöveg. DE maga ez a szöveg statikus. Ha nem az lenne, akkor szinte lehetetlen lenne elméleti módszerekkel vizsgálni a működését (éppúgy, mint ahogy a nemlin. diff. egyenletek viselkedését is nehéz vizsgálni). Talán vannak itt a fórumon még olyanok, akik még anno írtak önmódosító kódot asmben (RuLZ! :-), s ennek analógiájára lehet önmódosító algoritmusokat is írni. :-)
Továbbá léteznek nem algoritmikus feladat-megoldási módszerek, mint például a neurális hálók. SZVSZ ezek megoldóereje jóval az algoritmusok fölött van (persze most nem a perceptronos backpropos hálókra kell gondolni -bár ezek is izmosak lehetnek-, hanem pl egy kaotikus rekurrens hálóra, amely már tényleg közel áll egy emberi agyhoz (jelenlegi tudásunk szerint)). Persze nem tudom bizonyítani, hogy tényleg nagyobb-e a megoldóerejük.
Még tovább menve a két dolgot össze is kapcsolhatod: van egy algoritmusod amely "tanítja" a hálót, DE később maga a háló módosíthatja a tanító algoritmust. Ez -emberre vonatkoztatva- olyan lenne, mintha tudati úton átírnád a DNS-edet vagy pl a neurotranszmitterek működési elvét a hatékonyság érdekében.
"Az, hogy egy számítógép nem tud programot írni, igen egyezerűen bizonyítható. Ugyanis egy számítógép képtelen lenne leellenőrizni, hogy az általa írt program működőképes, ugyanis a megállási probléma miatt végtelen ciklusba kerülhet a saját maga által írt programmal."
Nem! A megallasi problema csak akkor eldonthetetlen, ha minden programrol el akarjuk donteni, hogy megall e. Ha a gep csak a sajat maga altal generalt programrol akarja bizonyitani, hogy megall e, akkor ennek korantsem kell eldonthetetlennek lennie. Valojaban generalhatja ugy a programot, hogy egszeru legyen bizonyitani, hogy meg fog allni. Ez avval analog, hogy egy bizonyitast bar nehez megtalalni, de konnyu leellenorizni. (P != NP)
"Látom, végülis sokan kétlik, hogy az ember képes olyan feladatok meoldására, amelyre a számítógép nem, de számomra ez evidencia, hisz minden nap tapasztalom."
Bill Gates mondta ugy 15 eve: "640k should be enough for everyone." Ha a szamitastechnika statikus volna, ez a vita letre se jott volna. Honnan veszed a batorsagot (botorsagot), hogy a programok mai allasat vedd orokervenyunek?
Nem reagalnek a nagy 'kinyilatkoztatasokra', maradnk csak a konkretumoknal:
Irod:
"Sehol sem írtam, hogy az ember BÁRMELY programról eldönthetné, hogy megáll-e, vagy sem, midössze arról, hogy olyan esetekben képes ilyen döntésre, amikor a számítógépek nem."
Mutass egyetlen ilyen programot, ha ilyenekkel talalkozol nap mint nap... Addig nincs ertelme vitazni.
Nos, hogy visszatérjünk az alapproblémára, mi is igazán a lényege a formális rendszereknek és kapcsolatuk a gondolkodáshoz, ezen keresztül pedig Gödel nem teljességi tételéhez.
A valóságról alkotott tapasztalataink során szembesülünk azzal, hogy sok dolog ismétlődik. Például a Szóthisz csillag Heliákus kelése után 7-8 nappal mindig kiárad a Nílus, és megtermékenyíti a termőföldeket az őserdőkből magávalhozott, nitrátokban és foszfátokban gazdag üledékkel. Ez alapján, ha a csillagok olyan nagy volumenű dolgokat maghatároznak, mint a Nílus áradása, akkor olyan elenyésző dolgokat, mint a porból vétetett ember sorsa, méginkább kell hogy meghatározzák. Innen ered az asztrológia "tudománya".
Na ja, de akkor mi a tudomány, és mi a hit és végül is mi közöttük a különbség? A megfigyeléseink rendezésére találták már ki az ókorban az első axiómarendszert a geometriára, de a logika is megjelent már Arisztotelésznél. A "racionalizmus" az újkorban éppen azért alakult ki, hogy a tudományt megkülönböztethesse a különböző, erősen kétséges hitektől. Jól kiválasztott, mindenki számára könnyen hihető, megfigyeléseken alapuló axiómákból, a logika segítségével levezetett tételeket bizonyítva jusson állításokhoz, amelyek ugyancsak kísérletileg bizonyíthatók. De, ahogy arra már Pascal is rámutatott, és napjainkban Kuhn és mások is, a helyzet nem ilyen egyszerű. Mindig valamilyen intuitív, nem éppen szigorú nézeteink vannak a világról, amelyeknek csak egy részét axiomatizáljuk, azt amelyet egyáltalán lehet rendszerbe foglalni. Továbbá, ha van is egy uralkodó nézetrendszerünk egy adott korban, mindig akadnak olyan megfigyeléseink, amelyek nem egyeztethetők össze az adott paradigmával.
Gödel tétele pedig éppen azt mondja ki, hogy ilyen dolgok mindig is lessznek, azaz soha sem érhetünk a tudomány végére, hisz nem lesz egyik rendszerünk se teljes. Mindig szükség lesz újabb és újabb rendszerekre, amelyek maguk után vonják, hogy megint csak lesznek, az adott rendszer keretei között meg nem magyarázható jenségek.
A matematika itt kilóg, abban az értelemben, hogy egy adott axiómarendszerét örökre igaznak tekintjük, ha az ellentmondásmentes. Az újabb részek, vagy az újabb ismertekre alkotott matematika modellek axiómái, mint új rendszerek mintegy hozzáadódnak a matematika egészéhez, nem ignorálnak régebbi rendszereket, mint a tudományok egyébb területén, ahol például ma már az arisztotelészi fizika csak kuriózomnak számít néhány tudománytörténésznél, míg a logikája ma is alapja a matematikai logikának. Ugyan akkor - Gödel tétele miatt - azonban a matematikában is juthatunk olyan tételekhez, amelyek nem következnek az adott axiómarendszerből, ez viszont éppen a matematika fejlődésének a lehetőségét biztosítja, azaz mindig alkothatunk újabb axiómarendszereket (már ha szükségünk van rá), amelyek nem lesznek azonosak a már ismertekkel, vagy az ismertek lesznek különféleképpen bővíthetőek.
Látom, végülis sokan kétlik, hogy az ember képes olyan feladatok meoldására, amelyre a számítógép nem, de számomra ez evidencia, hisz minden nap tapasztalom. Én inkább annak bizonyítását nem látom, hogy bármilyen számítógépprogram képes lenne arra, amire akár egy kutya is. Én inkább továbblépnék, hogy mi is a formális rendszerek előnye, ha az ember mégis többre képes ezeknél.
Azért reagálnék néhány megjegyzésetekre. Sehol sem írtam, hogy az ember BÁRMELY programról eldönthetné, hogy megáll-e, vagy sem, midössze arról, hogy olyan esetekben képes ilyen döntésre, amikor a számítógépek nem. Az, hogy egy számítógép nem tud programot írni, igen egyezerűen bizonyítható. Ugyanis egy számítógép képtelen lenne leellenőrizni, hogy az általa írt program működőképes, ugyanis a megállási probléma miatt végtelen ciklusba kerülhet a saját maga által írt programmal, miközben ellenőrzi, innen aztán vége, hacsak ki nem kapcsolod a számítógépet, és újra nem indítotd. A heurisztikus módszerek sem csodaszerek, hisz azok is algoritmusok, rájuk is érvényesek a tételek.
Aztán, ott van az, hogy csak egy teljes modellt kell adni a vlóságról, és máris úgy viselkedik. A Gödel-tétel éppen ezt akadályozza meg, a tétel értelmében ilyen teljes modell nem lesz soha sem lesz adható. Mert a Gödel-tétel éppen azt jelenti, hogy nincs teljes rendszer, egy bizonyos bonyolutság felett. Persze az eredti bizonyítás, amely a valós számok tulajdonságán alapult, valóban jelezheti egyeseknek, hogy csak a valós számokról bizonyítja, hogy számosságuk végtelen, de nem erről van szó. Az igaz, hogy a matemetika által konstruállt dolgain általában kontinuum számosságúak, mig az axiómák és a belőle képzett tételek csak megszámlálhatóak lehetnek, így mindig lehet találni megszámlálhatatln sok olyan tétetelt, amely nem lesz következménye az axiómarendszernek.
Ahogy azonban már írtam, itt csak megismételni tudom, minden formális rendszer, amely tud beszélni saját szintaxisáról és struktúrájáról, az már Gödeli rendszer. Ezt Tarski bizonította be. Továbbá ő mondta ki, hogy az olyan rendszer, amely saját szemantikájáról is tud beszélni az ellentmondásos lesz, nem lehet axiomatizálni. A beszélt nyelv estén evidens mindenki számára, hogy a mondataink jelentéstartalmáról is tudunk beszélni ugyan azzal a nyelvel. A beszélt nyelv struktúrája egészen más, mint a formális rendszereké! Persze tele is van ellentmondással! Ez azonban nem zavarja az embert, hisz csak meg kell(ene) néznie, hogyan is van valami a valóságban. Éppen a valóságtól elrugaszkodott, egy adott eszmerendszerhez túlságosan is következetesen ragaszkodó embert szoktak irracionális viselkedéssel vádolni.
> Pontosan ugyan úgy bizonyítják az algoritmikus kiszámolhatatlanságot, mint annak idelyén Gödel a nem teljességi tételét,
Nem! A nem kiszamlalhato fuggvenyek letezese trivialis: egyszeru szamossagi oka van: fuggveny kontimuum sok van mag algoritmus csak megszamlalhato.
A megallasi problema eldonthetetlensege is csak tavolbol emlekeztet Godel bizonyitasara. Mig az elobbi majdhogynem trivialis egy-ket soros teljesen intuitiv bizonyitas, addig a Godel tetele technikailag sokkal komplikaltabb. Igaz a Godel tetele egy egyszeru paradoxonon alapul: "ez az allitas hamis", az igazi lenyege kicsit mas. Sokan interpretaljak Godel tetlet valami negativnak: "nincs teljes axiomarendszer. En a Godel nemteljessegi tetelet valojaban egy teljessegi tetelnek latom: a termeszetes szamok axiomarendszer olyan eros, hogy meg az onreflexiora is kepes. Es itt nagyon fontos, hogy Godel tetele kihasznalja, hogy az axiomarendszer tartalmazza a termeszetes szamok axiomarendszeret, kulonben nem is lenne igaz.
> Nincs olyan, hogy a halmazelmélet axiómarendszere.
Van egy altalanosan elfogadott axiomarendszer, amit a matematika 99%-ban hasznalnak.
> akkor a geometriában bebizonyíthatóvá válik a Banach-Tarski-paradokszon
A Banach-Tarski paradoxonnal nincs semmi baj. Ez a kivalasztasi axioman mulik. Ezt altalaban a geometerek is igaznak tekintik. A kivalasztasi axiomaval bizonyitott allitasokkal csak egy bibi van: ha csak a segitsegevel tudjuk egy matematikai objektumrol bizonyitani, hogy letezik, akkor biztos, hogy sosem fogunk az objektumra konkret (konstruktiv) peldat mondani. Ez azert van, mert a kivalasztasi axioma fuggetlen a tobbi (mondjuk igy, veges axiomatol, tehat ez egy Godeli allitas). Ezert szoktak a matematikusok az ilyen teteleket nem kedvelni, es hozzateszik, hogy fugg a kivalasztasi axiomatol. Ez azonben csak marginalis kerdes, es lenyegeben csak a halmazelmeleszek vacakolnak kulonbozo axiomarendszerekkel es modellekkel, a matematika nagy resze Zermelo-Fraenkel axiomarendszerre epul (+/- kivalasztasi axioma).
> Az, hogy egy Turing-gép nem bővithető tovább úgy, ahogy leírtad, az abból következik, hogy az univerzális Turing-gép univerzális, azaz bármit, amit ki lehet számolni, azt már ki tudja, ennél az univerzálisnál univerzálisabbat már nem lehet definiálni.
Atgondoltad, hogy mit irsz? Az univerzalis Turing-gepnek semmi koze nincs ahhoz, amit irtam, sot az egesz vitahoz nincs sok koze. Az univerzalis Turing gep egy specialis Turing gep, amely minden Turing gepet modellezni tud egy megfelelo veges bemeneti szalaggal. Nem tudom, hogy miert hoztad ezt fel. Egyebkent pedig igenis lehet definialni, amit irtam. Konkretan: legyen f egy fuggveny ami egy adott Turing geprol eldonti, hogy valaha megall e.
Definicio: Bovitsuk ki a hagyomanyos Turing gepet avval, hogy a hagyomanyos operaciokon kivul az is a rendelkezesere all, hogy kiertekeli f-et egy bizonyos (megfelelo kodolassal adott) Turing-gepre.
Ez a kibovitett Turing gep jol definialhato. Igaz nagy valoszinuseggel a valosagban sosem lesz megepitheto, viszont nem ez volt a kerdes, hanem hogy lehet e olyan matematikai modellt adni amiben a kiszamithatosag szelesebb koru, mint a hagyomanyos Turing-gepben. Ime.
Mas reszrol maga a Turing gep sem lesz soha a valosagban megepitheto. Egy vegtelen szalagot ugyanis nehez legyartani.
> mert lehet megfogalmazni olyan utasításlistát, amelyek, amelyek alapján az emberek meg tudnak oldani olyan feladatokat, amelyek nem hogy számítógéppel nem oldhatók meg, de még szigorú matematikai leírása is pillnatnyilag lehetetlen.
Ha nem tudod matematikailag leirni, akkor nem tudod bizonyitani, tehat ez egy hittetel, vagy velemeny, de legalabbis nincs sok koze Godel tetelehez, amivel allandoan dobalodzol. Egyebkent kivancsi lennek egy ilyen utasitaslistara.
> Egy gyakorlott programozó ezt minden további nélkül megteheti.
Egy gyakorlott programozo sem tudja egy tetszoleges programrol eldonteni, hogy meg fog e allni. O csak megprobal olyan programot generalni, amirol o tudja, hogy meg fog allni. Es altalaban meg ez sem sikerul tokeletesen. Egy szamitogepnek szerintem sokkal tobb eselye lesz, hogy programokat irjon, amikrol be tudja bizonyitani, hogy megallnak. Egy ember ilyet szinte sosem csinal.
> a renormáláselmélet már matematikailag korrekten nem is tárgyalható
Most eppen nem tudjak, de ez meg nem jelenti, hogy "nem targyalhato".
> nincsenek szigorú matematikai alapjai
A leirasodbol ugy tunik, hogy nagyon is van, de a fizikusok meg nem elegedettek, mert bizonyos helyen homalyos pontok vannak, amit intuicioval (lasd: pattern matching, stb) bizonyos szituaciokban jo esellyel ki lehet tolteni. Ez viszont nem jelenti, hogy egy gep ne lehetne kepes erre ugyanolyan biztonsaggal (vagy inkabb bizonytalansaggal) mint egy ember. Masreszt pedig szerintem a fizikusok nagy resze arra voksolna, hogy ezek a hezagokat az elkovetkezo par szaz evben ugyis be fogjak tomni.
> A többi példát nem sorolom, amikor az ember képes olyan dolgok megoldására, amelyekre a Turing-gép nem.
Meg egyet sem mondtal.
> Azt is mondtam azonban, hogy lehet, az ember sem oldja meg azokat, csak annyira bonyolult az algoritmusa...
Szerintem a szituacio valami ilyesmi, bar lehet hogy egy kicsit komplikaltabb.
> Ez a vélemény azonban nem lehet helyes, mert ha egyszer egy probléma nem oldaható meg bizonyíthatóan számítógéppel, akkor az nem oldaható meg, ha valahogy valami mégis megoldja, akkor az nem lehet számítógép.
Az Torgyan is megirigyelhetne a godnolatmenetedet:)
A megoldas az, hogy az altalad felsorolt kerdeseket az ember sem oldja meg biztosra, csak neha, ha makja van. A valoszinuseget szerencsere lehet novelni.
"Pl. programot írni nem fog tudni egyetlen számítógép se, mert képtelen lenne leellenőrizni, hogy működik-e a programja, avagy sem, mivel elég könnyen végtelen ciklusba kerülhet egy ilyen ellenőrzés kapcsán a megállási probléma lehetetlensége miatt. (Egy gyakorlott programozó ezt minden további nélkül megteheti.)"
Ez baromság. Maximum azt állíthatod, hogy a program nem fog tudni BÁRMILYEN programot leellenörizni véges idö alatt. De, lepödj meg, programozó sincs ilyen.
És ha már itt tartunk, elárulom neked, hogy a heurisztikus módszerek is algoritmusok.
Pontosan ugyan úgy bizonyítják az algoritmikus kiszámolhatatlanságot, mint annak idelyén Gödel a nem teljességi tételét, hogy vannak nem bizonyítható állítások, iletve vannak nem kiszámítható dolgok, a bizonyítás menete teljesen megegyezik a két esetben.
Az, hogy egy rendszer kibővithető egy olyan tételle, amely sem nem bizonyítható, sem nem cáfolható, az megint csak Gödel tételéből következik, ha ugyanis az adott állítás gödeli a rendszerben, akkor hozzávehetjük vagy az állítást, vagy a tagadását, az új rendszer nem lesz ellentmondásos, ha az eredeti sem volt az. Mivel azonban Gödel tételének bizonyításából az következik, hogy megszámlálhatatlanul végtelen sok ilyen állítás van, ezért akárhány állítással is bővíted a rendszered, soha sem válik deduktívan teljessé. Ez egyúttal azt is jelenti, hogy soha sem adható semilyen teljes modellje bármilyen dolognak. Azonban már a matematikában is bajok vannak. Nincs olyan, hogy a halmazelmélet axiómarendszere. Vannak axiómarendszerek a halmazelméletre és a matematikusok annak függvényében használják egyiket vagy másikat, hogy mit akarnak bizonyítani. Mert pl. ha azt a halamazelméleti axiómarendszert használják, amely a modern algebrák alapja, akkor a geometriában bebizonyíthatóvá válik a Banach-Tarski-paradokszon. Ha azonban olyan halmazelméleti axiómarendszert használnak, amelyben ez a paradoxon nem lép fel a geometriában, akkor az aritmetikában sok érdekes tétel nem lesz bizonyítható.
Aztán pl. a fraktális számítógépek teljesek, megoldják a megállási problémát, a baj az, hogy csak elméletebn léteznek, a valóságban nem megépíthetők. Az egyéb számítógépek, mint a párhuzamosan programozhatók, a kvantumszámítógépek stb. pedig valóban visszavezethetők a lináris Turing-gépre.
Az, hogy egy Turing-gép nem bővithető tovább úgy, ahogy leírtad, az abból következik, hogy az univerzális Turing-gép univerzális, azaz bármit, amit ki lehet számolni, azt már ki tudja, ennél az univerzálisnál univerzálisabbat már nem lehet definiálni. Az persze igaz, hogy az algoritmus fogalma tovább bővithető, ez egy lényeges nehézsége az algoritmusok elméletének napjainkban, mert minden matematikus más definíciót ad, a "hivatalosnak" az számít valóban, amit egy Turing-gép véges idő alatt meg tud oldani. Az algirtmusok fogalmának a bővítése azért érdekes kérdés, mert lehet megfogalmazni olyan utasításlistát, amelyek alapján az emberek meg tudnak oldani olyan feladatokat, amelyek nem hogy számítógéppel nem oldhatók meg, de még szigorú matematikai leírása is pillanatnyilag lehetetlen.
Pl. programot írni nem fog tudni egyetlen számítógép se, mert képtelen lenne leellenőrizni, hogy működik-e a programja, avagy sem, mivel elég könnyen végtelen ciklusba kerülhet egy ilyen ellenőrzés kapcsán a megállási probléma lehetetlensége miatt. (Egy gyakorlott programozó ezt minden további nélkül megteheti.) A programok szerencsére még matematikailga elemezhetőek. Azonban a fizikában pl. a renormáláselmélet már matematikailag korrekten nem is tárgyalható, nemhogy a megoldása. Ennek ellenére jól meghatározott, tanítható diszciplinákból áll, amely elsajátítása után bárki ugyan úgy meg tud oldani kvantutérelméleti problémákat, mint Feynman, a kitalálója ennek az eljárásnak. Tudományosnak csak azért tartják, mert ugyan nincsenek szigorú matematikai alapjai, azonban ezzel a módszerrel számolt eredmények a kísérletekkel sok tizedesjegyre megegyeznek. A többi példát nem sorolom, amikor az ember képes olyan dolgok megoldására, amelyekre a Turing-gép nem, mert már az előzőekben is felsoroltam jó párat. Azt is mondtam azonban, hogy lehet, az ember sem oldja meg azokat, csak annyira bonyolult az algoritmusa, hogy ilyen problémák valamely közelítése után már könnyen látja a megoldást. Ez a vélemény azonban nem lehet helyes, mert ha egyszer egy probléma nem oldaható meg bizonyíthatóan számítógéppel, akkor az nem oldaható meg, ha valahogy valami mégis megoldja, akkor az nem lehet számítógép.
> Ha fizikai modelt akarsz, az persze lehetetlen, mivel az is egy adott rendszer lenne, arra is érvényes lesz Gödel tétele
Na, ez mar a homalykeltes csucsa!
A Godel tetelnek nincs ilyen kozvetlen kapcsolata az algoritmikus kiszamolhatosaghoz.
Manapsag egy olyan fuggvenyt nevezunk algoritmikusan kiszamolhatonak amit egy Turing gep veges ido alatt tetszoleges behelyettesitesre ki tud szamolni.
A Godel tetel nem zarja ki, hogy definialjunk olyan matematikai modellt "Trans-Turing gepet", amiben ilyen feladatok megoldhatok. Pelda erre: vagyunk egy algoritmikusan nem kiszamithato fuggvenyt es bovitsuk ki a Turing gepunket egy szubrutinnal, ami ezt a fuggvenyt szamolja. Ez egy ervenyes "Trans-Turing gep"-lesz, ami fog tudni olyat szamolni, amit Turing gep nem (Latod, ennek nincs koze a Godel-tetelhez.) A kerdes, hogy ez fizikailag megvalosithato e. Sokat gondolkoztak arra, hogy a mai fizika torvenyei lehetove teszik e olyan gepek letre-hozasat amely megnoveli a Turing gepek altal kiszamolhato fuggvenyek osztalyat. Ahogy ezt magad is kitalalhattad, meg sikertelenul. Definialtak ugyan a kvantumszamitogep fogalmat, de ez ugyanugy csak a Turing-geppel kiszamolhato fuggvenyek osztalyat tudja szamolni, csak gyorsabban. Az meg mindig vita targya, hogy kvantumszamitogep valoban epitheto e. Ez nem csak gyakorlati, de elmeleti kerdes, mert ki elvileg ki lehetne hozni minden kiserletezes nelkul csak a matematikai fizika modszereivel, hogy ez lehetetlen, azert mert a kvantumszamitogep modellje olyan posztulatumokra epul, amik nem 100%-ig bizonyitottak.
Mutass jol definialt matematikai feladatot, ami az emberi aggyal megoldhato, de egy Turing-geppel nem.
Ha nem tudsz, akkor az allitasod csak velemeny, es ilyenkor egy "szerintem" kitetel kotelezo lenne.
Egyebkent ez komoly vita targya, a Church tezis szerint az emberi agy minden merheto (tehat diszkret) megnyilvanulasa modellezheto Turing geppel. Ezt tudomasom szerint eddig senki nem cafolta, sokan persze ellenkezo velemenyen vannak, de ez csak velemeny, es nem tudomanyosan bizonyitott teny. Meg nagyobb a hatarozatlanok tabora, mint en, akik mindket feltetlezes mellett sulyos erveket latnak.
Ez az egesz, nem ennek a topicnak a targya: nem is en hoztam fel a szamitogepek vs. emberek temat: az idegesit, hogy a Godel-tetelbol, ami egy viszonylag egyszeru paradoxon technikailag magasabb szintu atfogalmazasa, egesz mas iranyu kovetkeztetest vonnak le logikailag helytelenul, es ezt ezutan mint tenyt talaljak. Sajnos a Godel tetel kivaloan alkalmas erre, mert laikusnak is konnyu felszinesen megerteni.
Ha fizikai modelt akarsz, az persze lehetetlen, mivel az is egy adott rendszer lenne, arra is érvényes lesz Gödel tétele, de ha azt akarod, mondjak olyan vlóságosan létező fizikai rendszert, amely képes elvégezni turing géppel el nem végezhtő dolgokat, olyan létezik, és úgy hívják emberi agy.
Ez most egyre zavarosabb. Természetesen egy számítógép sosem tud teljesen úgy viselkedni, mint egy vízmolekula. Tehát ha a megoldandó problémának azt adod, hogy "legyél tökéletesen olyan, a legapróbb fizikai részletekig, mint egy vízmolekula", akkor sajnos a vízmolekula gyöz a Cray-3 fölött. És akkor mi van? Azt is adhatnánk, hogy "viselkedj úgy mint egy Cray-3", és rögtön gyözött a technofetisizmus :-)
Itt most valódi problémák megoldásáról van szó. Keresd meg a legrövidebb utat. Vagy egyél-növekedj-szaporodj. Esetleg írjál miszticista cikkeket a Tudomány rovatba.
Attol fugg, hogy mit ertesz szamitogep alatt, hol huzod meg a hatart. A kerdes valojaban, hogy egy ember viselkedese szimulalhato e szamitogeppel (feltetelezve a megfelelo input/output lehetosegeket). Ha neked ennek az ellenkezoje teny, akkor te sokkal tobbet tudsz, mint a szakma nagymenoi. Pl. el lehetne felejteni a Church-tezist, tehat eleg izgalmas lenne. Meg a kvantumszamitogepek sem lepik tul a Turing-kiszamithatosag kereteit. Adj egy fizikai modellt egy szamitogepre, amely Turing geppel elvegezheto szamolast vegez, es vilaghires leszel.
> de ha te ezt nem látod, én soha nem foglak tudni meggyőzni róla, mivel te azon az axiómán vagy, hogy semmi különbség a kettő között.
Pont forditott a szituacio: te posztulaltad az axiomadat, es en vagyok nyitott allasponton. Ha vegignezed a hozzaszolasaimat, sehol nem irtam, hogy az ember viselkedese Turing geppel modellezheto, en csak azt irtam, hogy egy Turing gep (tehat mai szamitogep) is kepes lehet szintetizalo gondolkodasra, azaz modellkbol axiomarendszereket absztrahalni es felulvizsgalni. Ez viszont tenyleg teny.
> Nem én kevertem a dolgokat, hanem te abban a hozzászólásban, amire válaszoltam
Ez nem igaz, te hozol elo ujra meg ujra irrelevans dolgokat.
> tanulni sosem késő
Retorikus fogas, ellenerv hianyaban. En, ellentetben veled, tudom, hogy mirol beszelek : ismerem a halmazelmelet axiomarendszeret, es tudom, hogy az aritmetikat es algebrat, hogy lehet ezeket a halmazelmelet keretein belul definialni. Arrol is van nemi sejtelmem, hogy az algoritmuselmeletnek mi a koze az aritmetikahoz, legalabbis, hogy te mire gondolhatsz, de nem akarok technikai reszletekbe menni, a dobalodzast altalad (latszolag) csak felszinesen ismert tenyekkel nyugodtan abbahagyhatod.
> Továbbá az, hogy egy probléma megoldására adható algoritmus
En azt hittem, hogy mi problema alatt azt ertjuk, hogy adott egy allitas egy axiomarendszerben, es dontsuk el, hogy az allitas igaz, hamis, vagy eldonthetetlen az axiomarendszerben.
Ebben az esetben nincs ertelme annak, hogy "egy problemara adunk algoritmust". Vagy megadjuk a bizonyitast, a cafolatot (a tagadas bizonyitasat), vagy ket modellt az axiomarendszerre, amiben teljesul, illetve nem teljesul az allitas, hogy jon ide az algoritmus?
A problema, hogy nem definialtuk, hogy mi ertunk problema alatt :) Ha ezt megtetted, definialhatnad, hogy mit ertesz egy "problema megoldasa", es a "problemara adott algoritmus" alatt. Bizonyos kontextusban ezeknek a kifejezeknek van ertelme, de egy meta-vitaban nincs ilyen kontextus, igy az ilyen lazasag csak kavarodast szul. Abban az esetben, persze, amikor a homaly keltes a cel, ez hasznos lehet.
Amit írsz az lépéseiben (mint elvonatkoztatások és egyszerűsítések) igaz, ugyanakkor semmi nem zárja ki, hogy a "létező dolgok valósága" ne lenne leképezhető rájuk. Másképp fogalmazva, nincs okunk feltételezni, hogy a "valóságosan létező dolgok" BÁRMELY aspektusa ne lenne / lehetne leképezhető mondjuk "bináris" rendszerre. (Ez a feltételezés egyébként (hallgatólagosan) elméleti és kísérleti megismerésünk hátterében is meghúzódik).
Az elmélei rendszereid, mindig rendszerek lesznek, de ezek csak a valóság modelljei, semmi több, pláne nem a valóság, a valóságnak mindig csak bizonyos, és néha nemis éppen ajellemző aspektusát írod le matematikailag, úgyhogy hogy lesz ez ellenérv arra, hogy pl. egy élő rendszer több, mint a matematikai modellje, nem értem, mert szerintem ez evidens dolog. Egyrészt a matematika már lényeges legegyszerűsítése a valóságnak, azon belül pedig a számítógépek és az algoritmusok egy további egyszerűsítés eredményei, már igen csak messze vannak minden valóságosan létező dologtól.
Az egy tény, hogy az emberek nem számítógépek, az hogy ebből hogyan következik, hogy többre képesek mint a számítógépek, én sem tudom, de ez is tény. Persze mondhatod, hogy amilyen teljesítményre képesek az emberek, arra számítógépek is ídővel képesek lesznek, csak elég bonyolult programot kell írni, ugyanis az emberi agyban az idegeknyulvényokba is csak elektromos impulzusok terjednek, ez megfelel a szilikoncsippekben terjedő impulzusoknak, semmi különbség a kettő között, és a mostani programok még ne érék el az agy "programjának" a bonyolultságát. Szerintem pedig alapvető különbség van, de ha te ezt nem látod, én soha nem foglak tudni meggyőzni róla, mivel te azon az axiómán vagy, hogy semmi különbség a kettő között.
Azért lenne egy kérdésem, te vizes leszel attól, hogy én itten már szinte teljesen tökéletesen ki tudok számolni egy vízmolekulát a nagyszámítógépünkön? Már egy vízmolekula is sokkal több, mint egy számítógépprogram, nem hogy egy egysejtű. Attól, hogy modellezel egy agyat teszem azt, attól az még nem lesz agy.
