Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
"... 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
share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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