Namespaces
Variants
Actions

Difference between revisions of "User:Joachim Draeger/sandbox"

From Encyclopedia of Mathematics
Jump to: navigation, search
Line 1: Line 1:
  
{{MSC|68Q05}}  
+
{{MSC|68Q05}}
  
 
{{TEX|done}}
 
{{TEX|done}}
Line 6: Line 6:
 
The universality property of Turing machines states that it exists a Turing machine, which can simulate the behaviour of each other Turing machine. This property is of great practical importance. It says that a Turing machine can be adapted to different tasks by ''programming''; from the viewpoint of computability it is not necessary to build special-purpose machines.
 
The universality property of Turing machines states that it exists a Turing machine, which can simulate the behaviour of each other Turing machine. This property is of great practical importance. It says that a Turing machine can be adapted to different tasks by ''programming''; from the viewpoint of computability it is not necessary to build special-purpose machines.
  
===Universality of Turing Machines===
+
===Definition of Universality===
  
 
A [[Turing machine]] $T=(Q,\Sigma,\Gamma,\sqcup,q_0,q_f,\delta)$ can be interpreted as partially defined function
 
A [[Turing machine]] $T=(Q,\Sigma,\Gamma,\sqcup,q_0,q_f,\delta)$ can be interpreted as partially defined function
 
$$F_T\colon\Sigma^\ast \longrightarrow \Sigma^\ast; i \mapsto
 
$$F_T\colon\Sigma^\ast \longrightarrow \Sigma^\ast; i \mapsto
\begin{cases} j &  
+
\begin{cases} j &
\text{$T$ stops in the final state $q_f\in Q$ with output $j$} \\  
+
\text{$T$ stops in the final state $q_f\in Q$ with output $j$} \\
\bot & \text{otherwise} \end{cases}$$  
+
\bot & \text{otherwise} \end{cases}$$
Using $F_T$, we are introducing the notions of simulation and universality. A Turing machine $U$ ''simulates'' a Turing machine $T$, if $\exists t\in\Sigma^\ast \forall s\in\Sigma^\ast \colon F_U(t, s) =F_T(s)$. The Turing machine $U$ is called ''universal'', if it can simulate every Turing machine $T$.
+
The definition can be generalized to multiple arguments in a canonical way. Using $F_T$, we are introducing the notions of simulation and universality. A Turing machine $U$ ''simulates'' a Turing machine $T$, if $\exists t\in\Sigma^\ast \forall s\in\Sigma^\ast \colon F_U(t, s) =F_T(s)$. The Turing machine $U$ is called ''universal'', if it can simulate every Turing machine $T$.
  
===Existence of a universal Turing Machine===
+
===Existence of an Universal Turing Machine===
  
Via [[Gödelization]] it can be proven that a  
+
Via [[Gödelization]] it can be proven that a universal Turing machine $U$ exists. For reasons of simplicity we will assume that $U$ uses the same input/output- and band alphabet as the machine $T=(Q,\Sigma,\Gamma,\sqcup,q_0,q_f,\delta)$ to be simulated. The basic idea is for realizing $U$ is as follows: The components of $T$ are codified in $\Sigma^\ast$ giving a Gödel number $g(T)$ (W.r.o.g we assume here that the input alphatbet $\Sigma\subset^{\text{fin}}\mathbb{N}$ of $U$ is a finite subset . Furthermore remember, that $\delta$ can be represented as a table). The same strategy is used to codify configurations (of $T$) and computations steps (of $T$) in the alphabet $\Sigma$.  
universal Turing machine exists. The basic idea is as follows: The components
 
of $T$ are coded in $\Sigma^\ast$ giving a Gödel number $g(T)$
 
(W.r.o.g we assume here that $\Sigma\subset^{\text{fin}}\mathbb{N}$.
 
Furthermore remember, that $\delta$ can be represented as a table).
 
The same strategy is used to code configurations (of $T$) and  
 
