Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
k-tape_turing_machine [2014/02/18 21:05] nikolaj |
k-tape_turing_machine [2014/04/08 14:44] nikolaj |
||
---|---|---|---|
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: definiendum | @#FFBB00: $ \langle Q,\Gamma,\Sigma,\delta\rangle \in \mathrm{TM}_k $ | | |
- | | @#FFBB00: $ \langle Q,\Gamma,\Sigma,\delta\rangle \in \mathrm{TM}_k $ | | + | | @#AAFFAA: inclusion | @#AAFFAA: $ \Sigma\subset\Gamma$ | |
- | + | | @#AAFFAA: inclusion | @#AAFFAA: $ \delta: Q\times\Gamma^k \to Q \times \Gamma^k \times \{\mathrm{L},\mathrm{S},\mathrm{R}\}^k$ | | |
- | | @#AAFFAA: $ \Sigma\subset\Gamma$ | | + | | @#55EE55: postulate | @#55EE55: $ q_\mathrm{start},q_\mathrm{halt}\in Q $ | |
- | | @#AAFFAA: $ \delta: Q\times\Gamma^k \to Q \times \Gamma^k \times \{\mathrm{L},\mathrm{S},\mathrm{R}\}^k$ | | + | | @#55EE55: postulate | @#55EE55: $ \Box,\triangleright,0,1\in\Gamma $ | |
- | + | | @#55EE55: postulate | @#55EE55: $ \Box\notin\Sigma $ | | |
- | | @#55EE55: $ q_\mathrm{start},q_\mathrm{halt}\in Q $ | | + | |
- | | @#55EE55: $ \Box,\triangleright,0,1\in\Gamma $ | | + | |
- | | @#55EE55: $ \Box\notin\Sigma $ | | + | |
==== Discussion ==== | ==== Discussion ==== | ||
Line 37: | Line 34: | ||
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. |