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?
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.)
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$.
As for your reference to the halting problem: You are right. But you consider only one machine there; who said this was not computable? The uncomputable halting problem is, however, general: the function we consider there has to answer correctly for all Turing machines.
The equivalent task in this setting here would be: Design such a function $f$ that takes a real number $r$ (not possible on TMs, but let us assume it was) and some integer $m$ and outputs $1$ iff at least $m$ zeros occurr in the decimals of $r$.
– Raphael Oct 06 '10 at 21:59I 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.
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!
post a bit old, but wanted to post another answer.
This is a non-constructive proof (or argument) of computability. It simply says that the function must exist in some sense since i can represent it (or more correctly index it), in the set (or universe) of computable functions. However it neither constructs the machine itself (i.e the algorithm), nor the index (assuming an effective enumeration of computable machines). The english phrase "thanks for nothing", seems in these cases most appropriate, like the following:
-- Look, I proved there is water somewhere!
Now you can be happy, while dying from thirst!
People in the history of mathematics have argued quite a bit on the actual validity (or range of validity) and meaning of such arguments. The end result is that the same type of arguments re-appear in the incompleteness theorems of Goedel and turn against this "closed universe assumption".
If you dont like these arguments so much i would not blame you.