computations steps (of $T$) in the alphabet $\Sigma$.
 
  
We will designate the Turing machine $T$ with Gödel number $g(T)$
+
We will designate the Turing machine $T$ with Gödel number $g(T)$ as $M_{g(T)}$ in the following. Now, a Turing machine $U$ can simulate $M_{g(T)}$ using its Gödel number $g(T)$. Assuming $M_{g(T)}$ is given the input $s$, the machine $U$ translates $s$ to the corresponding start configuration $c_s\in C$ of $T$. Afterwards, $U$ simulates each calculation step of $M_{g(T)}$ by looping over the following operation sequence  
as $M_{g(T)}$ in the following. Now, a Turing machine $U$ can simulate  
+
* Identify the actual configuration $c$ of the simulated Turing machine $M_{g(T)}$  
$M_{g(T)}=(Q,\Sigma,\Gamma,\sqcup,q_0,q_f,\delta)$ using its  
+
* Identify the transition operation to be applied to $c$ according to the (codified) transition function $\delta$ of $M_{g(T)}$  
Gödel number $g(T)$. Assuming $M_{g(T)}$ is given the input $s$, the
+
* Update the old configuration $c$ to the new configuration $c'$ using the identified transition operation  
machine $U$ translates $s$ to the corresponding start configuration
+
* Stop executing the loop if either no suitable transition operation exist (remember that $\delta$ is a partial function) or if in $c'= (B,i,q)$ it holds $q=q_f$.
$c_s\in C$ of $T$. Afterwards, $U$ simulates each calculation step of  
+
Invalid Gödel numbers are assigned to a Turing machine looping for all inputs. In effect, this gives $ U(g(T),s) = M_{g(T)}(s) $ for all $s\in\Sigma^\ast$.
$M_{g(T)}$ by looping over the following operation sequence
 
* Identify the actual configuration $c$ of the simulated Turing machine $M_{g(T)}$
 
* Identify the transition operation to be applied on $c$ according to the (codified) transition function $\delta$ of $M_{g(T)}$
 
* Update $c$ to the new configuration $c'$ using the identified transition operation
 
* Stop executing the loop if either no suitable transition operation exist (remember that $\delta$ is a partial function) or if in $c'= (B,i,q)$ it holds $q=q_f$.
 
Invalid Gödel numbers are assigned to a Turing machine looping for all inputs.
 
In effect, this gives $ U(g(T)\circ s) = M_{g(T)}(s) $ for all
 
$s\in\Sigma^\ast$.
 
  
 
===Interpretation of Universality===
 
===Interpretation of Universality===
  
The universality property shows that Turing machines are quite powerful
+
The universality property shows that Turing machines are quite powerful instruments. A Turing machine equipped with a suitable transition function $\delta$ can simulate each other Turing machine. For the other members of the Chomsky-hierarchy this closure property does not hold. Universality has far-reaching consequences for practice. It assures the usability for general purposes, i.e. the adaptability to all possible computable tasks by using a corresponding ''program'' as input.
instruments. A Turing machine equipped with a suitable transition function  
 
$\delta$ can simulate each other Turing machine. For the other members of  
 
the Chomsky-hierarchy this closure property does not hold. Universality
 
has far-reaching consequences for practice. It assures the general-purpose
 
property, i.e. the adaptability to all algorithmical problem-solving tasks
 
by using a corresponding ''program'' as input.
 
  
On the other hand, universality means a strong limitation as well. It
+
On the other hand, universality is a strong limitation as well. It exist an uncountable number of functions $f\colon\mathbb{N}\rightarrow\mathbb{N}$, but for a universal machine only a countable subset of them is computable. This is caused by the necessary usage of a [[Gödelization]].
exist uncountable many functions $f\colon\mathbb{N}\rightarrow\mathbb{N}$,
 
but for a universal machine only a countable subset of them is computable.
 
This is caused by the necessary usage of a [[Gödelization]].
 
  
 
===References===
 
===References===

Revision as of 18:21, 4 August 2013

2020 Mathematics Subject Classification: Primary: 68Q05 [MSN][ZBL]


