7 Rollback to Revision 5 edited Apr 23 at 11:02 David Richerby 72.1k16111201 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 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: Take a random Turing machine and a random input. 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. ??? 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 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: Take a random Turing machine and a random input. 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. ??? 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: Take a random Turing machine and a random input. 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. ??? 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. edited Apr 23 at 10:59 David Richerby 72.1k16111201 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 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: Take a random Turing machine and a random input. 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. ??? 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: Take a random Turing machine and a random input. 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. ??? 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 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: Take a random Turing machine and a random input. 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. ??? 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. edit approved Apr 23 at 10:30 ThoAppelsin 1033 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: 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: 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: Take a random Turing machine and a random input.  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.  ???  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/ edited Apr 13 '17 at 12:48 3 added relevant extracts from a comment discussion edited Dec 12 '15 at 17:56 Gilles♦ 33.8k798166 Mod Moved Comments To Chat occurred Dec 12 '15 at 17:52 2 formatting edited Aug 13 '13 at 10:53 Raphael♦ 58.4k25143322 1 answered Mar 14 '12 at 14:06 JeffE 7,79113047