Church (1936a, 1936b) and Turing (1936), inspired by techniques used by Gödel (1931) to prove his incompleteness theorems, independently demonstrated that the Entscheidungsproblem is not effectively decidable.
Church (1936a, 1936b) și Turing (1936), inspirați de tehnicile utilizate de către Gödel (1931) pentru a-și demonstra teoremele de incompletitudine, a demonstrat independent că problema deciziei nu este efectiv decidabilă.