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