147
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 42
    $\begingroup$ 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? $\endgroup$
    – Cory Klein
    Commented Aug 21, 2012 at 18:04
  • 93
    $\begingroup$ @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. $\endgroup$
    – Raphael
    Commented Aug 26, 2012 at 19:53

4 Answers 4

Reset to default
147
$\begingroup$

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

Improve this answer
$\endgroup$
9
  • 17
    $\begingroup$ 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? $\endgroup$
    – Others
    Commented Apr 6, 2016 at 5:29
  • 6
    $\begingroup$ @Others Yes, we would. $\endgroup$
    – JeffE
    Commented Apr 6, 2016 at 11:37
  • 3
    $\begingroup$ @JeffE Alright. Is a proof possible in Intuitionistic logic? Or is the law of the excluded middle necessary here? $\endgroup$
    – Others
    Commented Apr 6, 2016 at 17:13
  • 1
    $\begingroup$ Is this language(one in question) a regular? I think yes because we can construct dfa which accepts unary numbers lesser that certain integer. And also we can construct dfa to accept unary strings of arbitrary length. $\endgroup$
    – Vimal Patel
    Commented Dec 9, 2019 at 5:12
  • 4
    $\begingroup$ @VimalPatel Yes, the language $\{0^n \mid 0^n \text{ appears in the decimal representation of } \pi \}$ is indeed regular. Either the language is finite, and therefore regular, or the language is $0^*$, and therefore regular! $\endgroup$
    – JeffE
    Commented Dec 9, 2019 at 16:24
17
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 11
    $\begingroup$ Not all mathematicians accept this - e.g. intuitionists don't. $\endgroup$
    – reinierpost
    Commented Jul 10, 2013 at 19:25
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kaa1el
    Commented Sep 20, 2018 at 17:39
6
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 13
    $\begingroup$ 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... $\endgroup$
    – Yuval Filmus
    Commented Nov 12, 2014 at 0:07
  • 2
    $\begingroup$ Ah, the dangers of inductive leaps :P Good catch, thanks. $\endgroup$
    – Stephen Voris
    Commented Nov 12, 2014 at 1:28
  • 2
    $\begingroup$ 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? $\endgroup$
    – Stephen Voris
    Commented Nov 12, 2014 at 1:40
  • 5
    $\begingroup$ @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. $\endgroup$
    – David Richerby
    Commented Nov 12, 2014 at 1:54
  • 3
    $\begingroup$ @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. $\endgroup$
    – Stephen Voris
    Commented Nov 12, 2014 at 2:35
-2
$\begingroup$

The function is computable by the simplest of all functions, the constant function that always returns 1. Why? Because $\pi$, like any other irrational number, contains any sequence imaginable that is fixed in advanced, as is the case here. So $f$ should always return 1 regardless of the input $n$. This is a great question for that reason.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ "Because π, like any other irrational number, contains any sequence imaginable that is fixed in advanced" -- To my knowledge, that is an open question for $\pi$; can you reference a proof? The more general claim is just straight up false; it is easy to construct irrational numbers that don't use some digits at all, e.g. $0.101001000100001...$. $\endgroup$
    – Raphael
    Commented Sep 12 at 6:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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