Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Consider $f(n)$, a function that returns 1 iff $n$ zeros appear consecutively in $\pi$. Now someone gave me a proof that $f(n)$ is computable:

Either for all n, $0^n$ appears in $\pi$, or there is a m s.t. $0^m$ appears in $\pi$ and $0^{m+1}$ does not. For the first possibility $f(n) := 1$; For the second one $f(n) := 1$ iff $n \leq m$, 0 otherwise.

The author claims that this proves computability of $f(n)$, as there exists an algorithm to compute it.

Is this proof correct?

share|improve this question
1  
You can use latex in your questions to make them more readable. –  Dave Clarke Oct 6 '10 at 17:11
3  
The argument is correct, but not constructive. The person is not giving you a TM, he is giving you two TMs and tells you that one of them is computing the function you want, but doesn't know which one. –  Kaveh Oct 6 '10 at 17:35
    
Your version is computable. However, I misread and accidentaly found a version that I believe is uncomputable. The only change: instead of exactly n zeroes, ask whether π has at most n zeroes. If it really does, I believe you cannot confirm it, since π has an infinite number of digits and there (seems?) to be no pattern re-appearing. –  chazisop Nov 23 '10 at 13:33
    
I corrected a Wikipedia page once which made a related mistake, asserting that the existence of Chaitin's constant proved the existence of "uncomputable integers". –  Geoffrey Irving Apr 1 at 17:06
add comment

4 Answers

Think of it this way, Mike: This proof is "branching" into multiple possible cases, one of which has to be true (using the law of excluded middle that for every proposition $p$, either $p$ is true or $\neg p$ is true). But at the end of each of these branches, you always manage to prove that the function $f$ is computable. Therefore, no matter which of the cases actually holds in real life, $f$ must be computable. (However, the precise reason why $f$ is computable will be different, depending on the branch.)

share|improve this answer
add comment

It is correct. This is the same as the following: define $f(x)$ to be the constant function $x \mapsto 0$ if God exists, and $x \mapsto 1$ if God doesn't exist. The resulting function is a constant function, thus computable. What you may not be able to do is to give that function, but the function itself is computable.

Here, one of the two possibilities is true : either there exists such an $m$, or it doesn't. The function is either the constant function $x \mapsto 1$ or a simple threshold function, defined with $m$.

share|improve this answer
2  
I would replace "if God exists" with $P \neq NP$. :) –  Kaveh Oct 6 '10 at 17:38
    
Ok, sorry for the misunderstanding, I'm not having trouble with the non-constructivity of the proof. The problem I have is, that we (or at least I) don't know whether $m$ is computable or not. Why isn't it necessary to prove that? –  Mike B. Oct 6 '10 at 19:04
4  
It doesn't really make sense to talk about whether an integer is computable or not. Whatever value m takes, there is a Turing machine that outputs it. Finding it might be hard of course, but this isn't so different from the general situation: finding algorithms is hard, which is the fact that keeps many of us employed. –  Aaron Roth Oct 6 '10 at 19:30
    
I still don't get it. What Turing machine could possibly output this m? Not just would it have to show that $0^m$ appears in $\pi$, more than that it would have to verify that $0^{m+1}$ doesn't - and that is IMO the problem. –  Mike B. Oct 6 '10 at 20:00
    
This is the constructive way you're talking about. If I give you a machine that outputs such an $m$, it doesn't need to convince you that this is the right $m$, as it is the machine for outputing such an $m$ (well, a machine at least). This is the same as God's example (which BTW comes from Sipser): if the machine outputs $0$, it doesn't need to convince you that God doesn't exist. It is just the case. –  Michaël Cadilhac Oct 6 '10 at 20:06
show 4 more comments

I think -- and hope -- that every computer science student is confronted with this problem which feels like a paradoxon. It is a very good example for the difference of computable in TCS sense and computable in a practical sense.

My thoughts back then were: "Yea, if I knew the answer, it would obviously be computable. But how to find out?" The trick is to rid yourself from the illusion that you have to find out wether $\pi$ has this property or not. Because this, obviously (read: imho), cannot be done by a Turing machine (as long as we do not have more knowledge than we have about $\pi$).

Consider your definition for computability: we say $f$ is (Turing-)computable if and only if $\exists M \in TM : f_M = f$. That is you only have to show existence of an appropriate Turing machine, not give one. What you -- we -- try to do there is to compute the Turing machine that computes the required function. This is a way harder problem!

The basic idea of the proof is: I give you an infinite class of functions, all of them computable (to show; trivial here). I prove then that the function you are looking for is in that class (to show; case distinction here). q.e.d.

share|improve this answer
add comment

Yes, thats right, its computable. The issue is that your function really isn't producing the solution to an infinite family of problems, the way (say) a function computing a solution to the halting problem is -- so there is no issue about computation. Instead, you are representing in function-form some single mathematical fact with finite representation -- either an integer, or the fact that f is the constantly 1 function

It is possible to encode the halting problem in individual real numbers, like Chaitan's constant $\Omega$, but integers always have finite representations and so can be encoded as Turing Machines.

Finding the correct algorithm of course might be a hard problem. But finding correct algorithms is usually hard!

share|improve this answer
add comment

Your Answer

 
discard

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.