0
$\begingroup$

I've been working on learning about recursion theory, and I've been doing problems with partial recursive functions. I stopped myself when I wrote something like this:

Let $g: \mathbb{N} \rightarrow \mathbb{N}$ be a partial recursive function and let $g(x)\downarrow$ denote that g converges for input x. Now, let $h(x) = \begin{cases} 0 & g(x)\downarrow \\ \uparrow & g(x)\uparrow \end{cases} $

Would $h$ be partial recursive? $h$ would be the partial "characteristic" function of the domain of $g$, but I cannot completely convince myself that $h$ is itself partial recursive. My main point of confusion is whether you can define a partial recursive function by asking if another one converges at an input. I cannot find any clarification on this point in my book.

And, moreover,

$k(x) = \begin{cases} 0 & g(x)\downarrow \\ 1 & g(x)\uparrow \end{cases}$

What would $k$ be considered? Although it converges at every point, it couldn't be recursive, as then it would decide non-recursive sets that are the domains of partial recursive functions.

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

My main point of confusion is whether you can define a partial recursive function by asking if another one converges at an input.

That's a very good confusion to have. Certainly in general we can't ask in the course of running an algorithm whether some other algorithm halts. However, there's a subtle "positive vs. negative" issue (or if you prefer, "c.e. vs. co-c.e.," or "existential vs. universal") here: if a computation halts, we see that at some finite time. This means that the following is a totally valid thing an algorithm can do:

... Now run $g(x)$ until it halts. When it does ...

If the computation $g(x)$ which is being "waited on" diverges, then so will the larger algorithm. More snappily, this means that clauses of the form "If $g(x)\uparrow$, then $\uparrow$" are perfectly fine: they abbreviate the strategy of running $g(x)$ and only proceeding further if it happens to halt.

(And we can elaborate on this in various ways, e.g. via dovetailing we can run a family of computations simultaneously and wait for one of them to halt.)

By contrast, steps of the form "If $g(x)\uparrow$, then $\downarrow=$..." are not safe: no similar strategy will succeed. A "$\downarrow$"-type conclusion has to be triggered by some finite blob of information, but a "$\uparrow$"-type hypothesis is in general not so triggered.

$\endgroup$

You must log in to answer this question.