Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

BB(3, 3) is Hard

sligocki.com

Post reply on HN
Print view View original

91–100 of 146 posts

Re: BB(3, 3) is Hard

#91

Post by klempner »

nine_k wrote: post #29
hakuseki wrote: post #23

Earlier quoted context omitted.

> there is nothing in principle stopping us from running this machine for BB(748) steps How would we compute the value of BB(748)?

Computing BB(748) would be best, but if we could get an upper-bound estimate that's reasonably close, that would suffice.

How can you come up with an "upper bound estimate" without having some idea of the structure of the computation of the specific 748 state Turing Machine in question?

Imagine you had an oracle telling you BB(748) excluding this machine. How do you get an upper bound on the runtime of this machine?

(There is an answer: this is surely not the optimal construction, and so such an oracle would give you an answer for some smaller ZFC machine which you could likely use to extrapolate a value for this machine. However, eventually you'll find a minimal state ZFC machine and that won't work anymore.)

Re: BB(3, 3) is Hard

#92

Post by konstantinua00 »

abetusk wrote: post #73

BB(3,3) is busy beaver (BB) problem, a subset of Turing machines (TM) [0], with 3 states (A,B,C) and three symbols (0,1,2) that can be written onto the infinitely long tape. An additional criteria for a Busy Beaver-like Turing machine is that there is a "halt" state, which can be seen in the article's table for state C reading input 0. The table in the article (under "The Machine" section) describes the state on the…

> An additional criteria for a Busy Beaver-like Turing machine is that there is a "halt" state, which can be seen in the article's table for state C reading input 0.

Technically, that's "halt" _transition_. There's supposed to be an implied Halt state - but it's straight up easier to treat halting as smth like "invalid instruction" hardware exception.

> The line that says "A(a,b,c) = 0^\inf 12^a 11^b While yes, it can be an input - instead it is mostly treated as "intermediate" state of the tape. TM is quite low level, so various abstractions are welcome. If you can prove that input you're interested in (empty tape) gets to your abstraction and stays there - stuff gets simpler.

> but I don't quite understand what the "One of very useful abstractions without much cost is to keep track of direction head was travelling in. 1) instead of "head is on this cell and state kept outside" it allows inline notation, while visually pointing to the cell the head is on 2) it's mostly explained as representation of TM with 2 stacks which is easy to implement and run 3) direction is already encoded in the transitions "1LC == That allows nice rewrite rules like "B> 1 -> 1 B>" that simplify manual playthrough, and it works nice with intuition - e.g. B> keeps going right all the way until it encounters 0, like a ship with a pointy nose through the water.

And, well, additional state helps a lot of the time.

Re: BB(3, 3) is Hard

#93

Post by neilkk »

FartyMcFarter wrote: post #84
sligocki wrote: post #35

Earlier quoted context omitted.

Yeah, I've oversimplified a bit with this title. The more accurate statement is in the first paragraph of the article: "Solving the BB(3, 3) problem is at least as hard as solving this Collatz-like problem." I also agree somewhat on the one trajectory vs. multiple trajectories point. However, note that (assuming we live in the world where this TM never halts) proving a single trajectory in this system is "harder" tha…

> "Solving the BB(3, 3) problem is at least as hard as solving this Collatz-like problem." > How hard is this Collatz-like problem? Well, let's see if anyone can solve it :) I thought John Conway already proved that all instances of the halting problem can be converted to a Collatz-like problem [1]. So one could say this about all BB values, not just BB(3, 3). Some will be easy, some will be hard, but all are reducib…

I think the point here is that it was not known whether all 3,3 halting problems are reducible to trivial Collatz-like problems. Unless someone is able to observe that sligicko's is actually trivial, then this provides a counterexample.

Re: BB(3, 3) is Hard

#94

Post by konstantinua00 »

FartyMcFarter wrote: post #82
dchftcs wrote: post #78

Earlier quoted context omitted.

I think you got the direction reversed. Here you have a reduction of B(x,y) to the halting problem, which only shows that (a subset of) halting is at least as hard as B(x,y). You need a reduction from collatz to halting to B(x,y) instead. Collatz to halting is trivial, halting to B(x,y) seems a bit less so - you need to precisely define which subset of halting problems can be reduced from Collatz yet is no harder tha…

My understanding is that this blog post converts a specific instance of the halting problem into a Collatz-like problem. It starts with a description of a specific Turing machine, and presents a Collatz-like problem that, if solved, also answers whether that Turing machine halts or not. Isn't this almost exactly what Conway did, with the only difference being that Conway's proof works for all Turing machines, and thi…

Are you talking about FRACTRAN?

Halting problem being reduced to [subset of collatz-like problems] says nothing about uncomputability of [all the rest of collatz-like problems] and even less about [does single specific collatz-like problem halt]

The only consquence is that "most general" definition of collatz-like problem as a whole is uncomputable

