Hacker News new | ask | show | jobs
by l33t7332273 978 days ago
It is not circular. Such a Turing machine clearly exists.

What we’ve seen is that there plainly exists a Turing machine which halts iff ZFC is consistent.

All of the other window dressing you’ve added hasn’t changed that simple fact.

I agree that finding busy beaver numbers is the issue. I do not agree that the existence of a TM that halts iff ZFC is consistent is hard.

2 comments

You "clearly" is not so clear.

BB(754) is an uncomputable number. It's independent of ZFC, so an enumeration of all consequences of axioms of ZFC doesn't contain it. How is that supposed TM of yours is supposed to know whether it has run BB(754) steps or not?

Oh, but other slightly bigger TMs exist – lets say in class TM(860) for the sake of an example – that might halt with after a more steps than BB(754). This _sounds_ intuitive. But: how do you prove that? It might be that all TM(860)s either halt within BB(754) steps or then run forever. There indeed might be some that halt in finite steps after BB(754), but that is not guaranteed! You need to prove it. But with what?

Oops, never mind, there exists a simple construction that you can perform to each TM(754) that clearly extends BB(754) a finite amount. Maybe you are corrent that such Turing machine exists. But seems that identifying it isn't possible in ZCF.
I agree that the problem is identifying the machine, not its existence.
Oh dear.
Excuse me?
I’m saying that all you’ve proven is that if you know a priori whether ZFC is consistent, you can construct a Turing machine that returns this value. If you consider that to be window dressing I don’t know what else I can tell you.
I’m saying that it doesn’t matter if you know if ZFC is consistent; I have proven there exists a TM that halts iff it is.