Turing teljesség bizonyítása?

ChatGPT 4o:

Ha egy számítógép csak összeadni képes, akkor az nem lehet Turing-teljes. Nézzük meg, miért, egyszerű és érthető magyarázattal, majd a bizonyítással.

# Turing-teljesség alapjai:

Ahhoz, hogy egy rendszer Turing-teljes legyen, három dologra van szükség:

- Adatok tárolása: A rendszer képes legyen információkat tárolni, például változókat vagy memóriahelyeket használva.

- Feltételes döntéshozatal: A rendszer tudjon dönteni bizonyos feltételek alapján (pl. „Ha X nagyobb, mint Y, akkor…”).

- Ciklusok: A rendszer képes legyen ismételten végrehajtani bizonyos műveleteket (pl. „amíg X nem lesz 10, addig...”).

Ha ezek közül bármelyik hiányzik, a rendszer nem lehet Turing-teljes.

Csak összeadás képessége:

# Ha egy számítógép csak összeadni tud, akkor:

- Adatok tárolása: Ez megvalósítható, például a számítás eredményeit tárolhatjuk.

- Feltételes döntéshozatal: Ez problémás, mert az összeadás önmagában nem elegendő ahhoz, hogy logikai döntéseket hozzunk, például egy "nagyobb-e?" összehasonlítást végrehajtsunk.

- Ciklusok: Mivel nincsenek feltételek, amikkel a ciklusokat vezérelhetnénk, ismétlés sem valósítható meg.

Tehát a rendszer képtelen bizonyos alapvető logikai műveletek végrehajtására, ami szükséges lenne a Turing-teljességhez.

# Egyszerű ellenérv:

Egy Turing-teljes rendszer képes megoldani bármilyen algoritmust, ha elegendő időt és memóriát biztosítunk. Ha azonban egy rendszer csak összeadásra képes, akkor például nem tud kivonást, logikai döntést vagy ciklust végrehajtani. Ez azt jelenti, hogy a rendszer funkciói túl korlátozottak ahhoz, hogy minden algoritmust megvalósítson.

Bizonyítás:

- Egy Turing-teljes rendszer képes szimulálni egy Turing-gépet.

- Egy Turing-géphez szükség van alapvető logikai műveletekre (pl. összehasonlításokra) és ciklusokra.

- Ha egy számítógép csak összeadni tud, akkor nem képes logikai műveletekre és feltételes vezérlésre.

- Tehát a rendszer nem képes szimulálni egy Turing-gépet, és így nem Turing-teljes.

# Összefoglalva:

Egy számítógép, amely csak összeadásra képes, nem lehet Turing-teljes, mert hiányzik belőle a feltételes döntéshozatal és az ismétlődő műveletek lehetősége.

Ha egy rendszer csak összeadásra képes, de rendelkezik ciklusokkal és feltételes elágazásokkal, akkor Turing-teljes lehet. Ez elsőre furcsának tűnhet, de nézzük meg lépésről lépésre!

Miért lehet Turing-teljes az összeadás-alapú rendszer?

1. Kivonás helyettesítése összeadással:

Bár nincs közvetlen kivonás, az összeadásból kivonás szimulálható. Például, ha negatív számokat használunk:

- A-B felírható úgy, hogy A számot összeadjuk a kivonandó, de már ezennel negatív B variánsával, azaz A+(-B). Példa: 20-10 = 20+(-10)

- Ha a rendszer nem támogatja a negatív számokat, ciklusokkal is megvalósíthatjuk: például ha B-t csökkentjük 1-gyel addig (az előző pont alapján), amíg 0 nem lesz, és közben A-t is csökkentjük (az előző pont alapján).

2. Szorzás helyettesítése ismételt összeadással:

Szorzás is összeadások sorozatára bontható:

- A*B megvalósítható úgy, hogy A-t hozzáadjuk önmagához B-szer.

3. Oszthatóság helyettesítése ismételt kivonással:

Az osztás is szimulálható ismételt kivonásokkal, vagyis összeadás helyettesítésének megfelelőjével. Egyszerűsítés kedvéért kivonás fogalmát használom:

Ha A-ból kivonjuk B-t addig, amíg A kisebb, mint B, akkor megszámolhatjuk, hányszor vontuk ki, ami az osztás eredménye, míg a megmaradt A lesz a maradék.

4. Memória és logika biztosítása:

Ha a rendszer rendelkezik elágazással (például „ha-akkor” utasítással) és ciklusokkal („amíg” vagy „for” ciklusok), ezekkel vezérelni tudjuk a fent említett folyamatokat.

Ezennel teljesül a Turing-teljesség követelményei, ami a következők:

Turing-teljesség követelményei:

- Adattárolás: Egy számítógépnek vagy rendszernek képesnek kell lennie értékek tárolására és manipulálására.

- Ciklusok: A rendszer képes legyen bizonyos műveleteket ismételni.

- Feltételes döntéshozatal: A rendszer képes legyen eldönteni, hogy egy feltétel teljesül-e, és aszerint hajtson végre különböző műveleteket.

- Teljes aritmetikai kifejezések szimulálása: Minden számítást (pl. kivonás, szorzás) végső soron az összeadásra vezethetünk vissza.

Hogy az adott számítógép processzorral rendelkezik vagy ezt helyettesítő kézi meghajtással történik az rendszer végrehajtási ütemezése az Turing-teljességen nem változtat. Akár, lehet teljesen mechanikus áram-mentes rendszer is, ha valamilyen módon a fenti műveleteket valamilyen reprezentációban tárolni vagy végrehajtani tudja. (pl.: lásd egyszerűbb példát mechanikus számológépek)

Nem, nincs értelme további összehasonlítást végezni az alacsonyabb helyi értékű biteken, ha az A-ra és B-re vonatkozó megadott feltételek teljesülnek. Ezért:

- MSB (legfelső helyi értékű bit): A legfelső bit a szám előjelét jelzi, ha a számokat aláírt (signed) formátumban kezeljük.

* Ha az A-ban az MSB 11, akkor A negatív szám.

* Ha a B-ben az MSB 00, akkor B pozitív szám.

Aláírt számok esetén mindig igaz, hogy minden negatív szám kisebb minden pozitív számnál. Ez független az alacsonyabb helyi értékű bitektől, mert az MSB dominál a szám nagyságának meghatározásában.

Következmény:

- Ha A-ban az MSB 11 és BB-ben az MSB 00, akkor:

* A<B minden esetben.

* Az alacsonyabb helyiértékű bitek összehasonlítása nem változtat az eredményen, így erre nincs szükség.

Példa:

A = 10000001A=10000001 (aláírt érték: −127−127)

B = 01111111B=01111111 (aláírt érték: +127+127)

Itt az MSB alapján azonnal megállapítható, hogy A<BA<B, további bitvizsgálat nélkül.