Let M be a deterministic Turing machine wich has the properties:

1) $\forall x,y \in \Sigma^* : t_M(xy) \ge t_M(x) + t_M(y)$

2) $\forall a \in \Sigma: t_M(a) \ge 1$ (Also 2) should be obvious for every DTM).

Then it follows that for all $x \in \Sigma^* : t_M(x) \ge |x| $. The graph $G_M$ induced by the transition function contains a cycle: To see this choose a word $w$ whose length $|w|$ is $> |Q|$ where $Q$ is the set of states of $M$. Then we have $t_M(w) \ge |w| > |Q|$. Since $M$ is at every time step on exactly one state, $M$ must visit in $t_M(w) > |Q|$ time steps one state at least twice, hence the graph $G_M$ must contain a cycle.

My question is this: Can we construct to every DTM $M'$ an equivalent DTM $M$ with the properties above? In my intuition this is possible: Just construct $M$ such that it reads all the input, writes what it has read, move the pointer to the beginning of the word and then gives control to $M'$. But is it possible to give a more formal proof for this? Or is my intuition wrong?

  • 1
    $\begingroup$ How exactly do you measure time? I find it hard to believe that the Turing machine knows that its input has length $1$ after exactly $1$ time step. $\endgroup$ – Yuval Filmus Jul 26 '16 at 8:09
  • $\begingroup$ Ok, I understand your consideration. I edited the question so that it is now hopefully more clear: $t_M(a) \ge 1$. $\endgroup$ – orgesleka Jul 26 '16 at 8:37

Use the following recursive procedure to construct $M'$ from $M$:

  1. Run $M'$ on all non-trivial prefixes and suffixes of the input (if any), and ignore the results.
  2. Run $M$ on the entire input, and output the result.

If $M$ always terminates, so does $M'$. The first step guarantees your first condition. The second condition is virtually automatic.

  • 1
    $\begingroup$ I guess I understand your answer, but can you give more details so that it is more clear. In particular, how do you construct $M'$ if in the definition of $M'$ it calls itself. Is it possible to give a not recursive definition? $\endgroup$ – orgesleka Jul 26 '16 at 8:55
  • $\begingroup$ You can implement recursion in many ways; it is essentially a programming question. If your laptop can execute recursive functions, so can a Turing machine. It is also possible to give a non-recursive definition, and it would make a nice exercise for you. What you have to do is to unroll the recursion. $\endgroup$ – Yuval Filmus Jul 26 '16 at 9:01

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.