Back مسألة توقف Arabic Стоп-проблем Bulgarian Problém zastavení Czech Halting-problemet Danish Halteproblem German Πρόβλημα τερματισμού Greek Halting problem English Problemo de halto Esperanto Problema de la parada Spanish مسئله توقف Persian
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]
- ↑ Immerman, Neil. Computability and Complexity. Spring 2016. Metaphysics Research Lab, Stanford University, 2016.
- ↑ 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].