Suppose that a Turing machine doesn't halt. For any t, there's a proof that it runs longer than t steps. But the size of the proof, as a function of t can grow faster than Ackerman's function. So it would be completely impractical to use such proofs. Victor PS. I remember Greg Chaitin using an argument like this in one of his monographs. I'll see if I can dig up a reference. On Tue, May 1, 2018 at 4:02 PM, 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