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

111–120 of 146 posts

Re: BB(3, 3) is Hard

#111

Post by [deleted] »

Pet_Ant wrote: post #107
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…

Why does BB sometimes take one number and sometimes 2? What is the difference between BB(3,3) and BB(3)?

[deleted]

Re: BB(3, 3) is Hard

#112

Post by smaudet »

Sharlin wrote: post #89
smaudet wrote: post #86

Earlier quoted context omitted.

>"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 extreme…

Hmm, I think its the same problem, you are somewhat arbitrarily drawing the line between "math" and the universe (or maybe I'm agreeing with you and don't realize it).

A halting/decide-able problem is one that is precisely about tractability - does it end, and can you decide that. The maths is about whether there is a tractable solution, in theory ignoring any energy/mass requirements.

The maths of the maths of the tractability issue is also one of tractability - if you provide an infinite solution to an infinite problem then is it a solution or an admission of defeat? You can't even decide if you can decide that you can decide.

If there is no maths for the maths for the decidability question of is it tractable (not even energy computeable), then in my mind there is no difference between the two, i.e. you have no higher order reduction with which to express the lower order problem. Without a constant time solution, there may not be enough math to express the solution to the problem, i.e. this may just be another set of infinities, as you mentioned the integers, irrational numbers, precision, etc. (which are lower order entities for which we have tractable mathematical solutions).

And the lower energy bound of the universe to the set of problems to me remains interesting, in that maths itself is an invented set of relationships, in the sense that the set is invented and less in that the relationships are invented (they exist but we value certain relationships over others, so the set is invented), so any maths that cannot survive and exist within the information space that is the universe is to some degree irrelevant - if there is no way to relate to it, does it exist? I think so, we simply lack the ability to process or observe it.

Consider, for instance, a constant time solution to the decideability problem, however the maths to prove it require a set of equations and theorems larger than the processing time of the universe. Then a solution exists, perhaps, but we will never discover it. It doesn't mean it doesn't exist, but it does not exist for us, and we can neither prove nor disprove that one exists.

Re: BB(3, 3) is Hard

#113

Post by reaperman »

concordDance wrote: post #76
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…

> Though we don't have the computing power for this currently I don't think you get how big BB748 is. To use a metaphor: If you took stuffed the entire observable universe full of computronium that can do more calculations in a fragment the size of a human cell than our entire civilization, then shrank that universe down to the size of a grain of sand and filled our entire universe with that, THEN did this once for e…

BB(6) might be too large even to store (let alone compute) using all the mass and energy of the universe. I think the computable limit if you converted all the mass in the observable universe to energy (E = mc^2) would be BB(5), assuming adherence to the Laundauer Limit[0].

After calculating this I found a quote in wikipedia[1]: "There is not enough computational capacity in the known part of the universe to have performed even S(6) operations directly." That cited this paper[2], which is probably better than my model at utilizing the total available physics of the universe for calculation purposes. Anyways, the mass of the known universe is on the order of 10^56 grams[3]. Converting this all to energy using E=mc^2 yields on the order of 10^70 Joules (10^88 electron volts). Setting or clearing a single bit of information requires at minimum 0.018 eV. That allows about 10^90 bits.

BB(6) may require on the order of 10^90^2 bit flips. So it is absolutely not computable using all the mass and energy in the universe. In fact, I don't think it's even storable using all the mass and energy in the universe.

I don't really understand Busy Beaver, so if I got any of this wrong please correct me for the record.

0: https://en.wikipedia.org/wiki/Landauer%27s_principle

1: https://en.wikipedia.org/wiki/Busy_beaver

2: https://arxiv.org/pdf/quant-ph/0110141.pdf

3: https://www.wolframalpha.com/input?i=mass+of+the+universe

Re: BB(3, 3) is Hard

#114

Post by eigenket »

smaudet wrote: post #88
onetimeuse92304 wrote: post #63

Earlier quoted context omitted.

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 stat…

> We are told that quantum entanglement cannot transmit information, I am unaware of how rigorously this has been proven/disproven

This has been rigorously proven [1]. If you are transmitting information you are doing something in addition to using entanglement.

[1] https://en.wikipedia.org/wiki/No-communication_theorem

Re: BB(3, 3) is Hard

#115

Post by tromp »

auggierose wrote: post #110
thaumasiotes wrote: post #106

Earlier quoted context omitted.

> Oh, see how I numbered this 1) and 2), not 0) and 1)? So what? > 2) it's not really clear if ℤ⁺ denotes ℕ or ℕ₀. On the contrary. ℕ is ambiguous between the positive integers and nonnegative integers, though in my experience it's usually the nonnegative integers. But ℤ⁺ is absolutely unambiguous. It's the positive integers. And since you frequently need to refer to the nonnegatives, it makes sense to have a symbol…

