imported>4uhrnachmittags: /* growthexperiments-addlink-summary-summary:1|0|0 */

2025-11-08T22:16:40Z

growthexperiments-addlink-summary-summary:1|0|0

Neue Seite

Eine '''Turingmaschine Typ 2''' ist eine Erweiterung einer [[Turingmaschine]]. Sie entstand aus dem Bestreben heraus, das effektive Rechnen mit [[Reelle Zahl|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:
# <math>\Sigma^*\longrightarrow\Sigma^*</math>
# <math>\Sigma^\omega\longrightarrow\Sigma^*</math>
# <math>\Sigma^*\longrightarrow\Sigma^\omega</math>
# <math>\Sigma^\omega\longrightarrow\Sigma^\omega</math>
Hierbei sind die <math>\Sigma^*</math> die endlichen und <math>\Sigma^\omega</math> die unendlichen Zeichenketten über einem geeigneten Alphabet <math>\Sigma</math>.
 
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 (<math><,></math>, etc.)
* Zu 3. zählen unter anderem 0-stellige Maschinen, die eine Zahl berechnen (zum Beispiel <math>\pi</math>), oder auch Maschinen, die reelle Folgen <math>f:\subseteq\mathbb{N}\longrightarrow\mathbb{R}: f(n):=(a_n)_{n\in\mathbb{N}}</math> (mit <math>a_n\in\mathbb{R}</math>) liefern (dann natürlich '''nicht''' 0-stellig).
* Zu 4. gehören dann solche Maschinen, die berechenbare, d. h. stetige, Funktionen <math>f:\subseteq\mathbb{R}^n\longrightarrow\mathbb{R}</math> 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 <math>M</math> ist eine surjektive (möglicherweise partielle) Funktion
:<math>\nu:\subseteq\Sigma^*\longrightarrow M</math>.

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 <math>M</math> ist eine surjektive (möglicherweise partielle) Funktion
:<math>\delta:\subseteq\Sigma^\omega\longrightarrow M</math>.
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 <math>\Sigma</math> ein Alphabet mit mindestens zwei Zeichen und <math>\Sigma^\omega</math> die unendliche Zeichenketten über dem Alphabet <math>\Sigma</math>. Es gelte per Definition <math>\bar{w_i}:=\nu_{\mathbb{Q}}(w_i)</math>, wobei <math>\nu_\mathbb{Q}</math> eine Notation der rationalen Zahlen sei. Das heißt also, dass <math>w_i</math> eine endliche Zeichenkette ist und <math>\nu_\mathbb{Q}(w_i)</math> die zugehörige rationale Zahl. Man sagt auch <math>w_i</math> ist der Name von <math>\nu_\mathbb{Q}(w_i)</math>.

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

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 <math>d_C</math> auf <math>\Sigma^\omega</math> ein (siehe auch [[Metrischer Raum]]):
 
Seien <math>p,q\in\Sigma^\omega</math>. Dann sei <math>d_C(p,q)=2^{\min\{i|p(i)\neq q(i)\}}</math>, falls <math>p\neq q</math> und <math>d_C(p,q)=0</math> sonst. Damit wird <math>(\Sigma^\omega,d_C)</math> zu einem metrischen Raum, dem ''Cantorraum''. Es zeigt sich, dass so genau die stetigen Funktionen berechenbar sind.

== Funktionendarstellung ==
Sei <math>A\subseteq\mathbb{R}^n</math>. Um mit einer stetigen Funktion <math>f:\subseteq A\longrightarrow\mathbb{R}</math> 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:
 
<math>I^n\langle v,w\rangle:=B\left([\nu_\mathbb{Q}]^n(v),2^{-\nu_\mathbb{N}(w)}\right)</math>
 
Hierbei ist <math>\nu_\mathbb{Q}</math> eine Notation der rationalen Zahlen, <math>\nu_\mathbb{N}</math> eine Notation der natürlichen Zahlen und <math>B(x,\varepsilon):=\{y\in\mathbb{R}||x-y|<\varepsilon\}</math> (die offenen ''Kugeln'' mit Radius <math>\varepsilon</math>). <math>\langle v,w\rangle</math> ist die [[Cantorsche Tupelfunktion]].
 
Weiterhin sei <math>C(A,\mathbb{R}):=\{f:\subseteq\mathbb{R}^n\longrightarrow\mathbb{R}|f</math> ist stetig und <math>Def(f)=A\}</math>.
 
Ein solcher Name kann folgendermaßen dargestellt werden (es gibt mehrere dazu äquivalente Darstellungen):
 
<math>\delta^A(p):=f\Longleftrightarrow</math>
 
<math>\exists v_0,v_1,\ldots\in Def(I^n)</math> und <math>\exists w_0,w_1,\ldots\in Def(I)</math>
 
mit <math>p=\iota(\langle v_0,w_0\rangle)\iota(\langle v_1,w_1\rangle),\ldots</math>
 
und <math>\forall w\in Def(I^n)</math> gilt
 
<math>f^{-1}[I^1(w)]=A\cap\bigcup_{\{i\in\mathbb{N}|w_i=w\}}I^n((v_i)</math>
 
für <math>p\in\Sigma^\omega, f:\subseteq\mathbb{R}^n\longrightarrow\mathbb{R}</math> mit <math>Def(f)=A</math>.
 
Ein solcher Name einer Funktion <math>f</math> ist also eine Liste aller offenen Mengen <math>f^{-1}[I^1(w)]</math>, bei der alle diese Mengen in dieser Liste als Vereinigung von Kugeln <math>I^n(v)</math> 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: [http://dimacs.rutgers.edu/Workshops/Programming/Report/bkapron.html '' Polynomial Time Type-2 Computation'']
* O. Bournez/E. Hainry: [http://www.loria.fr/publications/2004/A04-R-289/A04-R-289.ps ''An Analog Characterization of Elementary Functions Over the Real Numbers'']

[[Kategorie:Automatentheorie]]
[[Kategorie:Komplexitätstheorie]]
[[Kategorie:Berechenbarkeitstheorie]]

Turingmaschine Typ 2 - Versionsgeschichte

imported>4uhrnachmittags: /* growthexperiments-addlink-summary-summary:1|0|0 */