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

• 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.