Über die Theorie der Turing-Maschinen hinaus sind weitere Formalismen untersucht worden, um den Begriff der Berechenbarkeit genauer zu fassen, etwa die sog. Markoff-Algorithmen, oder die (partiell oder total) rekursiven Funktionen (mit unserer Definition von Rekursion haben sie nur am Rande zu tun). Hierher gehört auch die Frage nach der Entscheidbarkeit von Formalen Sprachen, also ob es für eine Formale Sprache ein Entscheidungsverfahren gibt.
Dabei hat sich herausgestellt, daß es zu jeder Grammatik von der Klasse 0 (also zu jeder Grammatik!) eine äquivalente Turing-Maschine gibt, und umgekehrt. Für die Klasse 1 kann man das Band sogar außerhalb der Eingabe abschneiden, und für die anderen Klassen ergeben sich noch stärkere Spezialisierungen der Maschinen, bis hin zu den endlichen Automaten.
Alle diese Untersuchungen haben immer denselben Berechenbarkeitsbegriff ergeben, und das führt auf die berühmte Church'sche These:
Jede berechenbare Funktion läßt sich programmieren.Diese These, von der es auch andere Formulierungen gibt, läßt sich nicht beweisen, weil die verwendeten Begriffe nicht präzise genug definiert sind. Sie ist heute dennoch allgemein akzeptiert.
Wichtig ist ihre Umkehrung:
Es gibt praktisch wichtige, wohldefinierte Probleme, die sich nicht entscheiden und nicht programmieren lassen.Dies mahnt zur Bescheidenheit; allerdings gibt es keinen Anlaß zur Resignation: wichtige und entscheidbare Probleme gibt es noch gerade genug!