5.4. Megállási probléma

Az előzőekben láttuk, hogy a feladatok túlnyomó többsége algoritmikusan nem megoldható, és általában annak eldöntése, hogy egy feladat algoritmikusan megoldható-e egyáltalán nem nyilvánvaló. A kérdéskört tovább vizsgálva az a természetes gondolat vetődik fel az emberben, hogy ha ennyire általános feladat nem is, de talán az megoldható, hogy egy konkrét Turing-gépről és egy szóról megállapítsuk, hogy a elfogadja-e -t vagy sem. Másképpen: el tudjuk dönteni, hogy egy adott algoritmus megold-e egy konkrét problémát vagy sem. Ennek vizsgálatához először is pontosan meg kell fogalmaznunk, a megoldandó feladatot.

5.21. Megállási probléma

Döntsük el a  programjával adott  Turing-gépről és  szóról, 
hogy  megáll-e a  bemeneten vagy sem.

A megállási problémának két alapvető megközelítése létezik: egy-egy konkrét esetre, vagy teljesen általánosan szeretnénk erre választ adni.

Az első esetben egyszerűbb a dolgunk, hiszen egyedi módszereket alkalmazhatunk minden alkalommal, speciálisan az adott problémához igazítva.

A második eset sokkal bonyolultabbnak tűnik, hiszen olyan bizonyítási eljárást kell találnunk, amelyik minden Turing-gépre és bemenetre működik. Mivel a bizonyítás lényegében logikai lépések sorozata, így lényegében egy egységes módszert - algoritmust - kell találnunk, ami eldönti az argumentumairól, hogy megfelelnek vagy sem. Ennek alapján a probléma általános megoldhatóságáról a következő állítást fogalmazhatjuk meg és bizonyíthatjuk be.

5.22. Tétel

Nem létezik olyan Turing-gép, amelyik minden  programjával adott
  Turing-gépről és t szóról eldönti, hogy  megáll-e a
  bemeneten vagy sem.

Bizonyítás

A tételt indirekt módon igazoljuk.

Tegyük fel, hogy létezik Turing-gép, amelyik minden programjával adott Turing-gépről és szóról eldönti, hogy megáll-e a bemeneten vagy sem. Ha megáll a bemeneten , egyébként válasszal tér vissza. Az egyszerűség kedvéért azt is feltételezhetjük, hogy bemenetét alakban adjuk meg.

A korábbi jelöléseknek megfelelően legyen

- az univerzális Turing-gép,

- egy Turing-gép, ami az . szalag tartalmát az . szalagra írja.

Definiáljuk -t a következőképpen:

pontosan azokat a szavakat fogadja el, amelyeket , azaz , hiszen azokat a szavakat, amelyeken meg sem áll természetesen nem fogadja el . Mivel már csak azokat a -ket engedi át bemenetként számára, amelyekről kiderítette, hogy meg fog állni rajta, ezért a hátralevő számítás mindenképpen befejeződik, azaz minden bemenő szón megáll. Ez azt jelentené, hogy , amiről már beláttuk, hogy nem igaz. Az ellentmondás oka a hibás (indirekt) feltételezésünk. ✓

Az eldönthetőségi problémának megfogalmazható egy egyszerűbb változata is.

5.23. Megállási probléma 2

Döntsük el a  programjával adott  Turing-gépről, hogy megáll-e az 
üres bemeneten vagy sem.

Bár lényegesen egyszerűbbnek tűnik, erre a feladatra is hasonló állítást lehet bizonyítani.

5.24. Tétel

Nem létezik olyan Turing-gép, amelyik minden  programjával adott
  Turing-gépről eldönti, hogy  megáll-e a  bemeneten vagy sem.

Bizonyítás

A tételt most is indirekt módon igazoljuk.

Tegyük fel, hogy létezik Turing-gép, amelyik minden programjával adott Turing-gépről eldönti, hogy megáll-e bemeneten vagy sem.

Legyen egy olyan Turing-gép, amelyik a bemenő szalagjára felírja a $ szót. Nagyon egyszerű ilyen Turing-gépet létrehozni, hiszen csak darab állapot kell hozzá, például , az átmenetfüggvénye pedig úgy definiálható, hogy ahol , ha $i$ páratlan és , ha páros.

Legyen egy olyan Turing-gép, ami a bemenő szóhoz elkészíti programját. A konstrukció során a további szokásos Turing-gépeket fogjuk használni:

- egy Turing-gép, ami az . szalag tartalmát az . szalagra írja

- az . szalag végétől indulva az első talált jelig átmásolja a talált szimbólumokat az . szalagra

- az . szalag végétől visszatöröl az első megtalált jelig. (A szimbólumot is törli.)

- ha az .és . szalagon a és Turing-gép programok találhatók, előállítja az . szalagra a Turing-gép programját. Ez szintén nem bonyolult feladat, hiszen lényegében csak össze kell fűzni a két programot, illetve az első végállapotaiból a második kezdőállapotába való átmenetet kell definiálni.

Ezek után definiáljuk -t a következőképpen:

Világos, hogy minden bemeneten megáll.

Ha bemenetként egy alakú szót adunk meg, akkor a következőket csinálja:

1. átmásolja -t a . szalagra,

2. a . szalag utáni részét, azaz -t átmásolja az . szalagra

3. az első szalagon -hez elkészíti a Turing-gép programját.

4. a . szalagon eltávolítja a utáni részt, azaz csak marad

5. az . és . szalagon levő Turing-gép programokból elkészíti az . szalagra az összefűzött programot.

6. megvizsgálja, hogy az . szalagon levő Turing-gép megáll-e az üres bemeneten.

Az 5. lépésben létrehozott Turing-gép működése olyan, hogy ha bemenetként az üres szót kapja, akkor először felírja a szalagjára a szót, majd úgy működik, mint az eredeti . Vagyis pontosan akkor áll meg az üres bemeneten, ha megáll a bemeneten.

Ez azt jelenti, hogy pontosan azokat a szavakat fogadja el, amelyekre megáll -n. Ekkor viszont megoldaná az általános megállási problémát, amiről az előző tételben bizonyítottuk, hogy lehetetlen. Az ellentmondás oka az indirekt feltételezésünk.