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

81–90 of 146 posts

Re: BB(3, 3) is Hard

#81

Post by [deleted] »

dchftcs wrote: post #78
FartyMcFarter wrote: post #74

> Therefore, solving the BB(3, 3) problem is at least as hard as solving this Collatz-like problem I don't understand why this is surprising, in fact it seems trivially provable. Aren't all BB(x, y) problems reducible to Collatz-like problems? BB(x, y) problems are trivially converted to the halting problem: - find all machines with x states and y symbols that halt, set all the non-halting ones aside. - run all the h…

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…

[deleted]

Re: BB(3, 3) is Hard

#82

Post by FartyMcFarter »

dchftcs wrote: post #78
FartyMcFarter wrote: post #74

> Therefore, solving the BB(3, 3) problem is at least as hard as solving this Collatz-like problem I don't understand why this is surprising, in fact it seems trivially provable. Aren't all BB(x, y) problems reducible to Collatz-like problems? BB(x, y) problems are trivially converted to the halting problem: - find all machines with x states and y symbols that halt, set all the non-halting ones aside. - run all the h…

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 this proof only works for a specific Turing machine?

Re: BB(3, 3) is Hard

#83

Post by [deleted] »

Xcelerate wrote: post #79

The halting problem often seems to “block” a lot of approaches to algorithmic information theory and induction that are based upon computable programs. However, is there any research on whether the halting problem actually has any sort of material influence on our ability to perform real-world induction? For instance, if an oracle could tell us whether any given monotone universal Turing machine has reached a point i…

[deleted]

Re: BB(3, 3) is Hard

#84

Post by FartyMcFarter »

sligocki wrote: post #35
nneonneo wrote: post #20

Probably more accurate to say that BB(3, 3) looks hard; that is, it encodes a Collatz-type problem, and many Collatz-type problems are very hard to solve (including, of course, the classic Collatz conjecture). However, this instance might not necessarily be hard. For one, the behaviour seems to be heavily biased; for another, we only have to consider a single trajectory instead of the trajectories for all integers (a…

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 reducible to Collatz-like problems IIUC.

[1] https://julienmalka.me/collatz.pdf

Re: BB(3, 3) is Hard

#85

Post by cubefox »

Xcelerate wrote: post #79

The halting problem often seems to “block” a lot of approaches to algorithmic information theory and induction that are based upon computable programs. However, is there any research on whether the halting problem actually has any sort of material influence on our ability to perform real-world induction? For instance, if an oracle could tell us whether any given monotone universal Turing machine has reached a point i…

I'm not sure this is what you mean but obviously in practice uncomputable problems don't differ from problems which are perfectly computable in theory but far too slow to be computed in practice.

Re: BB(3, 3) is Hard

#86

Post by smaudet »

Sharlin wrote: post #68
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…

It doesn't matter whether we can physically do it, as long as we can mathematically do it. In math running a TM for an arbitrary, finite number of steps is not a problem. The actual answer to OP's question was given in one of the other subthreads, namely: the result tells us that BB(754) is not computable in ZFC. Some 754-state TMs halt, others run forever, but there is no way to figure out (without an oracle) which…

>"It doesn't matter whether we can physically do it,"

Hmm. I'm not sure that I agree - philosophically if you could prove that something is computable mathematically and yet at the same time know that physically it cannot be done due to the laws of physics, I would say that imposes a "second order" halting problem.

By which I mean if you had some mathematical algorithm that could be proven to tell you some property of a system like halting, and you knew the number of steps required by that algorithm to produce that answer, if that number of steps is beyond the capacity of the physical world to provide, then there is a set of algorithms that can be proven to never be decidable.

I'm sure you are thinking, oh maybe we get more efficient, but to solve the bounding problem itself you must provide a constant time solution within the bounds of the universe, or else the "mathematical" solution is itself undecidable.

And even if you found a fast, low constant time solution (the holy grail), it still must be shown that the categories of problems are themselves infinite variations of finite categories, so that your low constant time solution could conceivably be applied within the limits of computation capacity, or else there will always be for some large enough set of problems some that are not decidable.

Re: BB(3, 3) is Hard

#87

Post by SCHiM »

Xcelerate wrote: post #79

The halting problem often seems to “block” a lot of approaches to algorithmic information theory and induction that are based upon computable programs. However, is there any research on whether the halting problem actually has any sort of material influence on our ability to perform real-world induction? For instance, if an oracle could tell us whether any given monotone universal Turing machine has reached a point i…

I'm a not educated in mathematics, so I can't know for sure if what I'm going to respond to your question is really relevant or not. But here it goes anyway.

I'm a security researcher, and I write my own fuzzers. Fuzzers are tools that automatically search for inputs that have security implications for the program that you're testing. They algorithmically generate and mutate inputs, feed them to a program, and observe what happens, tens/hundreds/thousands of times a second.

If an input crashes a program you can think of this as "halting" the program. To have a fuzzer that could find any or all bugs in any program you run it on, in a feasible amount of time, would surely involve solving the halting problem I think. And sure, even after billions of tests, people still manage to find bugs in image decoders, so the fuzzers we do have are not flawless.

At the same time, I have experienced in the real world that fuzzers manage to penetrate unexpectedly deep into complex programs if given enough time. The validation on input performed by the target under test, the limited memory and storage in a modern PC sort of helps to keep your fuzzer on the rails. Unless cryptography is involved, which are like computational tar-pits for fuzzers. Any well guarded/specified program acts as its own guardrail against needing to solve the halting problem for the fuzzer.

It convinced me of the following, regarding the finding of security bugs in programs:

1) Fuzzers are good at targeting programs that perform rigorous input validation, barring cryptography.

