Halting-problemet

Fra Wikipedia, den frie encyklopædi
Spring til navigation Spring til søgning

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 | redigér wikikode]

  • Moore, Cristopher; Mertens, Stephan (2011), The Nature of Computation, Oxford University Press, pp. 236–237, ISBN 9780191620805.
ArtikelstumpSpire
Denne artikel er en spire som bør udbygges. Du er velkommen til at hjælpe Wikipedia ved at udvide den.