<p>Think of it this way, Mike: This proof is "branching" into multiple possible cases, one of which has to be true (using the law of excluded middle that for every proposition $p$, either $p$ is true or $\neg p$ is true). But at the end of each of these branches, you always manage to prove that the function $f$ is computable. Therefore, no matter which of the cases actually holds in real life, $f$ must be computable. (However, the precise reason <em>why</em> $f$ is computable will be different, depending on the branch.)</p>

CC BY-SA 2.5
2010-10-06T22:17:39.527Z
2010-10-06T22:17:39.527Z
Ryan Williams
<p>It is correct.  This is the same as the following: define $f(x)$ to be the constant function $x \mapsto 0$ if God exists, and $x \mapsto 1$ if God doesn't exist.  The resulting function is a constant function, thus computable.  What you may not be able to do is to give that function, but the function itself is computable.</p>

<p>Here, one of the two possibilities is true : either there exists such an $m$, or it doesn't.  The function is either the constant function $x \mapsto 1$ or a simple threshold function, defined with $m$.</p>

CC BY-SA 4.0
2019-11-07T13:03:09.057Z
I don't get this. Is ExistGod->Bool a computable function? With this logic I can replace that with HaltsMyProgramOnInputX->Bool. And then f(x) solves halting problem for this particular program and input.
Cowboy Trader
CC BY-SA 4.0
2019-11-07T19:32:07.397Z
@CowboyTrader: That's correct. The function that takes an input and returns the function that returns true if the program stops on that input is, however, not computable.
Michaël Cadilhac
CC BY-SA 2.5
2010-10-06T17:38:51.983Z
I would replace "if God exists" with $P \neq NP$. :)
Kaveh
CC BY-SA 2.5
2010-10-06T19:04:37.997Z
Ok, sorry for the misunderstanding, I'm not having trouble with the non-constructivity of the proof. The problem I have is, that we (or at least I) don't know whether $m$ is computable or not. Why isn't it necessary to prove that?
Mike B.
CC BY-SA 2.5
2010-10-06T19:30:14.147Z
It doesn't really make sense to talk about whether an integer is computable or not. Whatever value m takes, there is a Turing machine that outputs it. Finding it might be hard of course, but this isn't so different from the general situation: finding algorithms is hard, which is the fact that keeps many of us employed.
Aaron Roth
CC BY-SA 2.5
2010-10-06T20:00:50.463Z
I still don't get it. What Turing machine could possibly output this m? Not just would it have to show that $0^m$ appears in $\pi$, more than that it would have to verify that $0^{m+1}$ doesn't - and that is IMO the problem.
Mike B.
CC BY-SA 2.5
2010-10-06T20:06:02.493Z
This is the constructive way you're talking about.  If I give you a machine that outputs such an $m$, it doesn't need to *convince you* that this is the right $m$, as it is *the* machine for outputing such an $m$ (well, *a* machine at least).  This is the same as God's example (which BTW comes from Sipser): if the machine outputs $0$, it doesn't need to convince you that God doesn't exist.  It is just the case.
Michaël Cadilhac
CC BY-SA 2.5
2010-10-06T21:59:26.040Z
Mike, your task is not to compute $m$. See my answer below.

As for your reference to the halting problem: You are right. But you consider only one machine there; who said this was not computable? The uncomputable halting problem is, however, general: the function we consider there has to answer correctly for _all_ Turing machines.

The equivalent task in this setting here would be: Design such a function $f$ that takes a real number $r$ (not possible on TMs, but let us assume it was) and some integer $m$ and outputs $1$ iff at least $m$ zeros occurr in the decimals of $r$.
Raphael
CC BY-SA 2.5
2010-10-13T13:28:25.840Z
Ok, thank you very much for your answers and your patience. I finally figured out my misunderstandings, especially with "uncomputable constants". One last thingh: $h(x) = 1$ iff $CH$ is true, 0 otherwise. This function is computable, right?
Mike B.
CC BY-SA 2.5
2010-10-13T14:15:43.790Z
This is a constant function in either case, so yes.
Michaël Cadilhac
CC BY-SA 2.5
2010-10-06T17:28:34.797Z
2010-10-06T17:28:34.797Z
Michaël Cadilhac
<p>I think -- and hope -- that every computer science student is confronted with this problem which feels like a paradoxon. It is a very good example for the difference of computable in TCS sense and computable in a practical sense.</p>

