Berechenbarkeit

Eine Funktion f : Nk -> N heißt berechenbar, falls es einen Algorithmus

gibt, der diese Funktion berechnet

Es gilt d ° c = id {0,1}*

und c ° d = id N,

wobei c eine Codierungs und d eine Dekodierunsfunktion ist

Bijektiv ist eine Funktion, wenn diese injektiv und surjektiv ist

Injektivität: Eine Funktion ist injektiv, wenn verschiedene Elemente der Definitionsmenge auf verschiedene Elemente der Zielmenge abgebildet werden. Anders ausgedrückt, es gibt keine zwei verschiedenen Elemente in der Definitionsmenge, die auf dasselbe Element in der Zielmenge abgebildet werden.

Surjektivität: Eine Funktion ist surjektiv, wenn jedes Element der Zielmenge durch mindestens ein Element in der Definitionsmenge abgebildet wird. Anders gesagt, es gibt keine "überschüssigen" Elemente in der Zielmenge, die nicht durch die Funktion erreicht werden.

Beweis von nicht berechenbaren Funktionen durch eine formale Maschine

Es gibt keinen Algorithmus, der in der Lage ist zu beweisen, dass ein Algorithmus terminiert oder nicht (hält)