A function given a string ( a program) accepts it if the next program which halts does so in an odd number of steps... is it turing computable

Question

A function which given a string returns 1 if the next program halts with an odd number of steps and 0 otherwise.

Is this function computable

f(s)=1 if w halts in odd number of steps where w>s and there us no u such that s < u < w. (u,v,w denoting programs that run on a UTM) and u halts.

f(s) = 0 otherwise.

If one has to consider an input to these programs we stipulate input as zero in all cases...

Answer 1

I suspect this problem is ill-posed: the degree of $f$ may depend on the specific enumeration of Turing machines used.

However, I can prove that the degree of the Halting Problem is attainable:

Claim: there is an admissible numbering $\varphi_i$ of Turing machines such that $f$, defined relative to this numbering, computes the Halting Problem.

(See https://en.wikipedia.org/wiki/Admissible_numbering.)

Let $\varphi_i$ be an admissible numbering such that for all $n$, $\varphi_{2n}$ is the program which always halts immediately - that is, in zero (= an even number of) steps. Now let $R$ be a computable function such that for all $e$, $\varphi_{R(e)+1}$ is an index for the program which on all inputs runs $\varphi_e(0)$, and halts in an odd number of stages if $\varphi_e(0)$ ever halts (via padding with a "dummy step" if necessary), and diverges otherwise. Such an $R$ exists by the Recursion theorem, since $\varphi_i$ is an admissible numbering. Then $\varphi_e(0)\downarrow\iff f(R(e))=0$.

---

Note that since you care about run time, "admissible numbering" isn't really the right term to use, since for instance if we just slow every machine down by a factor of 2 (so $f(e)=0$ always) this is still an admissible numbering.

You want a numbering of machines, not just functions.

Def'n. A numbering of machines is a function $\nu:\omega\rightarrow\omega$ such that $(i)$ $\nu$ is computable and $(ii)$ for every $i$, there is some $k$ such that for all $s, x, y$, we have $$\varphi_i(x)[s]=y\iff \varphi_{\nu(k)}(x)[s]=y,$$ that is, every machine occurs in the range of $\nu$.

(Here "$[s]=$" means "halts in $s$ steps and equals"; this is really useful notation.) Similarly to the construction of a Friedberg enumeration (but much simpler), we may construct a numbering of machines whose $f$ is computable! This is a good exercise.

The right notion of "tame numbering of machines," I think, is:

Def'n. A numbering of machines $\nu$ is tame if there is a computable function $g$ such that for all $i, x, y, s$, we have $$\varphi_i(x)[s]=y\iff \varphi_{\nu(g(i))}(x)[s]=y,$$ that is, we can computably find programs in $\nu$.

What I have absolutely no idea about:

• Is there a tame numbering of machines whose $f$ is strictly weaker than the Halting Problem? Is there a t.n.m. whose $f$ is computable?