Turing-gép
A HupWiki-ből...
A Turing gép
Bertrand Russell és Alfred North Whitehead monumentális, 1910 és 1915 között publikált Principia Matematicája szerint a logika jelenti a matematikai igazság biztos, ellentmondásmentes alapját. Tévedtek, hiszen Kurt Gödel 1931-es (nem-teljességi) tétele kimondja: "a számelmélet összes axiomatikus megfogalmazása tartalmaz eldönthetetlen állításokat". Márpedig "ennek a számelméleti állításnak a Principia Matematica rendszerében nincs bizonyítása" (D. R. Hofstadter). Létezik-e - akár csak elméletileg - olyan módszer (algoritmus), mellyel az összes matematikai kérdés megoldható? - tette fel a (Gödel tételére rímelő) kérdést Turing. Az ember által végrehajtott, logikai alapokon nyugvó módszertani folyamatokat, illetve egy (elméleti) számítógép működését elemezve, jutott arra a következtetésre, hogy a szükséges algoritmus nem létezik. (Alonzo Church, amerikai logikus szintén 1936-ban dolgozta ki - Turing álláspontjával egyező - tézisét, azaz: "nincs csalhatatlan módszer arra, hogy megkülönböztessük a számelmélet tételeit azoktól az állításoktól, amelyek nem tételek".)
Az angol tudós mindezt a "kiszámítható számokról" szóló, 1936 decemberében megjelent dolgozatában vetette papírra. Különös írás. Szerzője - a matematikai problémán túllépve, azt általánosítva - a logikus és a fizikai folyamatok, gondolkodás és cselekvés szintézisére törekedett.
E célt szolgálta, az úgynevezett (Egyetemes) Turing-gép teóriája. Tulajdonképpen egy automatát, egyszerű számítógépmodellt képzelt el, amely három részből - belső állapotból: memóriából és utasításkészletből, érzékelő fejből, illetve négyzetekre osztott, elméletileg végtelen bemenő (input) szalagból - állna. A bemeneti jelek rendeltetését szabályok határozzák meg, majd a gép újabb jeleket (azaz számokba kódolt, standardizált utasításokat) ír a szalagra. Ha a szalag elegendő hosszúságú, bármi kiszámolható; az összes (jól-meghatározott) feladat, egyetlen (a szükséges programokkal ellátott) géppel. De hogyan rendszerezhetők, milyen szabályok alapján működnek a valóság matematikailag rendkívül nehezen vagy egyáltalán nem modellálható (uncomputable) szegmensei, például az emberi intuíció? E kérdésekre egy 1938-as esszében (Ordinal Logics) próbált választ adni, a későbbiekben viszont soha többé.
A negyvenes években, elektronikai ismeretekkel felvértezve, az elméleti számítógép gyakorlati megvalósításán munkálkodott. Már nem foglalkoztatta az, hogy mire képtelen a Turing-gép, hanem a benne rejlő lehetőségeket tanulmányozta. "Mintha egy agyat építenénk" - nyilatkozta. Elképzelhetőnek tartotta, hogy a jövőben (az ezredfordulóig bezárólag) mesterséges intelligenciát hozzunk világra. AI-t, amely átmenne a Turing-teszten. A korabeli neurológia, fiziológia eredményeire támaszkodva a mai neuronhálózatokat előlegező elméletet vázolt fel: ha egy mechanikus rendszer kellően komplex, akár a tanulás képességével is bírhat.
Turing koncepciója
- Külső adat és tárolóterület: végtelen szalag, amelynek egymás után cellái vannak, amelyek vagy üresek, vagy jelöltek.
- A gép egyszere egy cellával foglalkozik (Az író/olvasó feje egy cellán áll)
- A szalagon tud jobbra-balra lépni, tud jelet olvasni, törölni és írni. Az „üres" szalagon nincs jel. A jelet a továbbiakban 1-gyel, az üres cellát 0-val jelöljük.
- A bevitel, a számítás és a kivitel minden konkrét esetben véges marad, ezen túl a szalag üres.(0)
- A gép belső állapotait számozzuk meg 0,1,2,...
- A gép működését megadja egy explicit helyettesítési táblázat. Állapot, bemenet --> Állapot, kimenet, fejmozgás
A Turing gép használata
Tételezzük fel, hogy a gép mindig 0 belső állapotból indul, és a szalag a fejtől balra üres. Praktikus, ha a szalaggal összhangban az állapotokat is binárisan írjuk fel. A táblázat többi részét is meg tudjuk adni bináris számokkal. (Ez még nem az igazi, egy gép megadása így is n darab m hosszú szám sorozata)
Hogyan adjuk meg bemenetként számokat, vagy ezek sorozatát?
Unáris ábrázolás: az ábrázolni kívánt számnak megfelelõ számú jel. A számok végét 0 jelzi.
Példa: 6, 8 számpár: ...01111110111111110... A "..." a szalagon további végtelen 0-t jelent.
Példa Turing gépre
A következő turing gép egy unárisan ábrázolt számhoz hozzáad egyet:
UN+1: 00->00R, 01->11R, 10->01S, 11->11R
Bemenet: ...00111100... esetén a kimenet: ...001111100... lesz
A legegyszerűbb műveletekre is bonyolult, rossz hatásfokú gépek keletkeznek. A dolognak azonban nem gyakorlati jelentõsége van.
Kiterjeszett bináris jelölés
Az Unáris jelölés vizsgálataink szempontjából kényelmetlen. Jobb lenne valamilyen, a hagyományos bináris jelöléshez hasonló ábrázolás.
A hagyományos bináris jelölés önmagában nem elég, mert szükséges számok végét, vagy számok közötti elválasztásokat is jelölni. Több algoritmushoz szükséges lehet számsorozatok megadása (pl. euklidészi algoritmus)
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 - Turing tétel
Ha egy algoritmus elég mechanikus és világos, akkor bizonyára 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 elérhető, amit elvileg el lehet érni.
A Turing gép definiálja mindazt, amit matematikailag algoritmikus eljárás alatt értünk. Minden más algoritmikus eljárást végrehajtó rendszer ekvivalens valamely Turing-géppel.
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.
