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
- Moore, Cristopher; Mertens, Stephan (2011), The Nature of Computation, Oxford University Press, pp. 236–237, ISBN .
Spire Denne artikel om matematik er en som bør udbygges. Du er velkommen til at Wikipedia ved at udvide den. |