The universality property of Turing machines states that it exists a Turing machine, which can simulate the behaviour of each other Turing machine. This property is of great practical importance. It says that a Turing machine can be adapted to different tasks by programming; from the viewpoint of computability it is not necessary to build special-purpose machines.

Definition of Universality

A Turing machine $T=(Q,\Sigma,\Gamma,\sqcup,q_0,q_f,\delta)$ can be interpreted as partially defined function $$F_T\colon\Sigma^\ast \longrightarrow \Sigma^\ast; i \mapsto \begin{cases} j & \text{$T$ stops in the final state $q_f\in Q$ with output $j$} \\ \bot & \text{otherwise} \end{cases}$$ The definition can be generalized to multiple arguments in a canonical way. Using $F_T$, we are introducing the notions of simulation and universality. A Turing machine $U$ simulates a Turing machine $T$, if $\exists t\in\Sigma^\ast \forall s\in\Sigma^\ast \colon F_U(t, s) =F_T(s)$. The Turing machine $U$ is called universal, if it can simulate every Turing machine $T$.

Existence of an Universal Turing Machine

Via Gödelization it can be proven that a universal Turing machine $U$ exists. For reasons of simplicity we will assume that $U$ uses the same input/output- and band alphabet as the machine $T=(Q,\Sigma,\Gamma,\sqcup,q_0,q_f,\delta)$ to be simulated. The basic idea is for realizing $U$ is as follows: The components of $T$ are codified in $\Sigma^\ast$ giving a Gödel number $g(T)$ (W.r.o.g we assume here that the input alphatbet $\Sigma\subset^{\text{fin}}\mathbb{N}$ of $U$ is a finite subset . Furthermore remember, that $\delta$ can be represented as a table). The same strategy is used to codify configurations (of $T$) and computations steps (of $T$) in the alphabet $\Sigma$.

We will designate the Turing machine $T$ with Gödel number $g(T)$ as $M_{g(T)}$ in the following. Now, a Turing machine $U$ can simulate $M_{g(T)}$ using its Gödel number $g(T)$. Assuming $M_{g(T)}$ is given the input $s$, the machine $U$ translates $s$ to the corresponding start configuration $c_s\in C$ of $T$. Afterwards, $U$ simulates each calculation step of $M_{g(T)}$ by looping over the following operation sequence

  • Identify the actual configuration $c$ of the simulated Turing machine $M_{g(T)}$
  • Identify the transition operation to be applied to $c$ according to the (codified) transition function $\delta$ of $M_{g(T)}$
  • Update the old configuration $c$ to the new configuration $c'$ using the identified transition operation
  • Stop executing the loop if either no suitable transition operation exist (remember that $\delta$ is a partial function) or if in $c'= (B,i,q)$ it holds $q=q_f$.

Invalid Gödel numbers are assigned to a Turing machine looping for all inputs. In effect, this gives $ U(g(T),s) = M_{g(T)}(s) $ for all $s\in\Sigma^\ast$.

Interpretation of Universality

The universality property shows that Turing machines are quite powerful instruments. A Turing machine equipped with a suitable transition function $\delta$ can simulate each other Turing machine. For the other members of the Chomsky-hierarchy this closure property does not hold. Universality has far-reaching consequences for practice. It assures the usability for general purposes, i.e. the adaptability to all possible computable tasks by using a corresponding program as input.

On the other hand, universality is a strong limitation as well. It exist an uncountable number of functions $f\colon\mathbb{N}\rightarrow\mathbb{N}$, but for a universal machine only a countable subset of them is computable. This is caused by the necessary usage of a Gödelization.

References

[H77] F. Hennie, "Introduction to Computability", Addison-Wesley 1977
[HU79] J. Hopcroft, J. Ullman, "Introduction to Automata Theory, Languages and Computation", Addison-Wesley 1979
[P81] C. Papdimitriou, "Elements of the theory of computation", Prentice-Hall 1981
How to Cite This Entry:
Joachim Draeger/sandbox. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Joachim_Draeger/sandbox&oldid=30043