Home -> Themen -> Funktionen


Turing-Werkstatt

Theoretische Informatik am PC


O.Pletsch 1862 Berechenbare Funktionen

Eine Funktion f : A -> B heißt berechenbar, wenn es eine Turing-Maschine M gibt, die zu jedem a aus A den Funktionswert f(a) berechnet.

Funktion

Beispiele :

  1. f : N -> N mit f(n) = 2n     Mal2.tm
  2. f : N x N -> N mit f(a,b) = a - b     Minus.tm
  3. f ordnet jedem Wort das gespiegelte Wort zu.    Reverse.tm

Download aller Beispiele

Man kann Funktionen definieren, die nicht berechenbar sind.
Im Thema Halteprobleme wird eine solche Funktion angegeben.