Berechenbarkeitsbegriff

Eine (eventuell partielle) Funktion $f:{\mathbb{N}}^k\to \mathbb{N}$ heißt berechenbar, wenn es einen endlichen Algorithmus $\mathcal{A}$ gibt, sodass für alle $n_1,\dots ,n_k,m\in \mathbb{N}$ gilt:

Wichtige Punkte:

• Partielle Funktion: Wenn $f$ für eine Eingabe nicht definiert ist, muss der Algorithmus $\mathcal{A}$ für diese Eingabe nicht halten (er darf in eine Endlosschleife geraten).
• Endlicher Algorithmus: Die Beschreibung des Algorithmus selbst muss endlich sein.
• Endliche Zeit: Wenn die Funktion definiert ist, muss der Algorithmus nach endlich vielen Schritten terminieren.
• Existenzielle Aussage: Um zu zeigen, dass eine Funktion berechenbar ist, genügt es, die Existenz eines einzigen solchen Algorithmus nachzuweisen.