Vita:Turing-gép

Ez a szócikk témája miatt az Informatikai műhely érdeklődési körébe tartozik.
Bátran kapcsolódj be a szerkesztésébe! Jól használható Ez a szócikk jól használható besorolást kapott a kidolgozottsági skálán. Nélkülözhetetlen Ez a szócikk nélkülözhetetlen besorolást kapott a műhely fontossági skáláján. Értékelő szerkesztő: Zafir (vita), értékelés dátuma: 2012. május 20.

Informatikai szócikkek

Wikipédia:Cikkértékelési műhely/Index

Tekintsük a következő szimbólumkészletet és kódolást:

szimbólum	kód
0	0
1	10
,	110
bármi más	1110

Belátható, hogy a végtelen szalagra felírt kódokból a szimbólumok mindig visszaállíthatók.

Példa a 6,8 számpár ábrázolása binárisan 110,1000, kiterjeszett bináris jelölésben: ...01010011010000110...

Church-tézis (vagy Church–Turing-tézis): Ha egy algoritmus elég mechanikus és világos, akkor található olyan Turing-gép, amely azt végrehajtja.

A Turing-gép korlátozottság (egy jel, bináris, egy darab egydimenziós szalag) csak rossz hatásfokot eredményez, de mégis minden elérhető, amit elvileg el lehet érni.

A Turing-gép definiálja mindazt, amit matematikailag algoritmikus eljárás alatt értünk. Eddig minde másféle matematikai és informatikai modell, amit az algoritmikus problémamegoldás leírására és meghatározott lépésekben történő számítási eljárások vizsgálatára alkottak, ekvivalensnek bizonyult a Turing-géppel, azaz ha egy eljárást sikerült precízen leírni, akkor sikerült azt Turing-géppel is leírni.

Kiszámíthatóság

• Természetes számok: láttuk.
• Negatív számok: előjel.
• Véges törtek: kettedespont vagy / jel -> természetes számok
• Irracionális számok: pi, gyök 2

Van-e vajon olyan algoritmus (Turing-gép), amelyik a pi minden jegyét kiadja egymás után? Nem lehet, mert egy algoritmus nem futhat végtelen ideig. Amíg a Turing-gép meg nem állt (csengőszó!), addig a kimenet nem lehet biztos, nem vizsgálhatjuk meg. Más értelemben lehetséges: véges idő alatt kiadhatja az n-ik jegyét. Kiszámítható számok Megadható olyan algoritmus, amely a fentiek szerint teszőleges pontossággal elő tudja állítani. Nem kiszámítható számok Nem állíthatók elő semmilyen Turing-géppel A kiszámíthatóság persze nem csak számokra fontos, hanem mindenre, amely számokkal kódolható. Matematikai képletek, levezetések, természetes nyelvi szövegek... Turing-gépek kódolása Bármely Turing-gép leírható a kiterjeszett bináris jelöléssel. A szimbólumkészletet alkalmasan bővítjük: 0 = 0, 1 = 10, R = 110, L = 1110, S = 11110 A nyilak jelölésére nincs szükség. A fenti, UN+1 gép ábrázolása:

• Táblázattal: 00->00R, 01->11R, 10->01S, 11->11R
• Tömörítve: 00R11R01S11R,
• Kiterjeszett bináris jelöléssel: 00110101011010111101010110
• elhagyható a kezdő 00110, hiszen minden Turing-gép 00->00R kell kezdődjön, és a záró 110, mert az is közös.

Az eredményül kapott szám a Turing-gép sorszáma. Jelöljük az n-ik Turing-gépet Tn-nel. (Itt: 101011010111101010 = 177642. Meglepő, hogy egy ilyen egyszerű gépnek milyen nagy sorszáma van.) Belátható, hogy ha felsoroljuk a természetes számokat, akkor az összes Turing gépet (így az összes létező algoritmust is) felsoroltuk! Az algoritmusok száma végtelen, de megszámlálható (felsorolható)! Problémák

1. A legtöbb számhoz tartozó Turing-gép semmi értelmeset nem csinál. (Nem meglepő: a kódolt természetes nyelvi szövegeket tekintsük) Nézzük T0, T1 gépeket!
2. Sőt: van olyan, amelynek a leírása nem helyes, mert kerülhet olyan belső állapotba, amire nincs utasítása.
3. Vannak, amelyek ugyanazt csinálják, mint egy másik.
4. Vannak, amelyek soha nem állnak meg!
5. Lehetne javítani a kódoláson, hogy az átfedéseket és értelmetlenségeket csökkentsük. Ezt megtenni csak akkor érdemes, ha tényleg mindet ki tudjuk küszöbölni. (Ez viszont nem lehetséges.)

