1
$\begingroup$

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)?

$\endgroup$
0
$\begingroup$

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 $L\subseteq \Sigma^*$, here is an algorithm in your model that decides $L$ deterministically, and in linear time:

  1. Scan the input tape, and write every letter on a new tape, move to state $q$.
  2. We define the transition function as $\delta(q,w)=q_{acc}$ if $w\in 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".

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Hmm, interesting, thanks. My initial motivation was: In real computers, we have limited memory and even so we can use the TM model (with infinite tape) and answer many important questions... So what if we similarly presume that we have infinitely many "cores". However in this $\infty$-tape DTMs there is not only infinitely many heads, but there is also infinitely many infinite tapes now. $\endgroup$ – Antonin Komenda Nov 14 '13 at 15:51
  • $\begingroup$ It's not really the amount of tapes that matter, the power is more in the number of heads you use. As you can see, we only use one cell in every tape... The point is that mathematically, having an unbounded (or indeed, infinite) number of heads, is problematic and yields a useless model. That is, it does not correctly depict multiple cores. Perhaps you should look at the complexity class NC, which captures, in a way, multiple cores. $\endgroup$ – Shaull Nov 14 '13 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.