Først er der selve begrebet beregnelighed. Hvad kan (og hvad kan ikke) beregnes. Hvis vi til en begyndelse alene ser på endelige beregninger -- såsom de der normalt, når alt går vel, foreskrives af f.eks. Fortran programmer, ja så ser vi at dette spørgsmål blev hypotetisk besvaret i 1930rne. Da foreslog den engelske matematiker Alan Turing og den amerikanske matematiker Alonzo Church forskellige modeller for ``beregnings-maskiner''. Turing's blev kendt som Turing Maskinen, Church's som -kalkylen. Alt hvad der kan beregnes kan beregnes, blev tesen, enten vha. Turings Maskine eller ved evaluering af et udtryk i -kalkylen. Turing's og Church's arbejde falder indenfor meta-matematikken som igen måske bedst kan forstås som en afledning fra den matematiske logik. Derfor er en rimelig dyb indsigt i meta-matematik -- nærmere bestemt den rekursive funktionsteori -- en vigtig forudsætning for den teoretiske datalog.