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öntheto, hogy megáll-e vagy sem (van-e megoldás). De melyik algoritmust használjuk ennek eldöntésére? Erre nincs algoritmus!

Tg-nek megállási problémája: minden -e T tg. amelyik tetszoleges T’ tg és tetszoleges w szó esetén eldönti, hogy a T’ megáll-e w-n.
Tétel: a megállási probléma nem oldható meg (nem minden T)
Bizonyítás: indirekt, tegyük fel hogy, minden T ez el tudja dönteni minden T’-rol, hogy megáll-e P’-n( T’ programja) T bol megalkotunk eg T1-t amelyikminden áll meg(igen válaszol ) minden P’-n ha T’ nem áll meg P’-n. L={w w-t T1 elfogadja} erre L=D minden T1 :D felismero tg. (diagonikus nyelv). Ilyen nincs ellentmondás nem minden T

Tétel: Az egyszerusített megállási probléma (w=lambda ) nem oldható meg tg.el