131–140 of 146 posts
One thing I see is that they effectively don't need to use a halt state. So maybe a 3-state BBB is sort of similar to a 4-state BB in that sense. What is there more to it?
Earlier quoted context omitted.
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.
Oh dear.
Earlier quoted context omitted.
It’s an unknown integer, whose value depends on the consistency of ZFC. Let me show you why this is circular. I can define another integer N which is 1 if there exists a proof of the inconsistency of ZFC and 0 if there doesn’t (note that BB(754) already encodes this information). Then I can define a program that determines the consistency of ZFC thusly: if N=1, I define the program to immediately return false. If N=0…
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.
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?
Is there any intution for why BBB (beeping busy beavers) can run for much longer (before quasihalting?) One thing I see is that they effectively don't need to use a halt state. So maybe a 3-state BBB is sort of similar to a 4-state BB in that sense. What is there more to it?
IIRC basically this same construction means that while knowing BB(N) lets you (very slowly) compute the halting problem for programs up to size N, knowing BBB(N) lets you (even more slowly) compute the halting problem for turing machines supplied with a halting oracle up to that size.
Earlier quoted context omitted.
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.
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 _sou…
Earlier quoted context omitted.
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 _sou…
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.
Earlier quoted context omitted.
There's a difference between a TM/algorithm/etc. that computes a function , like BB(n) (for all Natural numbers n); versus computing a particular value , like BB(748). For comparison, there is no TM which computes the halting function halts(p) (for all programs p); but it's easy to compute particular values like halts("exit") or halts("while(true){}")
Yes. My reasoning applies to a function n=> BB(n) Isn't that what "the function is not computable" is about? Or is the thesis that the value of BB(748) can't be computed?
Earlier quoted context omitted.
> if it halts, we have proven by Thm 1 that ZFC is inconsistent. If not, we have similarly proven that ZFC is consistent. The second part is wrong. We can't physically check that a program runs forever - this requires an infinite amount of time.
His point is if you know the value of BB(748) then you don't have to wait forever, just BB(748) steps, as after that the Turing machine is guaranteed not to halt. The problem with his argument is that we don't know the value of BB(748). Not only that, it is incomputable, which resolves the contradiction.
I'm hoping someone can enlighten me here. My understanding is that there is a turing machine of 748 states [0], which halts iff ZFC is inconsistent (Thm 1). But this machine is a "physical" object, in the sense that we can materialize it on a computer and run it. Though we don't have the computing power for this currently, there is nothing in principle stopping us from running this machine for BB(748) steps: if it ha…
The issue is the "run the turing machine for BB(748) steps" part. We don't know what BB(748) is. If the god of busy beavers came to us and told us that value, then we could (in theory) run the TM that long and just like you say, that would prove whether ZFC is consistent. But in order for us mere mortals to compute BB(748) we would effectively need to figure out if this specific 748-state TM ever halted (along with a…
All the parent says: if it's possible even theoretically to learn the answer to the BB problem then we've proven something that cannot be proven, as shown by Godel incompleteness.
Earlier quoted context omitted.
Oh dear.
Excuse me?