Re: [math-fun] Is the Continuum Hypothesis a) really true or really false, or b) something else ?
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
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
The proof that it runs >t steps only requires a t+1 step simulation. This should be doable on a regular TM in space gD+ht+i and time about jt*(kD^2+lt+m) where g,h,i,j,k,l,m are small constants, D is the size of the target machine description, and t is time. If you can store the simulated tape on a second prover tape, then the time per simulated step is only kD^2+m, the time to scan the description and match the label of the next state. Maybe add a log term to count the steps. Rich --------- Quoting Victor Miller <victorsmiller@gmail.com>:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Right. Proving that it runs for at least t steps is easy, for any t. Proving that it runs forever is the hard part… - Cris
On May 2, 2018, at 2:17 PM, rcs@xmission.com wrote:
The proof that it runs >t steps only requires a t+1 step simulation. This should be doable on a regular TM in space gD+ht+i and time about jt*(kD^2+lt+m) where g,h,i,j,k,l,m are small constants, D is the size of the target machine description, and t is time. If you can store the simulated tape on a second prover tape, then the time per simulated step is only kD^2+m, the time to scan the description and match the label of the next state. Maybe add a log term to count the steps.
Rich
--------- Quoting Victor Miller <victorsmiller@gmail.com>:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
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
On Tue, May 1, 2018 at 7:19 AM, Cris Moore <moore@santafe.edu> wrote:
... 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. ...
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? ...
To answer the question posed, shouldn't we ask if, given any *particular* TM, there exists *some* consistent system/set of axioms that can prove whether it halts or not? I was under the impression that the answer here was "yes", regardless of any individual consistent system being unable to tackle the general problem.
On Tue, May 1, 2018 at 1:13 PM, James Davis <lorentztrans@gmail.com> wrote:
On Tue, May 1, 2018 at 7:19 AM, Cris Moore <moore@santafe.edu> wrote:
... 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. ...
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? ...
To answer the question posed, shouldn't we ask if, given any *particular* TM, there exists *some* consistent system/set of axioms that can prove whether it halts or not? I was under the impression that the answer here was "yes", regardless of any individual consistent system being unable to tackle the general problem.
The problem is when you have nonstandard natural numbers. It's perfectly valid, for instance, to have a Turing machine halt after ω + 3 steps. You can say, "oh, but we use the unique standard model defined by the second-order theory", but then the second order theory has to live in some universe, and there are universes in which what's uncomputable in your universe can be computable in mine: http://jdh.hamkins.org/every-function-can-be-computable/ https://johncarlosbaez.wordpress.com/2016/04/02/computing-the-uncomputable/ So as soon as you move away from "only physically implementable math is real", then you have do deal with all these other models. -- Mike Stay - metaweta@gmail.com http://www.math.ucr.edu/~mike http://reperiendi.wordpress.com
participants (6)
-
Cris Moore -
hbaker1 -
James Davis -
Mike Stay -
rcs＠xmission.com -
Victor Miller