Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision Last revision Both sides next revision | ||
|
k-tape_turing_machine [2014/02/18 17:56] nikolaj |
k-tape_turing_machine [2014/03/21 11:11] 127.0.0.1 external edit |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ===== k-tape Turing machine ===== | ===== k-tape Turing machine ===== | ||
| ==== Set ==== | ==== Set ==== | ||
| - | | @#88DDEE: $ k\in\mathbb N $| | + | | @#55CCEE: context | @#55CCEE: $ k\in\mathbb N $| |
| - | | @#FFBB00: $ \langle Q,\Gamma,\Sigma,\delta\rangle \in \mathrm{TM}_k $ | | + | | @#FFBB00: definiendum | @#FFBB00: $ \langle Q,\Gamma,\Sigma,\delta\rangle \in \mathrm{TM}_k $ | |
| - | | @#AAFFAA: $ \Sigma\subset\Gamma$ | | + | | @#AAFFAA: inclusion | @#AAFFAA: $ \Sigma\subset\Gamma$ | |
| - | | @#AAFFAA: $ \delta: Q\times\Gamma^k \to Q \times \Gamma^k \times \{\mathrm{L},\mathrm{S},\mathrm{R}\}^k$ | | + | | @#AAFFAA: inclusion | @#AAFFAA: $ \delta: Q\times\Gamma^k \to Q \times \Gamma^k \times \{\mathrm{L},\mathrm{S},\mathrm{R}\}^k$ | |
| - | | @#55EE55: $ q_\mathrm{start},q_\mathrm{halt}\in Q $ | | + | | @#55EE55: postulate | @#55EE55: $ q_\mathrm{start},q_\mathrm{halt}\in Q $ | |
| - | | @#55EE55: $ \Box,\triangleright,0,1\in\Gamma $ | | + | | @#55EE55: postulate | @#55EE55: $ \Box,\triangleright,0,1\in\Gamma $ | |
| - | | @#55EE55: $ \Box\notin\Sigma $ | | + | | @#55EE55: postulate | @#55EE55: $ \Box\notin\Sigma $ | |
| ==== Discussion ==== | ==== Discussion ==== | ||
| Line 37: | Line 37: | ||
| The following sucker lets you compute if your input is a string of 0's of length $2^n$ for some $n$. The picture encodes $\delta$ and $\triangleright$. | The following sucker lets you compute if your input is a string of 0's of length $2^n$ for some $n$. The picture encodes $\delta$ and $\triangleright$. | ||
| - | {{http://i.imgur.com/U3Mc1vP.png?x600}} | + | {{2_to_the_n_zeros.png?x600}} |
| The conventions in the pic (Snipsers book) are slightly different, blanks are denoted by another symbol, $q_\mathrm{start}$ is $q_1$, there are two final states $q_\mathrm{accept},q_\mathrm{reject}$ instead of $q_\mathrm{halt}$ and $\mathrm{x}$ is used for what we would likely use $1$. The simulation is considered over when $\delta$ doesn't tell you anymore what to do. | The conventions in the pic (Snipsers book) are slightly different, blanks are denoted by another symbol, $q_\mathrm{start}$ is $q_1$, there are two final states $q_\mathrm{accept},q_\mathrm{reject}$ instead of $q_\mathrm{halt}$ and $\mathrm{x}$ is used for what we would likely use $1$. The simulation is considered over when $\delta$ doesn't tell you anymore what to do. | ||
| Line 56: | Line 56: | ||
| Switching to a tape which is infinite in both directions gives a runtime bonus factor of $\frac{1}{4}$. Other variations are two- or three dimensional tapes and random access (larger head movements at a single step), but they don't have a significant effect on runtime neither. | Switching to a tape which is infinite in both directions gives a runtime bonus factor of $\frac{1}{4}$. Other variations are two- or three dimensional tapes and random access (larger head movements at a single step), but they don't have a significant effect on runtime neither. | ||
| - | Encode the original Turing machine $M$ into a string itself, i.e. $\triangleright\ \mathrm{Mcode}\ \Box\ \Box\ \dots$, where $\mathrm{Mcode}$ is the so called "machine code" of the machine $M$. Now have another machine $M'$ (designed for taking other Turing machines as additional input and copy what they would do) simulate the machine code together with some normal input for $M$. This changes the runtime only as $\mathcal O\left(T(n)\right)\to \mathcal O\left(\lceil\log T(n)\rceil\cdot T(n)\right)$. | + | See also [[Universal Turing machine]]. |
| - | + | ||
| - | Turing showed that there are so called //universal Turing machines// ($\mathrm{TM}\mathcal U$), which are capable of running //any// other Turing machine $M$ when given in machine code format. Such a universal machine $M'$ might then be physically realized via hardware (like a PC, designed for executing $\delta$ with 3 Gigahertz) and a machine code $\mathrm{Mcode}$ might come from a computer program written by a 6 year old fat girl from Ohio. [[http://www.youtube.com/watch?v=E3keLeMwfHY|This video]] is from a nerd who wanted to build himself a hands on realization of a $\mathrm{TM}\mathcal U$. | + | |
| - | + | ||
| - | Without going into detail, the idea is the following. Remember that a general transition function is of the type: | + | |
| - | + | ||
| - | $ \delta: Q\times\Gamma^k \to Q \times \Gamma^k \times \{\mathrm{L},\mathrm{S},\mathrm{R}\}^k$ | + | |
| - | + | ||
| - | Consider a transition function $\delta$ for a Turing machine $M$ we want to simulate: | + | |
| - | + | ||
| - | $ \delta: Q\times\Gamma \to Q \times \Gamma \times \{\mathrm{L},\mathrm{S},\mathrm{R}\}$ | + | |
| - | + | ||
| - | The art in designing the universal Turing machine $M'$ (and in particular $\delta'$, which by construction has access to $Q$ and $\delta$) in terms of $M$. One key is to story $Q$ and $\delta$ of $M$ on $M'$'s tapes $\Gamma_Q, \Gamma_\delta$. Roughly | + | |
| - | + | ||
| - | "$ \delta': Q'\times\Gamma \times \Gamma_Q \times \Gamma_\delta \to Q' \times \Gamma \times \Gamma_Q \times \Gamma_\delta \times \{\mathrm{L},\mathrm{S},\mathrm{R}\}^3$" | + | |
| - | + | ||
| - | After this 3-tape Turing machine is constructed we can concert is to a 1-tape Turing machine, if necessary. | + | |
| ==== Parents ==== | ==== Parents ==== | ||
| === Requirements === | === Requirements === | ||
