# Timely lower bounded Turing machines

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?

• 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. – Yuval Filmus Jul 26 '16 at 8:09
• Ok, I understand your consideration. I edited the question so that it is now hopefully more clear: $t_M(a) \ge 1$. – 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.
• 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? – orgesleka Jul 26 '16 at 8:55