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. |
🔥 Top keywords: ForsideHelle Sara PetersSpeciel:SøgningEM i fodbold (mænd)Kasper HjulmandArnela MuminovićKylian MbappéSpeciel:Seneste ændringerAntoine GriezmannMartin BrygmannMikael JalvingParadise Hotel (Danmark, sæson 8)Maurits KjærgaardRomelu LukakuElisabeth WæverSlovenienVM i fodbold (mænd)Europamesterskabet i fodbold 2024 (mænd)Tour de France 2023Morten HjulmandSlovakietDanmarks fodboldlandsholdViggo MortensenChristian EriksenJosefine HøghDanmarkEuropamesterskabet i fodbold 2020 (mænd)Carsten EskelundJens Stryger LarsenFemern Bælt-forbindelsenThomas GravesenOkapiClaes AntonsenFlemming PovlsenPhilip Patrick WesthLudvig von KahlenMetallicaFrankrigs fodboldlandsholdRalf Rangnick