Problema de la parada

En teoria de la computabilitat el problema de la parada és un problema de decisió que es pot formular de forma informal:[1]

donada una descripció d'un programa i el seu estat inicial, determinar si el programa, quan executa aquesta entrada, s'atura (completa). L'alternativa és que funciona per sempre sense aturar-se

Alan Turing va provar el 1936 que un algorisme general per resoldre el problema de la parada per totes les possibles parelles programa-entrades no pot existir. Es diu que el problema de la parada és indecidible amb màquines de Turing.[2]

  1. ↑ Immerman, Neil. Computability and Complexity. Spring 2016. Metaphysics Research Lab, Stanford University, 2016. 
  2. ↑ Turing, A. M. «On Computable Numbers, with an Application to the Entscheidungsproblem» (en anglès). Proceedings of the London Mathematical Society, s2-42, 1, 1937, pàg. 230–265. Arxivat de l'original el 2019-06-27. DOI: 10.1112/plms/s2-42.1.230. ISSN: 0024-6115 [Consulta: 28 novembre 2018].