Etikett: 42

(the halting problem) – frågan om det på förhand går att räkna ut ifall en körning av ett datorprogram kommer till ett slut någon gång, eller om beräkningen fortsätter i all evighet. – Alan Turing† bevisade i sin berömda artikel ”On computable numbers with an application to the Entscheidungsproblem” (länk) från 1936 att uppgiften är olöslig. – Observera att detta gäller när frågan ska besvaras enbart med mekaniska metoder och för varje tänk­bar beräkning. En matematiskt kunnig mänsklig bedömare kan ofta avgöra ifall en beräkning kommer att fortsätta i evighet eller om den tar slut någon gång, men stopproblemet gäller ifall man kan programmera en dator så att den avgör saken i alla tänkbara fall och utan mänsklig hjälp. – Vi vet till exempel att om vi sätter en dator att räkna ut det exakta värdet på pi så kommer den aldrig att bli klar, men det ”vet” inte datorn. Att det är så har mänskliga matematiker räknat ut, och det har de inte gjort genom att räkna på pi oändligt länge. Hur länge man än räknar på värdet av pi så får man nämligen inte, enbart genom att fortsätta räkna, någon information om ifall räknearbetet tar slut någon gång, eller aldrig tar slut. – I uppsatsen ”On computable numbers…” beskrev Turing också det som senare blev känt som Turing­maskinen. – Några månader före Turing hade Alonzo Church† bevisat samma sak, fast utan att beskriva en maskin. – Stopproblemet är besläktat med avgörbarhetsproblemet (das Entscheidungsproblem), men också med Kurt Gödels† ofullständig­hets­sats. – Läs också om omega (Chaitins konstant).

[datorvetenskap] [matematik och logik] [ändrad 6 juni 2017]