Turingmaschine Typ 2

Eine Turingmaschine Typ 2 ist eine Erweiterung einer Turingmaschine. Sie entstand aus dem Bestreben heraus, das effektive Rechnen mit reellen Zahlen auf eine ähnlich verlässliche Grundlage zu stellen, wie dies für das Rechnen mit natürlichen Zahlen durch die Turingmaschine bereits gegeben ist. Man lässt als Ein- und Ausgaberaum jeweils sowohl endliche Zeichenketten als auch unendliche Zeichenketten zu. Es ergeben sich vier verschiedene Möglichkeiten:

• 1.: $\Sigma^*\longrightarrow\Sigma^*$
• 2.: $\Sigma^\omega\longrightarrow\Sigma^*$
• 3.: $\Sigma^*\longrightarrow\Sigma^\omega$
• 4.: $\Sigma^\omega\longrightarrow\Sigma^\omega$

Hierbei sind die Σ ^* die endlichen und Σ^ω die unendlichen Zeichenketten über einem geeigneten Alphabet Σ.
Dabei müssen 1. und 2. nach endlicher Zeit halten, 3. und 4. laufen unendlich lange, müssen aber auch unendlich oft etwas auf das Ausgabeband schreiben.
Des Weiteren darf man auf dem Eingabeband nur nach rechts gehen und nur lesen, und auf dem Ausgabeband nur schreiben und nur nach rechts gehen. So stellt man sicher, dass man nach einer endlichen Zeit bereits ein endliches Anfangsstück der Ausgabe erhält, das nicht mehr verändert wird.

Beispiele

• Aus 1. ergibt sich die klassische Turingmaschine.
• Die Maschinen zu 2. berechnen alle Arten von Test ( < , > , etc.)
• Zu 3. zählen unter anderem 0-stellige Maschinen, die eine Zahl berechnen (zum Beispiel π), oder auch Maschinen, die reelle Folgen $f:\subseteq\mathbb{N}\longrightarrow\mathbb{R}: f(n):=(a_n)_{n\in\mathbb{N}}$ (mit $a_n\in\mathbb{R}$) liefern (dann natürlich nicht 0-stellig).
• Zu 4. gehören dann solche Maschinen, die berechenbare, d.h. stetige, Funktionen

$f:\subseteq\mathbb{R}^n\longrightarrow\mathbb{R}$ verarbeiten können.

Darstellungen/Notationen

Um mit Turingmaschinen rechnen zu können, muss man die Objekte, auf denen gerechnet werden soll (zum Beispiel natürliche Zahlen, rationale Zahlen, reelle Zahlen, ...), für die Turingmaschine in geeigneter Form benennen. Für endlich darstellbare Objekte (wie zum Beispiel die natürlichen und rationalen Zahlen) reicht im Prinzip ein Zeichen. Man spricht hierbei von Notation.
Eine Notation einer Menge M ist eine surjektive (möglicherweise partielle) Funktion

$\nu:\subseteq\Sigma^*\longrightarrow M$.

Komplizierter wird es bei unendlichen Objekten (kontinuumsmächtigen Objekten). Hier benötigt man mindestens zwei Zeichen. Man spricht dann von Darstellung (bzw. Repräsentation).
Eine Darstellung einer Menge M ist eine surjektive (möglicherweise partielle) Funktion

$\delta:\subseteq\Sigma^\omega\longrightarrow M$.

Eine solche Darstellung der reellen Zahlen, die sich als sehr brauchbar erwiesen hat, ist die Cauchydarstellung der reellen Zahlen.

Cauchydarstellung der reellen Zahlen

Es sei Σ ein Alphabet mit mindestens zwei Zeichen und Σ^ω die unendliche Zeichenketten über dem Alphabet Σ. Es gelte per Definition $\bar{w_i}:=\nu_{\mathbb{Q}}(w_i)$, wobei $\nu_\mathbb{Q}$ eine Notation der rationalen Zahlen sei. Das heißt also, dass w_i eine endliche Zeichenkette ist und $\nu_\mathbb{Q}(w_i)$ die zugehörige rationale Zahl. Man sagt auch w_i ist der Name von $\nu_\mathbb{Q}(w_i)$.

