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$ – user41014 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.

| cite | improve this answer | |
  • 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$ – user41014 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