Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 48 down vote favorite
7

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.

share|improve this question
 
Ah, I wanted to ask a similar question this morning ;) –  Daniil Mar 14 '12 at 15:44
6  
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
8  
@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

2 Answers

up vote 53 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.

share|improve this answer
6  
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! I feel like, following your proof scheme, one could prove that termination is decidable. Did I miss something? –  gallais Mar 14 '12 at 14:50
5  
@gallais: 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! –  Alex ten Brink Mar 14 '12 at 15:37
11  
@gallais That's not the same thing though. 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. –  sepp2k Mar 14 '12 at 16:00
6  
@gallais: the definition of "decidable" is that an algorithm exists to perform the task, not that we know which algorithm it is. As long as we can prove there is at least one suitable algorithm in existence then we know the problem is decidable. –  Carl Mummert Mar 14 '12 at 17:10
3  
I am also having a bit of a problem to accept this answer. But I think my issue is that this answer is non-constructive, and I am more inclined to constructive mathematics. But I guess the normal definition of computable is computable in a classic sense, and personally such a definition feels like nonsense. –  danr Mar 21 '12 at 11:00
show 6 more comments
up vote 6 down vote

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 of 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, supposing that we know N.

If N cannot be computed in a finite number of steps then program 1 will be correct. If N can be computed in a finite number of steps (very unlikely) then program 2 will be correct.

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.

share|improve this answer
1  
Not all mathematicians accept this - e.g. intuitionists don't. –  reinierpost Jul 10 at 19:25

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.