Lógicas e máquinas – parte III

– Referências e Errata

• Turing, Alan M. On Computable Numbers, with an Application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, 42(1): 230–265, 1936.
• O problema da decisão (Entscheidungsproblem) foi enunciado em Grundzüge der Theoretischen Logik em 1928, por Hilbert e Ackerman. O Entscheidungsproblem é mais amplo que o problema de encontrar certas soluções para uma classe de equações diofantinas. Esse último ficou conhecido como o décimo problema de Hilbert, e já havia sido enunciado no começo do século XX. Naturalmente, uma resposta positiva ao Entscheidungsproblem acarretaria em uma resposta positiva ao décimo problema, mas não vice-versa. Uma resposta negativa para o décimo problema só foi publicada nos anos 1970.