Re: BB(3, 3) is Hard

#95

Post by __s »

thethimble wrote: post #60
onetimeuse92304 wrote: post #26

Earlier quoted context omitted.

> This is not just some abstract result; this is a computation that we can perform and draw a real value from. No, this isn't a computation we can perform. There isn't enough energy in the visible Universe we can use to increase entropy to run this computation. Even if we built a computer that would use all matter and energy in the Universe, even if the computer only had one task and even if it ran the task as effici…

But if the universe is infinitely large then any finite thing should fit in it, right? Or are we saying that BB(748) can be infinite?

It can be finite, but you have to definitively prove the non halting cases are infinite (which, being infinite, can't be computed with brute force)

Look, you're arguing the collatz cobjecture can be proven by counting up by 1 & seeing when a number hits a loop without reaching 1 (which, if there is such a case, would eventually prove via refutation, but if not, you'd never know if you were about to hit an answer or not)

Mathematical uncomputability for problems with answers is a thing. Read up on Gödel's Incompleteness Theorem

& some conjectures have been refuted by computers: https://math.stackexchange.com/questions/2638897/conjectures... but until it's done the question remains unknown

Re: BB(3, 3) is Hard

#96

Post by FartyMcFarter »

neilkk wrote: post #93
FartyMcFarter wrote: post #84

Earlier quoted context omitted.

> "Solving the BB(3, 3) problem is at least as hard as solving this Collatz-like problem." > How hard is this Collatz-like problem? Well, let's see if anyone can solve it :) I thought John Conway already proved that all instances of the halting problem can be converted to a Collatz-like problem [1]. So one could say this about all BB values, not just BB(3, 3). Some will be easy, some will be hard, but all are reducib…

I think the point here is that it was not known whether all 3,3 halting problems are reducible to trivial Collatz-like problems. Unless someone is able to observe that sligicko's is actually trivial, then this provides a counterexample.

> I think the point here is that it was not known whether all 3,3 halting problems are reducible to trivial Collatz-like problems.

True, but it still isn't known either way. Nothing changed in that regard.

Re: BB(3, 3) is Hard

#97

Post by [deleted] »

konstantinua00 wrote: post #94
FartyMcFarter wrote: post #82

Earlier quoted context omitted.

My understanding is that this blog post converts a specific instance of the halting problem into a Collatz-like problem. It starts with a description of a specific Turing machine, and presents a Collatz-like problem that, if solved, also answers whether that Turing machine halts or not. Isn't this almost exactly what Conway did, with the only difference being that Conway's proof works for all Turing machines, and thi…

Are you talking about FRACTRAN? Halting problem being reduced to [subset of collatz-like problems] says nothing about uncomputability of [all the rest of collatz-like problems] and even less about [does single specific collatz-like problem halt] The only consquence is that "most general" definition of collatz-like problem as a whole is uncomputable

[deleted]

Re: BB(3, 3) is Hard

#98

Post by neilkk »

FartyMcFarter wrote: post #96
neilkk wrote: post #93

Earlier quoted context omitted.

I think the point here is that it was not known whether all 3,3 halting problems are reducible to trivial Collatz-like problems. Unless someone is able to observe that sligicko's is actually trivial, then this provides a counterexample.

> I think the point here is that it was not known whether all 3,3 halting problems are reducible to trivial Collatz-like problems. True, but it still isn't known either way. Nothing changed in that regard.

'trivial' isn't a mathematical concept. If no one has shown why this problem is trivial, it isn't trivial.

Re: BB(3, 3) is Hard

#99

Post by chriswarbo »

onetimeuse92304 wrote: post #26
tybug wrote: post #21

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…

> This is not just some abstract result; this is a computation that we can perform and draw a real value from. No, this isn't a computation we can perform. There isn't enough energy in the visible Universe we can use to increase entropy to run this computation. Even if we built a computer that would use all matter and energy in the Universe, even if the computer only had one task and even if it ran the task as effici…

I agree with your overall point, but note that computation doesn't actually increase entropy (we can do reversible computation, e.g. using quantum gates, Toffoli gates, billiard-ball computers, etc.)

Re: BB(3, 3) is Hard

#100

Post by chriswarbo »

kuboble wrote: post #58
tybug wrote: post #27

Earlier quoted context omitted.

I suppose I did! I was having a hard time reconciling this with the intuition that BB(n) is in principle "computable" (colloquially speaking) for any n - my thinking went that if I want to compute BB(n), I can enumerate turing machines and run them until they halt, since infinitely looping machines are excluded from BB(n). But of course I have now reduced this to the halting problem! How do you know when you're "done…

Isn't the easier proof that BB(n) isn't computable something like - assume BB is computable - there exist a TM called X that computes the function - it has K states - X(K+1) produces BB(K+1) but from the definition of BB our machine cannot produce a result higher than BB(K).

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){}")

Post reply on HN