Univerzális Turing-gép Legyen m az input, p pedig az n-ik Turing-gép erre adott outputja: Tn(m) = p Értelmezzük a feladatot úgy, hogy a Turing-gépek definíciója egy olyan lgoritmus, amely megadja, mi az eredménye a fenti n,m számpárnak. Ez az algoritmus legyen az univerzális Turing-gép, jele U. Ennek a szalagon egy számpárt kell megadnunk, a szimulálandó Turing-gép sorszámát, és annak az inputját. U(n,m) = p Ez a gép természetesen megadható, mint egy Turing-gép, sorszáma is van. (Ez a bevezetett jelöléseinket alkalmazva egy decimálisan 180 jegyű szám.) U(n,m) = Tn(m) Hilbert eldönthetőségi problémája Létezik-e általános eljárás a matematikai problémák megoldására? Turing átfogalmazásában: megáll-e az n-ik Turing-gép, ha m-re hat? Ez a „Megállási probléma” Van-e tehát algoritmus bármely n,m számpárról eldönteni, hogy Tn(m) vagyis U(n,m) megáll-e valaha? Turing megmutatta, hogy nincs ilyen algoritmus. Hilbert problémájára tehát nincs megoldás. Figyelem: Nem mondtunk semmit az egyes konkrét algoritmusokról. Minden konkrét esetben elvileg eldönthető, hogy megáll-e vagy sem (van-e megoldás). De melyik algoritmust használjuk ennek eldöntésére? Erre nincs algoritmus! Konklúzió Az algoritmusok önmagukban nem döntik el a (matematikai) igazságot. Az algoritmusok érvényességét mindig külső eszközökkel kell megállapítani.

érdekesség

A Turing gép néhány változatát, valamint egy részben erre épülő történetet (ami mellesleg bemutatja a T.g. gyakorlati működését) tartalmaz Neal Stephenson Diamond Age c. könyve, mely ettől eltekintve is izgalmas olvasmány.

Nem ismerem, de megnézem. :-)) Gubb

Jegyzet magamnak: a definíciót mégis sürgősen át kell írnom. Külön input-és output tár feltevése klasszikus, egyszalagos Turing-gépnél nemhogy lehetséges, ámde kifejezetten helytelen. Nem definiálható az átmenetfüggvény. Gubb

Vagy mégis? Végül is amúgy is csak egy parciális függvény. Jajj, ez bonyolult lesz. Gubb

Ha nincs matematikai érv, jó lesz a történetisághez ragaszkodni. Gubb

Két link, amik mire mutatnak?

• Church fejtegetése, miszerint effektíve Turing gépe képes bármilyen számítást bármilyen nyelven
• Langton's ant, az egyszerű kétdimenziós Turing-gép

Javitasok

"Végül valamiért Turing koncepciója bizonyult a legsikeresebbnek."

Ez esetlen stilusu. Tovabba nem vilagos, hogy miben lett Turing legsikeresebb. Felesleges ilyen homalyos osszehasonlito ertekeleseket kiirni.

Abban, hogy a számításelméleti tankönyvek általában ezt tárgyalják először, és a számításelméleti dolgozatok többsége a Turing-gép paradigmájával fogalmazza meg a dolgait. A sikeresebb talán elterjedtebbre vagy közismertebbre vagy hasonlóra javítható. A többi algoritmusmodell az én tapasztalataim szerint kétségkívül kevésbé közismert, inkább csak a kutatók körében. Csak mostanában kezd a RAM-gép koncepciója a Turing-gép fölébe helyeződni; de igazából nincs olyan marha nagy különbség.

Es, muszaly ezt igy leirni? Plane ugy, hogy "vegul valamiert...." Az enciklopediaban relevans adatoknak kell szerepelni, nem annak, hogy ki milyen ismert, es hogy rejtelyes modon ismert. Ez nem blikk! --Math 2005. június 16., 13:32 (CEST)

Ez teljesen releváns is, mivel tényleg Turing koncepciója bizonyult a legsikeresebbnek; és a sikeresség valódi okairól nem ismerek tudományos elemzést. Ha ismersz, és tudod is idézni, akkor javítsd át a "valamiért" szót az okra. Addig az ok: ismeretlen. Ezen mit nem lehet érteni? Gubb

" További jelentőségét az ún. Church-Turing tézis adja, amely szerint univerzális algoritmikus modell. "

