Koncepció
Megállási probléma (megállási probléma) jelenleg a hangsúly a logika, és a harmadik matematikai válság megoldása. Ennek lényege a kérdés: Adott egy T Turing-gépet, és egy tetszőleges nyelv S halmaz, ha T végül megáll mindegyik. Jelentése lehet meghatározni ugyanazon a nyelven. Természetesen bármely véges S eldönthető jellegű, megszámlálható (megszámlálható) S is leállás az input segítségével az Oracle.
Népszerű, hogy a megállási probléma annak eldöntése, hogy valaki program keretében kötött, korlátozott ideig fut a problémát. Ha ezt a problémát meg lehet oldani egy korlátozott ideig, akkor van egy program, annak megállapítására, hogy le fog állni a saját, és a másik viselkedését. Nyilvánvaló, hogy ez alkalommal nem számít, milyen az eredmény a megállási probléma nem felel meg a követelményeknek. Tehát ez egy megoldhatatlan probléma.Le jellege a probléma elsőrendű logika nem következetes és hiányosság. Hasonló kijelentések is borbély paradox, a Mindenható paradoxon, stb
Bizonyíték
Először is, azt állapítjuk meg, hogy egy programot le fog állni, a következőket jelenti: bármely egyik bemenet, annak megállapítására, hogy lefelé. Feltételezzük, hogy van egy ilyen Turing-gép, set H. Kérheti, hogy meg munkájukat: Ha valaki program leállt a termelés 1 M, egyébként kimenet 0 (mert eldönthető). Tudod építeni egy másik program D, amely a következőképpen működik: a H kimenet bemenet, ha a bemenet egy leállás, különben leáll.
H lehet meghatározni, mert az összes programot, akkor azt is meg lehet határozni D, ha azt állapítjuk meg, D bemenet 1 ütköző, a kimenet értéke 0, és D definíciója, mivel ismert, hogy le, és vice versa. Ezért nem algoritmus megoldására megállási probléma.
|
