Church's Thesis

Question

If we let $f$ be a computable function and define $h(x) = 1$, if $x$ is an element of $\operatorname{dom}(f)$ and undefined otherwise.

I am trying to prove that h is computable via Church's Thesis.

So the idea is that I can say that given $x$, compute $f$. If the computation stops, then set $h(x) = 1$, otherwise continue indefinitely.

But this is not very rigorous in the aspect of URM computability and I need help in polishing this claim. Thanks

Answer 1

A better description of the algorithm $h$ would be:

• Given input $x$:
  • Emulate the calculation of $f(x)$
  • Output 1

Answer 2

If the goal is to do it "via Church's thesis" then you don't want to be "very rigorous", you just want to give a ''sufficiently'' detailed argument that the function is computable by a human. The argument you gave is sufficiently detailed for that purpose; the sentence you wrote clearly describes the algorithm that is needed to compute $h$.

This method of showing that a function is computable is called "weak Church's thesis" by Rogers. The idea is to give a description of the algorithm that is precise enough for the reader to see that the function is computable, without writing a detailed program for the function. Of course, the reader could come back and ask for a more detailed explanation, but in practice it is often possible to convince the reader that a function is computable without producing a program for it.