Halting-problemet

Fra Wikipedia, den frie encyklopædi
Gå til: navigation, søg

Halting-problemet er et problem indenfor komputabilitetsteori. Problemet lyder:

"Eksisterer der en algoritme i Turing-maskinens komputationelle klasse, som kan komputerer 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.
Artikelstump Stub
Denne artikel er kun påbegyndt. Hvis du ved mere om emnet, kan du hjælpe Wikipedia ved at udvide den.