Re: [math-fun] Is the Continuum Hypothesis a) really true or really false, or b) something else ?
Doesn't it get worse? Aren't there *particular* TM's whose haltingness can be arbitrarily chosen? I.e., "TM XYZ halts" becomes an axiom *independent* of the rest of arithmetic? -----Original Message-----
From: Cris Moore <moore@santafe.edu> Sent: May 1, 2018 6:19 AM To: hbaker1 <hbaker1@pipeline.com>, math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Is the Continuum Hypothesis a) really true or really false, or b) something else ?
I agree with all this: indeed my favorite way to prove the first Incompleteness Theorem is the undecidability of the Halting Problem. For any set of axioms, there is a Turing machine which 1) never halts and 2) that set of axioms cannot prove that it never halts. Otherwise the Halting Problem would be decidable.
But don’t you agree that the Halting Problem has a definite truth value? In other words, that a given Turing machine (with a given input) either runs forever or doesn’t, regardless of our ability to prove it? Or does the unprovability of non-halting make you a pluralist on this topic — that if we can’t prove non-halting in ZFC (say), then we can have it either way?
- Cris
On May 1, 2018, at 7:02 AM, hbaker1 <hbaker1@pipeline.com> wrote: But that's the heart of the incompleteness theorem: *any* theory strong enough to describe number theory or Turing Machines has certain true statements that have no (finite) proofs.
Recall that proofs are finite sequences generated by non-deterministic machines from axioms and rules of inference in an attempt to list all theorems.
By a strong analogy to diagonalization of an attempt to list all of the numeral sequences of the real numbers, we can construct a new real number not on the list; and hence we can construct a new truth not on the list of provable theorems.
-----Original Message-----
From: Cris Moore <moore@santafe.edu> Sent: Apr 30, 2018 10:42 PM To: hbaker1 <hbaker1@pipeline.com>, math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Is the Continuum Hypothesis a) really true or really false, or b) something else ?
Right, the Halting Problem is asymmetric: there’s a finite proof of halting if it halts, but not necessarily a finite proof that it runs forever if it runs forever.
Cris
On Apr 30, 2018, at 11:02 PM, hbaker1 <hbaker1@pipeline.com> wrote:
Turing Machines which halt: "recursively enumerable" == "RE" Turing Machines which don't halt: complement of RE.
Turing proved that they aren't the same sets.
Thus, RE sets are kind of "fractals", in that their boundaries are a little difficult to determine -- at least from one direction.
-----Original Message-----
From: Cris Moore <moore@santafe.edu> Sent: Apr 30, 2018 2:28 PM To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Is the Continuum Hypothesis a) really true or really false, or b) something else ?
On Apr 30, 2018, at 3:21 PM, Cris Moore <moore@santafe.edu> wrote:
However, we should be careful, since even questions about the halting of Turing machines — which are certainly first-order claims about the integers — can be independent of ZFC: https://www.scottaaronson.com/busybeaver.pdf <https://www.scottaaronson.com/busybeaver.pdf> <https://www.scottaaronson.com/busybeaver.pdf <https://www.scottaaronson.com/busybeaver.pdf>>
Sorry, continuing: note that if a Turing machine halts in finite time, there is a finite proof of that fact — namely, run it and see what happens. But if it runs forever, proving that it does so might be difficult.
But surely there is a truth of the matter here! The Turing machine will either run forever, or it won’t. I find it hard to be a pluralist here.
- Cris
No, because if a TM halts we can prove that just by running it. But if you mean “TM XYZ runs forever”, then yes, that can be an independent axiom. - Cris
On May 1, 2018, at 8:08 AM, hbaker1 <hbaker1@pipeline.com> wrote:
Doesn't it get worse?
Aren't there *particular* TM's whose haltingness can be arbitrarily chosen? I.e., "TM XYZ halts" becomes an axiom *independent* of the rest of arithmetic?
-----Original Message-----
From: Cris Moore <moore@santafe.edu> Sent: May 1, 2018 6:19 AM To: hbaker1 <hbaker1@pipeline.com>, math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Is the Continuum Hypothesis a) really true or really false, or b) something else ?
I agree with all this: indeed my favorite way to prove the first Incompleteness Theorem is the undecidability of the Halting Problem. For any set of axioms, there is a Turing machine which 1) never halts and 2) that set of axioms cannot prove that it never halts. Otherwise the Halting Problem would be decidable.
But don’t you agree that the Halting Problem has a definite truth value? In other words, that a given Turing machine (with a given input) either runs forever or doesn’t, regardless of our ability to prove it? Or does the unprovability of non-halting make you a pluralist on this topic — that if we can’t prove non-halting in ZFC (say), then we can have it either way?
- Cris
On May 1, 2018, at 7:02 AM, hbaker1 <hbaker1@pipeline.com> wrote: But that's the heart of the incompleteness theorem: *any* theory strong enough to describe number theory or Turing Machines has certain true statements that have no (finite) proofs.
Recall that proofs are finite sequences generated by non-deterministic machines from axioms and rules of inference in an attempt to list all theorems.
By a strong analogy to diagonalization of an attempt to list all of the numeral sequences of the real numbers, we can construct a new real number not on the list; and hence we can construct a new truth not on the list of provable theorems.
-----Original Message-----
From: Cris Moore <moore@santafe.edu> Sent: Apr 30, 2018 10:42 PM To: hbaker1 <hbaker1@pipeline.com>, math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Is the Continuum Hypothesis a) really true or really false, or b) something else ?
Right, the Halting Problem is asymmetric: there’s a finite proof of halting if it halts, but not necessarily a finite proof that it runs forever if it runs forever.
Cris
On Apr 30, 2018, at 11:02 PM, hbaker1 <hbaker1@pipeline.com> wrote:
Turing Machines which halt: "recursively enumerable" == "RE" Turing Machines which don't halt: complement of RE.
Turing proved that they aren't the same sets.
Thus, RE sets are kind of "fractals", in that their boundaries are a little difficult to determine -- at least from one direction.
-----Original Message-----
From: Cris Moore <moore@santafe.edu> Sent: Apr 30, 2018 2:28 PM To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Is the Continuum Hypothesis a) really true or really false, or b) something else ?
> On Apr 30, 2018, at 3:21 PM, Cris Moore <moore@santafe.edu> wrote: > > However, we should be careful, since even questions about the halting of Turing machines — which are certainly first-order claims about the integers — can be independent of ZFC: https://www.scottaaronson.com/busybeaver.pdf <https://www.scottaaronson.com/busybeaver.pdf> <https://www.scottaaronson.com/busybeaver.pdf <https://www.scottaaronson.com/busybeaver.pdf>>
Sorry, continuing: note that if a Turing machine halts in finite time, there is a finite proof of that fact — namely, run it and see what happens. But if it runs forever, proving that it does so might be difficult.
But surely there is a truth of the matter here! The Turing machine will either run forever, or it won’t. I find it hard to be a pluralist here.
- Cris
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
Cris Moore -
hbaker1