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?

  • $\begingroup$ Does $k$ scale with the input size? Or is it constant for every machine (as, e.g., its number of states)? $\endgroup$ – dkaeae Jan 4 '19 at 16:57
  • $\begingroup$ 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. $\endgroup$ – dkaeae Jan 4 '19 at 16:59
  • $\begingroup$ 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?) $\endgroup$ – Ran G. Jan 4 '19 at 17:32
  • $\begingroup$ $w$ would be the input word. $\endgroup$ – Yotam Raz Jan 5 '19 at 9:47

Your Answer

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

Browse other questions tagged or ask your own question.