1
$\begingroup$

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...

$\endgroup$
  • $\begingroup$ What exactly is that string? An input to the next program? Or the binary representation of the next program itself? Of course you can compute such function, but you'll need a "much larger" machine (in terms of memory), which can compute all possible states of that program on the original machine (i.e., each state should reflect the entire physical state of the original machine), and then use that information in order to determine whether or not the program will have halted within an odd number of steps. $\endgroup$ – barak manos Dec 25 '15 at 16:38
  • $\begingroup$ @barakmanos but we don't know if the program halts or not. $\endgroup$ – ARi Dec 25 '15 at 16:45
  • $\begingroup$ This can almost certainly be used as a component to solve the halting problem. For each program, there probably is a larger program whose next program halts in an odd number of steps if and only if it halts. $\endgroup$ – Fengyang Wang Dec 25 '15 at 16:56
  • $\begingroup$ @FengyangWang How? We don't know which program will halt...or in how many steps. $\endgroup$ – ARi Dec 25 '15 at 16:58
  • $\begingroup$ My answer no longer convinces me. I have deleted my answer for now. $\endgroup$ – Fengyang Wang Dec 25 '15 at 18:32
0
$\begingroup$

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?
$\endgroup$
  • $\begingroup$ The function takes a single argument f(s) = 1 if w halts in odd number of steps where w>s and there is no u, s<u<w which halts. $\endgroup$ – ARi Dec 26 '15 at 3:54
  • $\begingroup$ @ARi Oh, I see. In this case the argument is a little more complicated, but the function is still the same degree as the Halting Problem; I'll add the details when I have a bit more time. $\endgroup$ – Noah Schweber Dec 26 '15 at 4:20
  • $\begingroup$ ...and of course claim 2 is obvious ie that it is no harder to compute f than it is to solve the halting problem. $\endgroup$ – ARi Dec 26 '15 at 12:51
  • $\begingroup$ @ARi See my edits. For context, there are some very weird numberings out there (e.g. Friedberg enumerations - a computable (but not admissible) numbering such that each program appears exactly once) $\endgroup$ – Noah Schweber Dec 26 '15 at 18:01
  • 1
    $\begingroup$ @ARi By the way I think this is a very interesting question - in particular, we can ask "What are the possible complexities of $f$ for admissible (or otherwise "nice-ish") numberings?" In fact, it's not entirely obvious to me that there isn't an admissible numbering whose $f$ is computable! $\endgroup$ – Noah Schweber Dec 26 '15 at 18:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.