Redaktion og opdatering af indholdet på denstoredanske.dk er indstillet pr. 24. august 2017. Artikler og andet indhold er tilgængeligt i den form, der var gældende ved redaktionens afslutning.

  • Artiklens indhold er godkendt af redaktionen

afgørbarhed

Oprindelig forfatter SAPe Seneste forfatter Redaktionen

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.

Annonce

Referér til denne tekst ved at skrive:
Stig Andur Pedersen: afgørbarhed i Den Store Danske, Gyldendal. Hentet 18. oktober 2019 fra http://denstoredanske.dk/index.php?sideId=33556