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?

  • 2
    $\begingroup$ You can use latex in your questions to make them more readable. $\endgroup$ – Dave Clarke Oct 6 '10 at 17:11
  • 8
    $\begingroup$ 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. $\endgroup$ – Kaveh Oct 6 '10 at 17:35
  • 1
    $\begingroup$ 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. $\endgroup$ – chazisop Nov 23 '10 at 13:33
  • $\begingroup$ 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". $\endgroup$ – Geoffrey Irving Apr 1 '14 at 17:06
  • $\begingroup$ these types of questions tend to be on "trivial languages". but note how usually a slight reformulation eg where the language is $f(n, k) = m$ where $m$ is a (or the 1st) location of the $0^k$ string or -1 if there is no such string may be undecidable. see also how can it be decidable that $\pi$ has some sequence of digits? / Computer Science $\endgroup$ – vzn Sep 5 '15 at 14:25

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$.

  • 4
    $\begingroup$ I would replace "if God exists" with $P \neq NP$. :) $\endgroup$ – Kaveh Oct 6 '10 at 17:38
  • $\begingroup$ 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? $\endgroup$ – Mike B. Oct 6 '10 at 19:04
  • 5
    $\begingroup$ 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. $\endgroup$ – Aaron Roth Oct 6 '10 at 19:30
  • $\begingroup$ 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. $\endgroup$ – Mike B. Oct 6 '10 at 20:00
  • $\begingroup$ 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. $\endgroup$ – Michaël Cadilhac Oct 6 '10 at 20:06

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.

  • $\begingroup$ It is trivial to write code that takes a proposition, and then finds a proof of it in ZFC if one exists. Take metamath and feed all possible proofs into it until it reports that one is a proof that pi has an sequence of zeros of arbitrary length. Run it concurrently with search for there exists an n s.t. pi doesn't have a sequence of zeros of length n. If one of those has a proof of finite length in ZFC, it will be found in finite time, even if not before the heat death of the universe. $\endgroup$ – prosfilaes Nov 11 '20 at 5:57
  • $\begingroup$ @prosfilaes I don't see how that relates to the answer, at all. $\endgroup$ – Raphael Nov 11 '20 at 10:27
  • $\begingroup$ You claimed that finding out whether π has this property cannot be done by a Turing machine. My point is that all finite proofs in ZFC can be enumerated by a Turing machine, so if provable, a Turing machine can find if π has this property. $\endgroup$ – prosfilaes Nov 12 '20 at 6:39
  • $\begingroup$ Even if dragging ZFC proofs into this were to help at all (I'm not convinced -- why that framework?) and it was decidable whether one of the enumerated proofs actually proves the claim (which I doubt), it would only give you a semi-decider. Here, we'd need a decider. $\endgroup$ – Raphael Nov 12 '20 at 9:01
  • $\begingroup$ You doubt that it is decidable whether one of the enumerated proofs actually proves the claim? Metamath is a program that takes an proof (with ZF/ZFC being the best supported theory) and decides whether the proof proves the claim. $\endgroup$ – prosfilaes Nov 12 '20 at 9:05

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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