# Church's Thesis

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

-
"... let f be a computable function.... I am trying to prove that f is computable." Huh? – Amit Kumar Gupta Feb 8 '13 at 8:48
For any TM, it is easy to put a little bit of code at the end to erase the answer $f(x)$ and write a $1$. – André Nicolas Feb 8 '13 at 8:50
Do you mean you're trying to prove $h$ computable? – Hurkyl Feb 8 '13 at 8:58
Yes, thanks for catching the typo – Buddy Holly Feb 8 '13 at 9:52
I tweaked the tags. This is a straight-up computability question, it's not really related to incompleteness or computational complexity. – Carl Mummert Feb 8 '13 at 11:58

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

• Given input $x$:
• Emulate the calculation of $f(x)$
• Output 1
-
This is good, do you mind adding some more details and explain where Church's thesis was implemented? – Buddy Holly Feb 8 '13 at 19:34

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.

-