Turing machine type 2

A Turing machine type 2 is an extension of a Turing machine . It arose out of the endeavor to put effective arithmetic with real numbers on a similarly reliable basis as is already given for arithmetic with natural numbers by the Turing machine. Both finite strings and infinite strings are permitted as input and output space. There are four different options:

1. ${\displaystyle \Sigma ^{*}\longrightarrow \Sigma ^{*}}$
2. ${\displaystyle \Sigma ^{\omega }\longrightarrow \Sigma ^{*}}$
3. ${\displaystyle \Sigma ^{*}\longrightarrow \Sigma ^{\omega }}$
4. ${\displaystyle \Sigma ^{\omega }\longrightarrow \Sigma ^{\omega }}$

Here are the finite and the infinite strings over a suitable alphabet . 1. and 2. must stop after a finite time, 3. and 4. run infinitely long, but also have to write something on the output tape an infinite number of times. Furthermore, you can only go to the right and only read on the input tape, and only write and only go to the right on the output tape. This ensures that after a finite amount of time you will already receive a finite initial section of the output that will no longer be changed. Examples ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \Sigma ^{\omega }}$ ${\displaystyle \Sigma }$

• From the first, the results classic Turing machine .
• The machines to 2. calculate all types of test ( , etc.) ${\displaystyle <,>}$
• To 3. count among other things 0-digit machines, which calculate a number (for example ), or also machines, which deliver real sequences (with ) (then of course not 0-digit). ${\displaystyle \pi }$ ${\displaystyle f:\subseteq \mathbb {N} \longrightarrow \mathbb {R} :f(n):=(a_{n})_{n\in \mathbb {N} }}$ ${\displaystyle a_{n}\in \mathbb {R} }$
• To 4. then belong those machines that are predictable, i. H. continuous, can process functions . ${\displaystyle f:\subseteq \mathbb {R} ^{n}\longrightarrow \mathbb {R} }$

Representations / notations

In order to be able to calculate with Turing machines , you have to name the objects on which you want to calculate (for example natural numbers, rational numbers, real numbers ...) for the Turing machine in a suitable form. For objects that can be represented finitely (such as natural and rational numbers), one symbol is sufficient in principle. One speaks here of notation.
A notation of a set is a surjective (possibly partial) function ${\displaystyle M}$

${\displaystyle \nu :\subseteq \Sigma ^{*}\longrightarrow M}$.

It gets more complicated with infinite objects (objects with continuum power). You need at least two characters here. One speaks then of representation (or representation).
A representation of a set is a surjective (possibly partial) function ${\displaystyle M}$

${\displaystyle \delta :\subseteq \Sigma ^{\omega }\longrightarrow M}$.

One such representation of real numbers that has proven very useful is the Cauchy representation of real numbers .

Cauchy representation of real numbers

Let it be an alphabet with at least two characters and the infinite strings above the alphabet . It applies by definition , where a notation of the rational numbers is. So that means that is a finite string and the associated rational number. They also say is the name of . ${\displaystyle \Sigma }$ ${\displaystyle \Sigma ^{\omega }}$ ${\displaystyle \Sigma }$ ${\displaystyle {\bar {w_{i}}}:=\nu _{\mathbb {Q} }(w_{i})}$ ${\displaystyle \nu _{\mathbb {Q} }}$ ${\displaystyle w_{i}}$ ${\displaystyle \nu _{\mathbb {Q} }(w_{i})}$ ${\displaystyle w_{i}}$ ${\displaystyle \nu _{\mathbb {Q} }(w_{i})}$

