Berechenbarkeit < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo
Wie ist der Begriff Berechenbarkeit einer Funktion in der Mathematik beschrieben. Kann mir das einer erklären.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:06 Mi 01.04.2009 | | Autor: | Rino |
Wir haben in "Berechenbarkeitstheorie" Berechenbarkeit wie folgt definiert:
Eine Funktion [mm] $f:\IN\to\IN$ [/mm] heißt (Turing-)berechenbar, falls eine Turningmaschine $T$ existiert, die bei Eingabe von [mm] $n\in \IN$ [/mm] terminiert und nach Terminierung von $T$ $f(n)$ auf dem Band steht
|
|
|
|
