Re: [math-fun] Is the Continuum Hypothesis a) really true or really false, or b) something else ?
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
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