Uberegnelige funktioner: Forståelse af grænserne for beregning

I beregningsteorien kaldes en funktion uberegnelig, hvis den ikke kan beregnes af nogen algoritme. Der er med andre ord ingen procedure, der kan anvendes på inputdata for at producere output fra funktionen.

Et eksempel på en ikke-beregnelig funktion er stopproblemet, som spørger, om et givet program til sidst vil stoppe (stoppe med at køre) eller forts
tte med at køre på ubestemt tid. Denne funktion er uberegnelig, fordi der ikke er nogen generel algoritme, der kan afgøre, om et givent program vil stoppe eller ej.

Andre eksempler på ikke-beregnelige funktioner omfatter Busy Beaver-funktionen, som spørger, hvor mange trin en given Turing-maskine vil tage, før den stopper, og Entscheidungsproblem, som spørger, om et givet formelt system er konsekvent eller inkonsekvent. Disse funktioner er også uberegnelige, fordi de ikke kan beregnes af nogen algoritme.

Sammenfattende er uberegnelige funktioner funktioner, der ikke kan beregnes af nogen algoritme, og de bruges ofte til at demonstrere begr
nsningerne ved beregning og vigtigheden af beregningskompleksitetsteori.