Die (intuitiv) berechenbaren Funktionen sind gerade die von einer universellen Turingmaschine berechenbaren. Turingmaschinen können genau die Typ-0-Sprachen akzeptieren. Das Halteproblem von Turingmaschinen ist nicht entscheidbar, aber semi-entscheidbar. Das heißt, es gibt Sprachen, deren Wortproblem nur semi-entscheidbar ist, ihre charakteristische Funktion aber berechenbar.