Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
7 Rollback to Revision 5
source | link

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$. Then there are a finite number of values $0=r_1<r_2<\dots<r_k=N$ such that the string $0^{r_i}$ appears in $\pi$. In In this case the following algorithm (with the valuesvalue $r_i$$N$ hard-coded) is always correct:

    Zeros-in-pi(n):
     if (n∈{r1,n ...,> rk}N) then return 10 else return 01
    

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

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$. Then there are a finite number of values $0=r_1<r_2<\dots<r_k=N$ such that the string $0^{r_i}$ appears in $\pi$. In this case the following algorithm (with the values $r_i$ hard-coded) is always correct:

    Zeros-in-pi(n):
     if (n∈{r1, ..., rk}) then return 1 else return 0
    

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.

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

6 Fixed a bug: it's possible that $N$ is the largest number of consecutive zeroes but that some smaller numbers don't appear.
source | link

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 Then there are a finite number of values $0=r_1<r_2<\dots<r_k=N$ such that the string $0^{r_i}$ appears in $\pi$. In this case the following algorithm (with the valuevalues $N$$r_i$ hard-coded) is always correct:

    Zeros-in-pi(n):
     if (nn∈{r1, >..., Nrk}) then return 01 else return 10
    

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

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

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$. Then there are a finite number of values $0=r_1<r_2<\dots<r_k=N$ such that the string $0^{r_i}$ appears in $\pi$. In this case the following algorithm (with the values $r_i$ hard-coded) is always correct:

    Zeros-in-pi(n):
     if (n∈{r1, ..., rk}) then return 1 else return 0
    

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.

5 I think the list in quote looks better this way. If not, then somehow the marker for the first item one also should be made to look inline.
source | link

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. 
  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.   
  3. ??? 4. 
  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

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

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

4 replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
source | link
3 added relevant extracts from a comment discussion
source | link
    Mod Moved Comments To Chat
2 formatting
source | link
1
source | link