2) You don't need a fuzzer for a program that does not perform rigorous input validation (where the fuzzer doesn't necessarily work well.)

Re: BB(3, 3) is Hard

#88

Post by smaudet »

onetimeuse92304 wrote: post #63
thethimble wrote: post #60

Earlier quoted context omitted.

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?

Even if the universe is infinite, you can't use its infiniteness because you can't communicate partial results across infinite distances. It is natural to think that the more time you have, the further you can travel to, potentially. But when it comes to the universe, the opposite is actually true. The more time passes, the less of the universe you can reach. A lot of universe you can see today is actually not at all…

Computational capacity must not be able to travel faster than the speed of light, yes?

We are told that quantum entanglement cannot transmit information, I am unaware of how rigorously this has been proven/disproven, on the off chance there is something the scientists have missed, the requirement to travel might not be necessary. Either through some advanced entanglement (a novel approach or a not yet understood state of matter), or reaching for a more exotic theory, some additional dimension enabling warp or wormhole like behaviors.

Then computational capacity would depend on some ratio of power (to entangle, set up facilities, etc.) to time spent not doing these things, and might possibly have an upper limit, or not. Perhaps this is a halting problem in itself?

Re: BB(3, 3) is Hard

#89

Post by Sharlin »

smaudet wrote: post #86
Sharlin wrote: post #68

Earlier quoted context omitted.

It doesn't matter whether we can physically do it, as long as we can mathematically do it. In math running a TM for an arbitrary, finite number of steps is not a problem. The actual answer to OP's question was given in one of the other subthreads, namely: the result tells us that BB(754) is not computable in ZFC. Some 754-state TMs halt, others run forever, but there is no way to figure out (without an oracle) which…

>"It doesn't matter whether we can physically do it," Hmm. I'm not sure that I agree - philosophically if you could prove that something is computable mathematically and yet at the same time know that physically it cannot be done due to the laws of physics, I would say that imposes a "second order" halting problem. By which I mean if you had some mathematical algorithm that could be proven to tell you some property o…

If you insist that only tractable problems are decidable (or computable), you don't really get a nice or useful theory of computation. You need a more fine-grained hierarchy.

Almost all real numbers are uncomputable (computable reals have measure zero; in other words, the probability of an arbitrary real number being computable is exactly 0). BB(754) is uncomputable in this sense even though its definition is extremely concise. Still, its value could be computed by a machine stronger than a TM (but it would again be unable to compute its own BB problem).

Of the countable subset of reals that are computable, almost all are like 𝜋, in that computability does not mean being able to actually calculate or represent its exact numeric value in the physical world. Only that it's in principle possible to compute it to any precision desired – but of course this isn't possible in reality either. Only in math.

Then there are numbers that are unbelievably large, like 3^^^^3 or (the immensely larger) Graham's number G, which nevertheless admit an incredibly compact definition, and we can prove various properties of them. Yet their numeric representation would not fit in our future light cone (either in space or in time). Where do you draw the line? After all, G is an entirely ordinary natural number, and indeed almost all natural numbers are greater than G.

Complexity theory draws a line, somewhat arbitrarily, between polynomial-time and superpolynomial-time problems, the former being tractable and the latter intractable. But a number might be easily defined in terms of a tractable function and still be entirely unfeasible to ever calculate or represent in the physical world. (Such a number wouldn't even have to be particularly large if the function that defines it grows sufficiently slowly.)

Nowhere is there a distinction made between "computable in reality" and "only computable in math", because it's impossible to formally define such a distinction. Some numbers are obviously within our reach, almost all others obviously aren't. In between there's a huge gray area.

Re: BB(3, 3) is Hard

#90

Post by [deleted] »

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…

[deleted]
Post reply on HN