ι ist eine Funktion, die endliche Zeichenketten eindeutig hintereinander schreibt.
$\rho_C :\subseteq \Sigma^\omega\longrightarrow \mathbb{R}$:
$\rho_{C}(p)=x:\Longleftrightarrow\exists w_0,w_1,\ldots\in$ Def$(\nu_{\mathbb{Q}})$, so dass
$p=\iota(w_0)\iota(w_1)\ldots$, und
$|\bar{w_i}-\bar{w_k}|\leq2^{-i}$ für i < k (Cauchykriterium)
und $x=\lim_{i\rightarrow\infty}\bar{w_i}$

Das heißt der Name einer reellen Zahl (bezüglich der Cauchydarstellung) besteht aus einer Folge rationaler Zahlen bzw. einer Folge der Namen rationaler Zahlen. Diese Folge konvergiert gegen die zu benennende reelle Zahl und zwar mit einer Mindestgeschwindigkeit (eine schnell konvergierende Folge). Diese Konvergenzgeschwindigkeit ist tatsächlich eine notwendige Voraussetzung, da nach endlicher Zeit etwas auf das Ausgabeband der Typ-2-Maschine geschrieben werden muss und nicht mehr verändert werden darf und so ein Mindestmaß an Information vorliegen muss. Dies wird durch das Cauchykriterium garantiert.
Aufgrund der Konstruktion sind nur abzählbar viele reelle Zahlen darstellbar.

Der Cantorraum

Um zu sehen, welche Art von Funktionen mit der Typ-2-Maschine berechenbar sind, führt man eine Metrik d_C auf Σ^ω ein (siehe auch Metrischer Raum):
Seien $p,q\in\Sigma^\omega$. Dann sei $d_C(p,q)=2^{\min\{i|p(i)\neq q(i)\}}$, falls $p\neq q$ und d_C(p,q) = 0 sonst. Damit wird (Σ^ω,d_C) zu einem metrischen Raum, dem Cantorraum. Es zeigt sich, dass so genau die stetigen Funktionen berechenbar sind.

Funktionendarstellung

Sei $A\subseteq\mathbb{R}^n$. Um mit einer stetigen Funktion $f:\subseteq A\longrightarrow\mathbb{R}$ auf einer Turingmaschine Typ 2 rechnen zu können, muss diese auch durch einen Namen dargestellt werden. Hierzu muss man noch eine Notation der offenen rationalen Kugeln einführen. Die Notation einer solchen n-dimensionalen offenen Kugel ist definiert durch:

$I^n\langle v,w\rangle:=B\left([\nu_\mathbb{Q}]^n(v),2^{-\nu_\mathbb{N}(w)}\right)$

Hierbei ist $\nu_\mathbb{Q}$ eine Notation der rationalen Zahlen, $\nu_\mathbb{N}$ eine Notation der natürlichen Zahlen und $B(x,\varepsilon):=\{y\in\mathbb{R}||x-y|<\varepsilon\}$ (die offenen Kugeln mit Radius ε). $\langle v,w\rangle$ ist die Cantorsche Tupelfunktion.
Weiterhin sei $C(A,\mathbb{R}):=\{f:\subseteq\mathbb{R}^n\longrightarrow\mathbb{R}|f$ ist stetig und Def(f) = A}.
Ein solcher Name kann folgendermaßen dargestellt werden (es gibt mehrere dazu äquivalente Darstellungen):

$\delta^A(p):=f\Longleftrightarrow$
$\exists v_0,v_1,\ldots\in Def(I^n)$ und $\exists w_0,w_1,\ldots\in Def(I)$
mit $p=\iota(\langle v_0,w_0\rangle)\iota(\langle v_1,w_1\rangle),\ldots$
und $\forall w\in Def(I^n)$ gilt
$f^{-1}[I^1(w)]=A\cap\bigcup_{\{i\in\mathbb{N}|w_i=w\}}I^n((v_i)$
für $p\in\Sigma^\omega, f:\subseteq\mathbb{R}^n\longrightarrow\mathbb{R}$ mit Def(f) = A.

Ein solcher Name einer Funktion f ist also eine Liste aller offenen Mengen f ^{− 1}[I¹(w)], bei der alle diese Mengen in dieser Liste als Vereinigung von Kugeln Iⁿ(v) aufgelistet werden.

Literatur

• Klaus Weihrauch: Computable Analysis. An Introduction. Springer, Berlin u. a. 2000, ISBN 3-540-66817-9, (Texts in theoretical Computer Science).
• B.M. Kapron: Polynomial Time Type-2 Computation
• O. Bournez/E. Hainry: An Analog Characterization of Elementary Functions Over the Real Numbers