Problem Detail: I know that for every $k$-tape DTM that runs in time $O(t(n))$, there exists a 1-tape DTM that runs in $O(t^2(n))$, no matter how large the $k$ (the $k$-part is a formulation from Wikipedia). But what if $k=infty$? If I understand it right, if $k=infty$, then the alphabet of the $infty$-tape DTM is infinite and therefore the transition function will be infinite as well. That is why it is not NTM by definition, however it should be much more powerful than a DTM (based on the argument that we can encode a countable infinitely long input into one symbol of countable infinitely large alphabet). So, is it known if a NTM can be simulated by $infty$-tape DTM (with preserving polynomially-same accepting times)?
Asked By : Antonin Komenda
Answered By : Shaull
This is a very nice question, which rises often in computability courses. Once you allow infinitely many tapes, with infinitely many read/write heads, then the model becomes way too powerful. Formally, consider any language $Lsubseteq Sigma^*$, here is an algorithm in your model that decides $L$ deterministically, and in linear time:
- Scan the input tape, and write every letter on a new tape, move to state $q$.
- We define the transition function as $delta(q,w)=q_{acc}$ if $win L$, and $delta(q,w)=q_{rej}$ otherwise.
By $delta(q,w)$ we mean that the state is $q$, and the letters that are read by the infinite number of heads form the word $w$. As you can see, we decide $L$ “by definition”, and this definition is legitimate, since the transition table is infinite. So your model can decide every language, which means that it provides no differentiation of language classes. So theoretically, we just showed that it’s “not interesting”.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/18015 Ask a Question Download Related Notes/Documents
