afgørbarhed

Afgørbarhed, mange logiske og matematiske problemer består i at afgøre, om et objekt fra en given klasse har en given egenskab eller ej. Det er fx et matematisk problem at afgøre, om et givet naturligt tal er et primtal eller ej.

Problemet kaldes afgørbart, hvis der findes en metode, som — anvendt på et vilkårligt objekt fra klassen — afgør, om objektet har egenskaben eller ej. Et logisk problem kan fx være en afgørelse af, hvorvidt et givet udsagn i et formelt sprog er sandt eller falsk. I begyndelsen af 1930'erne blev det påvist, at mange logiske og matematiske problemer er uafgørbare.

Således beviste Kurt Gödel, at meget simple formelle teorier vil være uafgørbare, og det er påvist, at det samme gælder problemet, om en algoritme vil stoppe eller ej.