Halting-problemet
Halting-problemet er et problem indenfor komputabilitetsteori. Problemet lyder:
"Eksisterer der en algoritme i Turing-maskinens komputationelle klasse, som kan afgøre, om en algoritme fra Turing-maskinens komputationelle klasse nogensinde stopper med et givet input?"
Alan Turing beviste i 1936 at en sådan algoritme ikke eksisterede i Turing-maskinens komputationelle klasse.
Kilder
[redigér | rediger kildetekst]- Moore, Cristopher; Mertens, Stephan (2011), The Nature of Computation, Oxford University Press, pp. 236–237, ISBN 9780191620805.
 | Spire Denne artikel om matematik er en spire som bør udbygges. Du er velkommen til at hjælpe Wikipedia ved at udvide den. |