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 21:05] 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. | ||
