Problem with Soare's book on re sets.

Question

On page 16 of his "RE sets and degrees" he introduces the notion of a (Turing) computable function indexed by e with input x and output y taking fewer than s steps to complete, WHERE s has to be greater than e, x, and y. Why must s be greater than e, x and y? Surely most stopping programs will stop long before they perform e steps, since e is usually astronomical. But the real issue I have is with the x less than s requirement, since this means that s is going to grow arbitrarily large since x is arbitrarily large. How is this modelling Turing computability? There are masses of Turing machines that halt after a few steps regardless of the size of input. The function x-1 (for x not = 0) for instance "Delete the symbol you're on and move one space to the right, then stop".

Answer 1

This is just a convention which makes some arguments simpler; it is harmless.

What do I mean by that? Well, one thing we can do is think of $s$ as the maximum of the running time defined in the usual way and $\max\{x, y, e\}$. Alternatively, you can show that there is a total increasing computable $f$ such that $\Phi_e$ and $\Phi_{f(e)}$ describe the same partial computable function but the running time of $\Phi_{f(e)}(x)$ is always greater than $f(e)$, $x$, or the output of $\Phi_{f(e)}(x)$ (just make your machine perform lots of pointless dithering). So we may just restrict our attention to machines of the form $\Phi_{f(e)}$ ($e\in\mathbb{N}$).

Keep in mind that we aren't really interested in questions of actual running time, it's just that for a lot of arguments we want to consider a number $s$ such that

• $\Phi_e(x)=y$ in $<s$ steps, and

• $s>e, x, y$.

We could give the least such $s$ a different name, say "fleen," but it's more intuitive to call it the "running time," even though that's slightly inaccurate.

---

Note that there definitely are occasions where this convention would not be harmless! In computability theory (as opposed to complexity theory), though, the questions we tend to ask are very robust: for instance, as long as we have an upper bound on how long a machine is going to take to halt, we're as happy as if we knew exactly how long it was going to take.