Man möchte vermuten, daß jede präzise festgelegte Funktion auch berechenbar ist; leider ist das aber nicht der Fall. Das kann man folgendermaßen einsehen:

• Ein Algorithmus hat eine endliche Beschreibung über irgend einem endlichen Zeichensatz; es gibt abzählbar unendlich viele endliche Texte, und daher nur abzählbar viele Algorithmen-Beschreibungen. Daher gibt es erst recht nur abzählbar  viele berechenbare Funktionen.

• Betrachten wir die auf N definierten Funktionen f, die als Ergebnisse nur die Werte 0 oder 1 liefern; jede davon definiert eine Teilmenge Mf N derjenigen  Zahlen m N, für die f(m) = 1 ist. Umgekehrt gibt es für jede Teilmenge M N eine solche Funktion fM, die charakteristische Funktion der Menge M. Die Menge der Teilmengen M N ist aber überabzählbar,  ebenso also die Menge ihrer charakteristischen Funktionen; und damit die Menge aller  Funktionen erst recht.

Beispiele:

Die folgenden Funktionen wären von enormer praktischer Bedeutung, wenn sie berechenbar wären; aber das sind sie leider nicht:

• Das Halteproblem:  Sei A die Menge aller Algorithmus-Beschreibungen (es kommt nicht darauf an, über welchem Zeichensatz und in welchem Formalismus), und E die Menge aller möglichen Eingaben dafür. Die Funktion f: AE Boolean, welche f(a,e) = true  liefert, falls ein Algorithmus aA angewandt auf eine Eingabe eE terminiert, ist nicht berechenbar.

  Das wird in der Theoretischen Informatik bewiesen und bedeutet: es gibt kein allgemeines Verfahren, um zu entscheiden, ob ein gegebenes Programm bei einer vorgegebenen Eingabe anhalten wird.

• Das Äquivalenzproblem:  Die Funktion g: AA Boolean, welche g(a1,a2) = true  liefert, falls zwei Algorithmen a1 und a2 dieselbe Funktion berechnen, ist nicht berechenbar.

  Es ist also nicht allgemein entscheidbar, ob zwei Programme dasselbe tun.