avgörbarhetsproblemet

das Entscheidungsproblem – frågan om det går att avgöra ifall ett matematiskt eller logiskt påstående är sant eller falskt på ett mekaniskt sätt (alltså med en algoritm) som ger rätt svar för alla mate­matiska och logiska påståenden. –– Pro­blemet fick sitt namn av den tyska ma­te­ma­tik­ern David Hilbert (1862——1942, se Wikipedialänk – se också Hilberts paradox), men andra filosofer och matematiker hade tänkt i samma banor tidigare. Ett annat sätt att se på saken är att fråga ifall det finns ett logiskt–matematiskt språk som kan användas för att formulera varje tänkbart problem, och som också kan användas för att räkna ut lösningen. Kurt Gödels ofullständighets­sats från 1931 visade indirekt att det inte går att avgöra, och något senare visade Alan Turing och Alonzo Church, obe­ro­ende av varandra och på olika sätt, att svaret på frågan är nej. Turings bevis innehöll beskrivningen av det som numera kallas för Turing­maskiner. (Avgörbarhetsproblemet kallas också för avgörandeproblemet.)

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

Dagens ord: 2013-05-05