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

Question

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

Answer 1

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