Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | Next revision Both sides next revision | ||
|
k-tape_turing_machine [2014/02/18 17:56] nikolaj |
k-tape_turing_machine [2014/02/18 21:05] nikolaj |
||
|---|---|---|---|
| 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 === | ||
