Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
dtime [2014/02/18 15:44] nikolaj |
dtime [2014/03/21 11:11] (current) |
||
---|---|---|---|
Line 1: | Line 1: | ||
===== DTIME ===== | ===== DTIME ===== | ||
==== Set ==== | ==== Set ==== | ||
- | | @#88DDEE: $ T:\mathbb N\to\mathbb N $| | + | | @#55CCEE: context | @#55CCEE: $ T:\mathbb N\to\mathbb N $| |
- | | @#FFBB00: $ L\in \mathrm{\bf{DTIME}}(T(n)) $ | | + | | @#FFBB00: definiendum | @#FFBB00: $ L\in \mathrm{\bf{DTIME}}(T(n)) $ | |
- | | @#AAFFAA: $ L\subseteq\{0,1\}^* $ | | + | | @#AAFFAA: inclusion | @#AAFFAA: $ L\subseteq\{0,1\}^* $ | |
- | | @#DDDDDD: $M\in\mathrm{TM}$ | | + | | @#DDDDDD: range | @#DDDDDD: $M\in\mathrm{TM}$ | |
- | | @#DDDDDD: $c\in\mathbb{N}$ | | + | | @#DDDDDD: range | @#DDDDDD: $c\in\mathbb{N}$ | |
- | | @#55EE55: $\exists M,c.\ M$ decides $L$ in $c\cdot T(n)$-time | | + | | @#55EE55: postulate | @#55EE55: $\exists M,c.\ M$ decides $L$ in $c\cdot T(n)$-time | |
==== Discussion ==== | ==== Discussion ==== | ||
- | The {\bf{D}} stands for deterministic. | + | The ${\bf{D}}$ stands for deterministic. |
==== Parents ==== | ==== Parents ==== | ||
=== Requirements === | === Requirements === | ||
- | [[k-tape Turing machine]] | + | [[Turing machine as partial function]] |
=== Subset of === | === Subset of === | ||
[[Bit string]] | [[Bit string]] |