World's most popular travel blog for travel bloggers.

Timely lower bounded Turing machines

, ,
Problem Detail:

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?

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.