Avgörbarhetsproblemet
From Wikipedia, the free encyclopedia
Inom matematik och datavetenskap är Avgörbarhetsproblemet eller Entscheidungsproblemet (av tyskans Entscheidung 'beslut') en fråga som ursprungligen formulerades av David Hilbert 1928:
” | Finns det en algoritm som tar en given utsaga inom första ordningens logik som indata (möjligen med ytterligare ett begränsat antal axiom förutom de vanliga axiomen i första ordningens logik) och svarar "Ja" eller "Nej" på frågan om den är sann för alla möjliga giltiga värden av variablerna i utsagan? | „ |
Enligt Gödels fullständighetssats för första ordningens logik är en utsaga universellt giltig om och endast om den kan härledas från dess axiom, så avgörbarhetsproblemet kan också ses som frågan om huruvida en utsaga är bevisbar utifrån axiomen eller inte.
År 1936 respektive 1937 publicerade Alonzo Church och Alan Turing oberoende av varandra artiklar som visar att en allmän lösning på avgörbarhetsproblemet inte existerar.[1] Dessa resultat är nu känd som Churchs teorem och Church-Turings hypotes. Avgörbarhetsproblemet har beröring med Hilberts tionde problem angående algoritmer för lösningar till Diofantiska ekvationer. Avsaknaden av någon sådan algoritm, fastställt av Yuri Matiyasevich 1970, innebär också ett negativt svar på avgörbarhetsproblemet.