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 matematiska och logiska påståenden. – Problemet fick sitt namn av den tyska matematikern David Hilbert (1862—1942, se Wikipedia – 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ändighetssats från 1931 visade indirekt att det inte går att avgöra, och något senare visade Alan Turing† och Alonzo Church†, oberoende 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 Turingmaskiner. (Avgörbarhetsproblemet kallas också för avgörandeproblemet.)
[matematik och logik] [ändrad 6 juni 2017]