Ez viszont fontos volna, mert ez adja a Turing gep jelentoseget. --Math 2005. június 16., 13:20 (CEST)

Nem tudom, miért kifogásolod ezt, hogy nincs a cikkben, mivel benne van (a cikkhead 2. bekezdésének nálam a 4. sora). Gubb 2005. június 16., 13:27 (CEST)

Elneztem a laptortenetben torlest jelzett. Tenyleg ott van, megnezem, hogy mi tortent. --Math 2005. június 16., 13:34 (CEST)

Na megneztem. Azt hittem, hogy torolted az en hozzatetelem, de visszaraktad a te egyik torolt reszedet. Na akkor ennekindoklasa:

"vagyis nem egy valóságosan létező gép (bár működése szimulálható akár egyszerű PC-k segítségével is, sőt bizonyára egy konkrét Turing-gép megépítésének sincs semmi elvi akadálya). "

Ez megint esetlen.

Mi van ezen esetlen? Tökéletesen megfogalmazott, érthető magyar mondat, ami tényeket ír le. Ha definiálod nekem, hogy mi az "esetlen" benne, akkor tudom figyelembe venni. A Turing-gép mint informatikai koncepció, a mai Neumann-elvű számítógép egy egyszerűsített modellje. Ez tökéletesen igaz. Az is igaz azonban, hogy szimulálható a működése, és a megvalósításának sincs akadálya. Ez így kerek, így pontos, így egész: benne van a lényeg, aztán pedig árnyalódik. Gubb

Kesobb targyalod azt, hogy a Turing gep absztrakt modell, es lehet valodi automata is. Szerintem abban a reszben ird le mindegyik lehetoseget: valos fizikai automata, modell, szimulalt modell es, hogy a szamitogep maga egy turing gepnel nem sokkal tobb.

Miért tenném? Így sokkal jobb, a cikk így kerek, egész és ugyanakkor lényegretörő. Ráadásul épp arról van szó, hogy a Turing-gép NEM valós fizikai automata, hanem egy modell - noha a megvalósításának sincs akadálya - továbbra sem nem értem, ezen a mondaton mit nem lehet megérteni. Gubb

A bevezeto szakaszban nem kellene osszekavarni az olvasot. Ott irjunk csak annyit, hogy a Turing gep a szamitogep modelljes es szamitasi modell. Ez adja a dolog jelentoseget. --Math 2005. június 16., 13:39 (CEST)

Ez van leírva, ha figyelmesen elolvasod a cikkfejet és összeveted a két bekezdést. Az első bekezdésben nem is igazán a gép definíciója van benne, hanem a létrejöttének motivációja. A második bekezdés pedig a fenti kvázi-definíciót pontosabb szakkifejezésekkel mondja el, és valóban definíció. Gubb 2005. június 16., 14:16 (CEST)

Nem ertheto, hogy turing miben legsikeresebb. ha valaminek az okat nem ismerjuk, akkor egy lexikonban nem azt irjuk, "valamiert".

nem erted. a bekezdesben egyszerusiteni kell. nem szabad akarni ott elmondani mindent.osszezavaro, mert az olvaso ott meg nemerti.. math

Nem értem, amit most mondasz, de átírtam a kérdéses mondatot. Nézd meg, megfelelő-e. Azt hiszem, a történelmi rész kb. elején van valahol az átirat. Másrészt nem értem, miért ne írhatnánk, hogy "valamiért", ha egyszer ez az igazság, hogy nem tudjuk. Gubb

A Turing-gép fogalma annyiban "jobb", mondjuk a parciálisan rekurziív függvény fogalmánál, hogy könnyen lehetővé teszi a lépésszám definícióját, ami egyszerűen lehetetlen a másik definícióval. Mivel a hetvenes évektől egyre jobban kezdtek érdeklődni a különböző lépésszám problémák iránt (lehet-e lineárisan kiszámítani az n-edik Fibonacci-szám értékét) előtérbe került a Turing-gép definíciója.Kope 2005. június 17., 08:31 (CEST)

Köszönjük, ez logikusnak tűnik. Megpróbálom majd valahová beilleszteni a cikkbe. Gubb

Feljegyzés

Akkor ha minden igaz, már csak két-három dolgot kell javítani a cikken:

1. valószínű, hogy nem kell külön input és output ábécé, ezt majd alkalomadtán megnézem Turing cikkében, mivel az az eredeti koncepció.
2. A felsorolhatóságról szóló rész egyelőre gyenge, csak sejtet dolgokat, még nem volt időm befejezni. Gubb