# RO turing machine with finite memory

Consider the following:

A weak TM is a TM with finite tape in size $$k$$ which can only read its input values. note: the tape size does not include the input length.

I need to determine whether if the weak model is equivalent to a regular TM, or to explain why not and to show the equivalence to any other computational model.

I'm quiet confident that the weak TM is equivalent to a DFA with $$\gamma^k\cdot q\cdot (n+k)$$ states where $$|\Gamma| = \gamma$$, $$|Q| = q$$ and $$|w| = n$$.

My intuition is that there are at most $$\gamma^k$$ strings that the machine can write, there are $$q$$ states and the head can be stationed at one of the $$n+k$$ slots on the tape.

I'm having a hard time to prove it though, Anyone can shed some light?

• Does $k$ scale with the input size? Or is it constant for every machine (as, e.g., its number of states)? – dkaeae Jan 4 at 16:57
• Also, any TM is equivalent to a DFA if the input size is fixed; this is trivial. The problem is that, for most machines, the respective DFAs are nonuniform across the input space. – dkaeae Jan 4 at 16:59
• If you can't prove it, maybe try to refute your guess? Can the weak TM recognize palindromes of size $k$? What about the DFA? (and what is $w$ in its def?) – Ran G. Jan 4 at 17:32
• $w$ would be the input word. – Yotam Raz Jan 5 at 9:47