<p>My thoughts back then were: "Yea, if I <em>knew</em> the answer, it would obviously be computable. But how to find out?" The trick is to rid yourself from the illusion that you have to find out wether $\pi$ has this property or not. Because this, obviously (read: imho), cannot be done by a Turing machine (as long as we do not have more knowledge than we have about $\pi$).</p>

<p>Consider your definition for computability: we say $f$ is (Turing-)computable if and only if  $\exists M \in TM : f_M = f$. That is you only have to show <em>existence</em> of an appropriate Turing machine, not <em>give one</em>. What you -- we -- try to do there is to compute the Turing machine that computes the required function. This is a way harder problem!</p>

<p>The basic idea of the proof is: I give you an infinite class of functions, all of them computable (to show; trivial here). I prove then that the function you are looking for is in that class (to show; case distinction here). q.e.d.</p>

CC BY-SA 4.0
2020-11-11T05:57:40.277Z
It is trivial to write code that takes a proposition, and then finds a proof of it in ZFC if one exists. Take metamath and feed all possible proofs into it until it reports that one is a proof that pi has an sequence of zeros of arbitrary length. Run it concurrently with search for there exists an n s.t. pi doesn't have a sequence of zeros of length n. If one of those has a proof of finite length in ZFC, it will be found in finite time, even if not before the heat death of the universe.
prosfilaes
CC BY-SA 4.0
2020-11-11T10:27:43.073Z
@prosfilaes I don't see how that relates to the answer, at all.
Raphael
CC BY-SA 4.0
2020-11-12T06:39:47.273Z
You claimed that finding out whether π has this property cannot be done by a Turing machine. My point is that all finite proofs in ZFC can be enumerated by a Turing machine, so if provable, a Turing machine can find if π has this property.
prosfilaes
CC BY-SA 4.0
2020-11-12T09:01:54.613Z
Even if dragging ZFC proofs into this were to help at all (I'm not convinced -- why _that_ framework?) _and_ it was decidable whether one of the enumerated proofs actually proves the claim (which I doubt), it would only give you a semi-decider. Here, we'd need a decider.
Raphael
CC BY-SA 4.0
2020-11-12T09:05:52.913Z
You doubt that it is decidable whether one of the enumerated proofs actually proves the claim? Metamath is a program that takes an proof (with ZF/ZFC being the best supported theory) and decides whether the proof proves the claim.
prosfilaes
CC BY-SA 4.0
2020-11-12T09:47:06.443Z
@prosfilaes As I said: Even assuming all of that is true -- to reiterate: that there _is_ a ZFC proof, that you can enumerate them, and check each of them -- you still only get a semi-decider. As such, I fail to see how this relates to my answer, or the question.
Raphael
CC BY-SA 4.0
2020-11-13T19:40:20.343Z
You said "Because this, obviously (read: imho), cannot be done by a Turing machine (as long as we do not have more knowledge than we have about π)." This can be done by a Turing machine, provided a proof exists, and if it doesn't, that's not really about how much knowledge we have about pi.
prosfilaes
CC BY-SA 4.0
2020-11-13T19:54:46.790Z
Actually, it's not a semidecider; a TM to check an arbitrary proposition is, but a TM with no arguments, to answer a question with no variables, either decides or not. Pedantic, but quite parallel to the original question.
prosfilaes
CC BY-SA 2.5
2010-10-06T18:35:07.117Z
2010-10-06T18:35:07.117Z
Raphael
<p>Yes, thats right, its computable. The issue is that your function really isn't producing the solution to an infinite family of problems, the way (say) a function computing a solution to the halting problem is -- so there is no issue about computation. Instead, you are representing in function-form some single mathematical fact with finite representation -- either an integer, or the fact that f is the constantly 1 function</p>

<p>It is possible to encode the halting problem in individual <em>real</em> numbers, like Chaitan's constant $\Omega$, but integers always have finite representations and so can be encoded as Turing Machines.</p>

<p>Finding the correct algorithm of course might be a hard problem. But finding correct algorithms is usually hard! </p>

CC BY-SA 2.5
2010-10-06T17:32:32.903Z
2010-10-06T19:32:20.660Z
2010-10-06T19:32:20.660Z
Aaron Roth
<p>post a bit old, but wanted to post another answer.</p>

<p>This is a <strong>non-constructive proof</strong> (or argument) of computability. It simply says that the function must exist in some sense since i can represent it (or more correctly index it), in the set (or universe) of computable functions. However it <strong>neither constructs the machine itself</strong> (i.e the algorithm), <strong>nor the index</strong> (assuming an effective enumeration of computable machines). The english phrase "<em>thanks for nothing</em>", seems in these cases most appropriate, like the following:</p>

<pre><code>-- Look, I proved there is water somewhere! 

Now you can be happy, while dying from thirst!
</code></pre>

<p>People in the history of mathematics have argued quite a bit on the actual validity (or range of validity) and meaning of such arguments. The end result is that the same type of arguments re-appear in the incompleteness theorems of Goedel and turn against this  <a href="http://en.wikipedia.org/wiki/Closed-world_assumption" rel="nofollow">"closed universe assumption"</a>.</p>

<p>If you dont like these arguments so much i would not blame you.</p>

CC BY-SA 3.0
2015-06-03T01:15:22.430Z
2015-09-02T18:12:12.650Z
2015-09-02T18:12:12.650Z
Nikos M.
<p>Consider $f(n)$, a function that returns 1 iff $n$ zeros appear consecutively in $\pi$. Now someone gave me a proof that $f(n)$ is computable:</p>

<blockquote>
  <p>Either for all n, $0^n$ appears in $\pi$, or there is a m s.t. $0^m$ appears in $\pi$ and $0^{m+1}$ does not.
  For the first possibility $f(n) := 1$; For the second one $f(n) := 1$ iff $n \leq m$, 0 otherwise.</p>
</blockquote>

<p>The author claims that this proves computability of $f(n)$, as there exists an algorithm to compute it.</p>

<p>Is this proof correct?</p>

CC BY-SA 3.0
2014-04-01T17:06:48.737Z
I corrected a Wikipedia page once which made a related mistake, asserting that the existence of Chaitin's constant proved the existence of "uncomputable integers".
Geoffrey Irving
CC BY-SA 3.0
2015-09-05T14:25:59.067Z
these types of questions tend to be on "trivial languages". but note how usually a slight reformulation eg where the language is $f(n, k) = m$ where $m$ is a (or the 1st) location of the $0^k$ string or -1 if there is no such string may be undecidable. see also [how can it be decidable that $\pi$ has some sequence of digits?](http://cs.stackexchange.com/questions/367/how-can-it-be-decidable-whether-pi-has-some-sequence-of-digits) / [cs.se]
vzn
CC BY-SA 3.0
2017-12-08T09:06:32.077Z
@Kaveh small comment -- since you don't know $m$, he's not really giving you the second TM: he's giving you 1 explicit TM and a *proof* that an alternative TM must also exist.
Aryeh
CC BY-SA 2.5
2010-10-06T17:11:57.087Z
You can use latex in your questions to make them more readable.
Dave Clarke
CC BY-SA 2.5
2010-10-06T17:35:24.820Z
The argument is correct, but not constructive. The person is not giving you a TM, he is giving you two TMs and tells you that one of them is computing the function you want, but doesn't know which one.
Kaveh
CC BY-SA 2.5
2010-11-23T13:33:25.320Z
Your version is computable. However, I misread and accidentaly found a version that I believe is uncomputable. The only change: instead of exactly n zeroes, ask whether π has at most n zeroes. If it really does, I believe you cannot confirm it, since π has an infinite number of digits and there (seems?) to be no pattern re-appearing.
chazisop
<computability>
(False?) proof for computability of a function?
Mike B.
# (False?) proof for computability of a function?

(Asked by: username_0 on 2010-10-06)

Consider $f(n)$, a function that returns 1 iff $n$ zeros appear consecutively in $\pi$. Now someone gave me a proof that $f(n)$ is computable:

> Either for all n, $0^n$ appears in $\pi$, or there is a m s.t. $0^m$ appears in $\pi$ and $0^{m+1}$ does not.
> For the first possibility $f(n) := 1$; For the second one $f(n) := 1$ iff $n \leq m$, 0 otherwise.

The author claims that this proves computability of $f(n)$, as there exists an algorithm to compute it.

Is this proof correct?

**Tags:** computability
> **Comments:**
> **username_4**: You can use latex in your questions to make them more readable.  
> **username_5**: The argument is correct, but not constructive. The person is not giving you a TM, he is giving you two TMs and tells you that one of them is computing the function you want, but doesn't know which one.  
> **username_6**: Your version is computable. However, I misread and accidentaly found a version that I believe is uncomputable. The only change: instead of exactly n zeroes, ask whether π has at most n zeroes. If it really does, I believe you cannot confirm it, since π has an infinite number of digits and there (seems?) to be no pattern re-appearing.  
> **username_1**: I corrected a Wikipedia page once which made a related mistake, asserting that the existence of Chaitin's constant proved the existence of "uncomputable integers".  
> **username_2**: these types of questions tend to be on "trivial languages". but note how usually a slight reformulation eg where the language is $f(n, k) = m$ where $m$ is a (or the 1st) location of the $0^k$ string or -1 if there is no such string may be undecidable. see also [how can it be decidable that $\pi$ has some sequence of digits?](http://cs.stackexchange.com/questions/367/how-can-it-be-decidable-whether-pi-has-some-sequence-of-digits) / [cs.se]  
> **username_3**: @Kaveh small comment -- since you don't know $m$, he's not really giving you the second TM: he's giving you 1 explicit TM and a *proof* that an alternative TM must also exist.  

---

## 5 answers

### Answer by username_7 on 2010-10-06. Score: 23

Think of it this way, Mike: This proof is "branching" into multiple possible cases, one of which has to be true (using the law of excluded middle that for every proposition $p$, either $p$ is true or $\neg p$ is true). But at the end of each of these branches, you always manage to prove that the function $f$ is computable. Therefore, no matter which of the cases actually holds in real life, $f$ must be computable. (However, the precise reason *why* $f$ is computable will be different, depending on the branch.)


---

### Answer by username_8 on 2010-10-06. Score: 16

It is correct. This is the same as the following: define $f(x)$ to be the constant function $x \mapsto 0$ if God exists, and $x \mapsto 1$ if God doesn't exist. The resulting function is a constant function, thus computable. What you may not be able to do is to give that function, but the function itself is computable.

Here, one of the two possibilities is true : either there exists such an $m$, or it doesn't. The function is either the constant function $x \mapsto 1$ or a simple threshold function, defined with $m$.

> **Comments:**
> **username_5**: I would replace "if God exists" with $P \neq NP$. :)  
> **username_0**: Ok, sorry for the misunderstanding, I'm not having trouble with the non-constructivity of the proof. The problem I have is, that we (or at least I) don't know whether $m$ is computable or not. Why isn't it necessary to prove that?  
> **username_10**: It doesn't really make sense to talk about whether an integer is computable or not. Whatever value m takes, there is a Turing machine that outputs it. Finding it might be hard of course, but this isn't so different from the general situation: finding algorithms is hard, which is the fact that keeps many of us employed.  
> **username_0**: I still don't get it. What Turing machine could possibly output this m? Not just would it have to show that $0^m$ appears in $\pi$, more than that it would have to verify that $0^{m+1}$ doesn't - and that is IMO the problem.  
> **username_8**: This is the constructive way you're talking about.  If I give you a machine that outputs such an $m$, it doesn't need to *convince you* that this is the right $m$, as it is *the* machine for outputing such an $m$ (well, *a* machine at least).  This is the same as God's example (which BTW comes from Sipser): if the machine outputs $0$, it doesn't need to convince you that God doesn't exist.  It is just the case.  
> **username_11**: Mike, your task is not to compute $m$. See my answer below.  As for your reference to the halting problem: You are right. But you consider only one machine there; who said this was not computable? The uncomputable halting problem is, however, general: the function we consider there has to answer correctly for _all_ Turing machines.  The equivalent task in this setting here would be: Design such a function $f$ that takes a real number $r$ (not possible on TMs, but let us assume it was) and some integer $m$ and outputs $1$ iff at least $m$ zeros occurr in the decimals of $r$.  
> **username_0**: Ok, thank you very much for your answers and your patience. I finally figured out my misunderstandings, especially with "uncomputable constants". One last thingh: $h(x) = 1$ iff $CH$ is true, 0 otherwise. This function is computable, right?  
> **username_8**: This is a constant function in either case, so yes.  
> **username_9**: I don't get this. Is ExistGod->Bool a computable function? With this logic I can replace that with HaltsMyProgramOnInputX->Bool. And then f(x) solves halting problem for this particular program and input.  
> **username_8**: @CowboyTrader: That's correct. The function that takes an input and returns the function that returns true if the program stops on that input is, however, not computable.  

---

### Answer by username_11 on 2010-10-06. Score: 14

I think -- and hope -- that every computer science student is confronted with this problem which feels like a paradoxon. It is a very good example for the difference of computable in TCS sense and computable in a practical sense.

My thoughts back then were: "Yea, if I *knew* the answer, it would obviously be computable. But how to find out?" The trick is to rid yourself from the illusion that you have to find out wether $\pi$ has this property or not. Because this, obviously (read: imho), cannot be done by a Turing machine (as long as we do not have more knowledge than we have about $\pi$).

Consider your definition for computability: we say $f$ is (Turing-)computable if and only if $\exists M \in TM : f\_M = f$. That is you only have to show *existence* of an appropriate Turing machine, not *give one*. What you -- we -- try to do there is to compute the Turing machine that computes the required function. This is a way harder problem!

The basic idea of the proof is: I give you an infinite class of functions, all of them computable (to show; trivial here). I prove then that the function you are looking for is in that class (to show; case distinction here). q.e.d.

> **Comments:**
> **username_12**: It is trivial to write code that takes a proposition, and then finds a proof of it in ZFC if one exists. Take metamath and feed all possible proofs into it until it reports that one is a proof that pi has an sequence of zeros of arbitrary length. Run it concurrently with search for there exists an n s.t. pi doesn't have a sequence of zeros of length n. If one of those has a proof of finite length in ZFC, it will be found in finite time, even if not before the heat death of the universe.  
> **username_11**: @prosfilaes I don't see how that relates to the answer, at all.  
> **username_12**: You claimed that finding out whether π has this property cannot be done by a Turing machine. My point is that all finite proofs in ZFC can be enumerated by a Turing machine, so if provable, a Turing machine can find if π has this property.  
> **username_11**: Even if dragging ZFC proofs into this were to help at all (I'm not convinced -- why _that_ framework?) _and_ it was decidable whether one of the enumerated proofs actually proves the claim (which I doubt), it would only give you a semi-decider. Here, we'd need a decider.  
> **username_12**: You doubt that it is decidable whether one of the enumerated proofs actually proves the claim? Metamath is a program that takes an proof (with ZF/ZFC being the best supported theory) and decides whether the proof proves the claim.  
> **username_11**: @prosfilaes As I said: Even assuming all of that is true -- to reiterate: that there _is_ a ZFC proof, that you can enumerate them, and check each of them -- you still only get a semi-decider. As such, I fail to see how this relates to my answer, or the question.  
> **username_12**: You said "Because this, obviously (read: imho), cannot be done by a Turing machine (as long as we do not have more knowledge than we have about π)." This can be done by a Turing machine, provided a proof exists, and if it doesn't, that's not really about how much knowledge we have about pi.  
> **username_12**: Actually, it's not a semidecider; a TM to check an arbitrary proposition is, but a TM with no arguments, to answer a question with no variables, either decides or not. Pedantic, but quite parallel to the original question.  

---

### Answer by username_10 on 2010-10-06. Score: 9

Yes, thats right, its computable. The issue is that your function really isn't producing the solution to an infinite family of problems, the way (say) a function computing a solution to the halting problem is -- so there is no issue about computation. Instead, you are representing in function-form some single mathematical fact with finite representation -- either an integer, or the fact that f is the constantly 1 function

It is possible to encode the halting problem in individual *real* numbers, like Chaitan's constant $\Omega$, but integers always have finite representations and so can be encoded as Turing Machines.

Finding the correct algorithm of course might be a hard problem. But finding correct algorithms is usually hard!


---

### Answer by username_13 on 2015-06-03. Score: 3

post a bit old, but wanted to post another answer.
This is a non-constructive proof (or argument) of computability. It simply says that the function must exist in some sense since i can represent it (or more correctly index it), in the set (or universe) of computable functions. However it neither constructs the machine itself (i.e the algorithm), nor the index (assuming an effective enumeration of computable machines). The english phrase "thanks for nothing", seems in these cases most appropriate, like the following:
-- Look, I proved there is water somewhere! 

Now you can be happy, while dying from thirst!

People in the history of mathematics have argued quite a bit on the actual validity (or range of validity) and meaning of such arguments. The end result is that the same type of arguments re-appear in the incompleteness theorems of Goedel and turn against this  "closed universe assumption".
If you dont like these arguments so much i would not blame you.


---

