O Problema da Terminação de Programas

Abstract

Neste artigo apresenta-se de forma simples e elementar a indecidi-
bilidade do Problema da Terminação de Programas apresentado por Turing
em 1936 em resposta ao Entscheidungsproblem de Hilbert. O resultado é
apresentado no contexto de programas imperativos modernos em arquitec-
tura de von Neumann, em vez de máquinas de Turing, para que o leitor
que conhece rudimentos de programação se sinta confortável. Discute-se o
impacto deste problema no desenvolvimento de aplicações computacionais.
Termina-se o artigo utilizando o resultado para construir um número real
não computável.