${\displaystyle \iota }$is a function that uniquely writes finite strings one after the other . : Def , so that , and for (Cauchy criterion) and
${\displaystyle \rho _{C}:\subseteq \Sigma ^{\omega }\longrightarrow \mathbb {R} }$
${\displaystyle \rho _{C}(p)=x:\Longleftrightarrow \exists w_{0},w_{1},\ldots \in }$ ${\displaystyle (\nu _{\mathbb {Q} })}$
${\displaystyle p=\iota (w_{0})\iota (w_{1})\ldots }$
${\displaystyle |{\bar {w_{i}}}-{\bar {w_{k}}}|\leq 2^{-i}}$ ${\displaystyle i<k}$
${\displaystyle x=\lim _{i\rightarrow \infty }{\bar {w_{i}}}}$

That is, the name of a real number (with regard to the Cauchy representation) consists of a sequence of rational numbers or a sequence of names of rational numbers. This sequence converges to the real number to be named and that with a minimum speed (a rapidly converging sequence). This speed of convergence is actually a necessary prerequisite, since after a finite time something has to be written to the output tape of the type 2 machine and may no longer be changed, so a minimum amount of information must be available. This is guaranteed by the Cauchy criterion.
Due to the construction, only a countable number of real numbers can be represented.

The Cantor room

To see what kind of functions can be calculated with the type 2 machine, one introduces a metric on (see also Metric space ): Be . Then be , if and otherwise. This becomes a metric space, the Cantor space . It turns out that the continuous functions can be calculated so precisely. ${\displaystyle d_{C}}$ ${\displaystyle \Sigma ^{\omega }}$
${\displaystyle p,q\in \Sigma ^{\omega }}$ ${\displaystyle d_{C}(p,q)=2^{\min\{i|p(i)\neq q(i)\}}}$ ${\displaystyle p\neq q}$ ${\displaystyle d_{C}(p,q)=0}$ ${\displaystyle (\Sigma ^{\omega },d_{C})}$

Function display

Be . In order to be able to calculate with a continuous function on a Turing machine type 2 , it must also be represented by a name . To do this, one has to introduce a notation of the open rational spheres. The notation of such an n-dimensional open sphere is defined by: Here is a notation of the rational numbers, a notation of the natural numbers and (the open spheres with radius ). is the Cantor tuple function . Furthermore, let is continuous and . Such a name can be represented as follows (there are several equivalent representations): and with and applies to with . Such a name of a function is a list of all open sets , in which all these sets are listed in this list as a union of spheres . ${\displaystyle A\subseteq \mathbb {R} ^{n}}$ ${\displaystyle f:\subseteq A\longrightarrow \mathbb {R} }$

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

${\displaystyle \nu _{\mathbb {Q} }}$ ${\displaystyle \nu _{\mathbb {N} }}$ ${\displaystyle B(x,\varepsilon ):=\{y\in \mathbb {R} ||x-y|<\varepsilon \}}$ ${\displaystyle \varepsilon }$ ${\displaystyle \langle v,w\rangle }$
${\displaystyle C(A,\mathbb {R} ):=\{f:\subseteq \mathbb {R} ^{n}\longrightarrow \mathbb {R} |f}$ ${\displaystyle Def(f)=A\}}$


${\displaystyle \delta ^{A}(p):=f\Longleftrightarrow }$
${\displaystyle \exists v_{0},v_{1},\ldots \in Def(I^{n})}$ ${\displaystyle \exists w_{0},w_{1},\ldots \in Def(I)}$
${\displaystyle p=\iota (\langle v_{0},w_{0}\rangle )\iota (\langle v_{1},w_{1}\rangle ),\ldots }$
${\displaystyle \forall w\in Def(I^{n})}$
${\displaystyle f^{-1}[I^{1}(w)]=A\cap \bigcup _{\{i\in \mathbb {N} |w_{i}=w\}}I^{n}((v_{i})}$
${\displaystyle p\in \Sigma ^{\omega },f:\subseteq \mathbb {R} ^{n}\longrightarrow \mathbb {R} }$ ${\displaystyle Def(f)=A}$

${\displaystyle f}$ ${\displaystyle f^{-1}[I^{1}(w)]}$ ${\displaystyle I^{n}(v)}$

literature

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