En 1936, de manera independiente, Alonzo Church y Alan Turing demostraron ambos que es imposible escribir tal algoritmo.
Como consecuencia, es también imposible decidir con un algoritmo si ciertas frases concretas de la aritmética son ciertas o falsas.
La pregunta se remonta a Gottfried Leibniz, quien en el siglo XVII, después de construir exitosamente una máquina mecánica de cálculo, soñaba con construir una máquina que pudiera manipular símbolos para determinar si una frase en matemáticas es un teorema.
La respuesta negativa al Entscheidungsproblem fue dada por Alonzo Church en 1936 e independientemente, muy poco tiempo después por Alan Turing, también en 1936.
Es importante notar que si se restringe el problema a una teoría de primer orden específica con constantes, predicados constantes y axiomas, es posible que exista un algoritmo de decisión para la teoría.