computabiliteitstheorie
Computabiliteitstheorie is een onderdeel van de theoretische informatica dat bestudeert welke problemen algoritmisch oplosbaar zijn en hoe dit in formele modellen wordt vastgelegd. Centrale vragen zijn of er voor een gegeven probleem een algoritme bestaat dat altijd correct beslist, en waar de grenzen van berekenbaarheid liggen. Verschillende modellen worden gebruikt om berekeningen te modelleren, zoals Turingmachines, μ-recursieve functies en het λ-calculus; voor deze modellen geldt vaak dat ze dezelfde klasse berekenbare functies beschrijven, wat samenhangt met de Church-Turing-these: elke intuïtief berekenbare functie is berekenbaar door een Turingmachine (of door een equivalent model).
Een belangrijke scheiding is tussen beslisbare problemen, waarvoor een algoritme in finite stappen altijd ja of
Daarnaast spelen reducibiliteit en Rice's theorema een cruciale rol: vele onbeslisbare problemen kunnen worden gereduceerd tot