Entscheidungsproblem

Rövid szöveges bemutatás: 
A probléma magyarul az eldönthetőségi probléma. A probléma azt firtatta, hogy létezik-e a természetes számokkal foglalkozó tetszőleges (tehát igaz vagy hamis) állítását igazságát eldönteni képes algoritmus. Az algoritmus bemenete egy elsőrendű logikai állítás. Tehát az algoritmusnak gyakorlatilag azt kellet megvizsgálnia, hogy a bemenet levezethető-e a létező axiómákból.