# Can be non-deterministic Turing machine simulated by $k$-tape deterministic TM where $k=\infty$ with preserving polynomially-same accepting times?

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

## 1 Answer

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".

• 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. – Antonin Komenda Nov 14 '13 at 15:51
• 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. – Shaull Nov 14 '13 at 16:09