> So what? Well, it means I usually need either ℕ or ℤ, not ℕ₀. > And since you frequently need to refer to the nonnegatives It depends on the context. You don't use ℕ₀ much, if you agree that counting starts at 1. You then use either ℕ or ℤ, which just looks cleaner. No reason to complicate such a simple concept as {1, 2, 3, ...} with something complicated such as ℤ⁺. As I said before, to understand {1, 2, 3, ...},…

> if you agree that counting starts at 1

I argue that counting really starts at 0 in https://news.ycombinator.com/item?id=33022031

Re: BB(3, 3) is Hard

#116

Post by olddustytrail »

FartyMcFarter wrote: post #109
Pet_Ant wrote: post #107

Earlier quoted context omitted.

Why does BB sometimes take one number and sometimes 2? What is the difference between BB(3,3) and BB(3)?

BB(n) refers to Turing machines that have n states and 2 symbols. The version with two arguments lets you specify the number of states and the number of symbols respectively. So BB(n) = BB(n, 2) .

Are they fundamentally different or could you always map a BB(x,y) to a BB(z), where presumably z is much larger than x?

Re: BB(3, 3) is Hard

#117

Post by kuboble »

chriswarbo wrote: post #100
kuboble wrote: post #58

Earlier quoted context omitted.

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

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?

Re: BB(3, 3) is Hard

#118

Post by auggierose »

tromp wrote: post #115
auggierose wrote: post #110

Earlier quoted context omitted.

> So what? Well, it means I usually need either ℕ or ℤ, not ℕ₀. > And since you frequently need to refer to the nonnegatives It depends on the context. You don't use ℕ₀ much, if you agree that counting starts at 1. You then use either ℕ or ℤ, which just looks cleaner. No reason to complicate such a simple concept as {1, 2, 3, ...} with something complicated such as ℤ⁺. As I said before, to understand {1, 2, 3, ...},…

> if you agree that counting starts at 1 I argue that counting really starts at 0 in https://news.ycombinator.com/item?id=33022031

I guess it is the difference between measuring the size of a set, and labelling the elements of the set with a number. Both can be called "counting", but the meaning is different. The first of something should always be labelled 1, but obviously the empty set has size 0.

That's the main problem I have with using ℕ for {0, 1, 2, ...}. It's easy to get into the habit of writing stuff like x_0, ..., x_{n-1} for n elements, and that's just ugly. x_1, ..., x_n is much better and clearer. On the other hand, 0 is useful when it comes to measuring the size of something (an offset, for example, or age).

I think ℕ and ℕ₀ is a good way out of this dilemma. ℕ is the natural numbers, and ℕ₀ is the natural numbers with, well, 0.

The other way out of this dilemma is what most here prefer, I guess: It's to say a label is just a label, and starting with label 0 when labelling the elements of a set, is just as good as starting with label 1. Then you just need ℕ = {0, 1, ...}, and ℤ for the integers, and you will not have much use for ℕ⁺ = {1, 2, ...}, because now sizing something and labelling something is one and the same. So you will now use x_0, x_1, ..., x_{n-1}. So you start counting from 0. I don't know, I just don't like it, but in the long run, maybe it is less confusing, because you unified the concepts of sizing and labelling, and now you can call both of them just counting.

Re: BB(3, 3) is Hard

#119

Post by daynthelife »

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…

The “For instance, the notation `0^\inf 1^3 [0] https://www.sligocki.com/2021/07/17/bb-collatz.html

Re: BB(3, 3) is Hard

#120

Post by l33t7332273 »

dullcrisp wrote: post #69
l33t7332273 wrote: post #56

Earlier quoted context omitted.

Oh, sure. I was just pointing out that the hardness is in determining the busy beaver number and that it didn’t matter if your algorithm halts iff ZFC is consistent or if it’s an algorithm that halts iff ZFC is inconsistent.

No, if you had an algorithm that (you could prove) halts iff ZFC is consistent, then if that algorithm halts, you’ll have a proof that ZFC is consistent, which isn’t possible. Thus, the existence of such an algorithm would be a contradiction that proves the inconsistency of ZFC. The problem with your construction is that it relies on knowing the value of BB(754), which is impossible to know so long as ZFC is consiste…

> The problem with your construction is that it relies on knowing the value of BB(754)

Eh, this doesn’t really matter. That busy beaver number is just an integer, so there is some TM that does exactly as I have described.

Thus, there I have proved that there is a turing machine that halts iff ZFC is consistent.

Post reply on HN