We were given the following exercise.

Let

$\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$

Prove that $f$ is computable.

How is this possible? As far as I know, we do not know wether $\pi$ contains every sequence of digits (or which) and an algorithm can certainly not decide that some sequence is not occurring. Therefore I think $f$ is not computable, because the underlying problem is only semi-decidable.

  • 29
    Forgive me for being completely ignorant, I'm obviously missing some foundational point of the question, but isn't 0^n always 0? Since the 32nd decimal place if pi is 0, wouldn't that mean f(n) always returns 1? – Cory Klein Aug 21 '12 at 18:04
  • 61
    @CoryKlein: This is formal language notation; superscript $n$ here means $n$-fold concatenation, i.e. $a^5 = aaaaa$. $0$ is only a symbol here, not a number. – Raphael Aug 26 '12 at 19:53
up vote 126 down vote accepted

There are only two possibilities to consider.

  • For every positive integer $n$, the string $0^n$ appears in the decimal representation of $\pi$. In this case, the algorithm that always returns 1 is always correct.

  • There is a largest integer $N$ such that $0^N$ appears in the decimal representation of $\pi$. In this case the following algorithm (with the value $N$ hard-coded) is always correct:

    Zeros-in-pi(n):
     if (n > N) then return 0 else return 1
    

We have no idea which of these possibilities is correct, or what value of $N$ is the right one in the second case. Nevertheless, one of these algorithms is guaranteed to be correct. Thus, there is an algorithm to decide whether a string of $n$ zeros appears in $\pi$; the problem is decidable.


Note the subtle difference with the following proof sketch proposed by gallais:

  1. Take a random Turing machine and a random input. 2. Either the computation will go on for ever or it will stop at some point and there is a (constant) computable function describing each one of these behaviors. 3. ??? 4. Profit!

Alex ten Brink explains:

watch out what the Halting theorem states: it says that there exists no single program that can decide whether a given program halts. You can easily make two programs such that either one computes whether a given program halts: the first always says 'it halts', the second 'it doesn't halt' - one program is always right, we just can't compute which one of them is!

sepp2k adds:

In the case of Alex's example neither of the algorithms will return the right result for all inputs. In the case of this question one of them will. You can claim that the problem is decidable because you know that there is an algorithm that produces the right result for all inputs. It doesn't matter whether you know which one that algorithm is. 10

  • Comments are not for extended discussion; this conversation has been moved to chat. – Gilles Dec 12 '15 at 17:52
  • 7
    What would happen if someone proved that the statement "For every positive integer n, the string 0^n appears in the decimal representation of π" is unprovable? Would we still say this problem is decidable, despite the fact no correct algorithm could ever be constructed? – Others Apr 6 '16 at 5:29
  • 3
    @Others Yes, we would. – JeffE Apr 6 '16 at 11:37
  • 1
    @JeffE Alright. Is a proof possible in Intuitionistic logic? Or is the law of the excluded middle necessary here? – Others Apr 6 '16 at 17:13
  • @Others If I understood correctly, the idea is this: If we for each $N$ define the Turing machine $M_N$ as in the first part of the answer, then we know that one of them computes this function. We don't know which one (and if your statement was proved, we'd even know that it is impossible to know which one) but we still know that there is such a Turing machine, so the function is computable. – JiK Sep 13 '16 at 20:31

Just posting a slight elaboration on JeffE's answer.

We know that two functions/cases exist that can compute the function f(n):

  1. A function that always returns true (for all n, there exist n number of consecutive 0's)
  2. A function that will return true if n is smaller than an integer N, where N is defined as the maximum length of consecutive 0's that exist in the given irrational number (otherwise it returns false).

One and only one of these functions can be correct. We do not know which, but we know for certain that an answer exists. Computability requires that a function exist that can determine the answer within a finite amount of steps.

The number of steps in case 1 is trivially bound to just returning 1.

In case 2 the number of steps are also finite. For every integer $N$ we can construct a Turing machine $T_N(n)$ that accepts if $n < N$ and otherwise rejects in finite time. So not knowing an upper bound on $N$ doesn't matter. For every $N$ there exists a Turing machine, namely $T_N(n)$, that computes correctly whether $n < N$ (we don't know which of these are correct, but it doesn't matter, one exists).

While it may not be possible to choose between the two cases (though one seems more likely than another), we know that exactly one of them must be correct.

As a side note: our solution supposes that while we can not determine which function will elicit a correct value the essence of computability does not rely on the constructability of the proof. Pure Existence is sufficient.

  • 8
    Not all mathematicians accept this - e.g. intuitionists don't. – reinierpost Jul 10 '13 at 19:25
  • You are basically making a long example of the law of excluded middle, $P\lor\lnot P$, lol. In intuitionistic logic or any type theory based logic system, this proof is rejected. – Kaa1el Sep 20 at 17:39

Step 5 of the following proof attempt is unjustified, and in fact wrong - a counterexample can be found here. (thanks, Yuval; it did feel like the sketchiest part of the sketch). I've left the answer here as I think the mistake is instructive.


First off: JeffE's pair of answers is sufficient; f is computable either way.

A brief detour, though, into an attempt at a sketch of a proof by induction:
Premise R: $\pi$ does not repeat.
1. Look at $\pi$ in base 2. This is mostly to cut down on the number of cases.
2. No matter how far down the line you go, you will always find another 1 somewhere: the alternative is all zeros, which would mean $\pi$ starts repeating, which goes against R.
3. Same goes for going down the line and finding 0.
4. Expand to two-digit sequences: you can't stop finding either 01 or 10 (that is, places where it switches), because otherwise $\pi$ would start repeating on 1's or on 0's. Similarly, you can't stop finding 11 or 00, because otherwise it starts repeating on 1010101...
5. The inductive step: each finite sequence has to appear an infinite number of times, because the alternative is that $\pi$ starts repeating on one of the shorter sequences, which contradicts R.

  • 9
    First of all, we know that the binary expansion of $\pi$ doesn't repeat since $\pi$ is irrational. Second, there are irrational numbers which contain neither 000 nor 111 in their binary expansion, for example the one corresponding to the Thue-Morse sequence: 0.0110100110010110... – Yuval Filmus Nov 12 '14 at 0:07
  • 1
    Ah, the dangers of inductive leaps :P Good catch, thanks. – Stephen Voris Nov 12 '14 at 1:28
  • 1
    Incidentally, if the conclusion is wrong, does it make more sense for me to delete it or to leave it and acknowledge via edit that it's wrong? – Stephen Voris Nov 12 '14 at 1:40
  • 4
    @StephenVoris It depends how educational you think the mistake is. Note that the question of whether $\pi$ is normal (i.e., its base-$b$ expansion contains every finite sequence of $b$-ary digits infinitely often) is one of the big open problems of number theory. – David Richerby Nov 12 '14 at 1:54
  • 2
    @DavidRicherby Big open problem, you say? Yeah, that's good to know. I do think this is a reasonably educational mistake, as evidence towards how tricky the problem the OP's question is based on is - obviously I could be wrong on that too, given the downvote. – Stephen Voris Nov 12 '14 at 2:35

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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