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

51–60 of 146 posts

Re: BB(3, 3) is Hard

#51

Post by jdthedisciple »

joshxyz wrote: post #49

This is too much nerd for me. Can anyone tell me what is the required pre-requisite of knowledge to understand things like this? Like will knowing basic calculus be enough? What specific topics or subjects will give me good fundamentals on these things? Thank you.

This fits squarely into theoretical computer science.

Going through any introductory TCS textbook will help you understand most of this stuff.

CS students do this in their first or second year of their studies, and yes it's tough (at my uni this was among the most feared exams).

Re: BB(3, 3) is Hard

#52

Post by jcagalawan »

joshxyz wrote: post #49

This is too much nerd for me. Can anyone tell me what is the required pre-requisite of knowledge to understand things like this? Like will knowing basic calculus be enough? What specific topics or subjects will give me good fundamentals on these things? Thank you.

Theory of Computation, Number Theory, and Probability are good starts.

Re: BB(3, 3) is Hard

#53

Post by markuswt »

joshxyz wrote: post #49

This is too much nerd for me. Can anyone tell me what is the required pre-requisite of knowledge to understand things like this? Like will knowing basic calculus be enough? What specific topics or subjects will give me good fundamentals on these things? Thank you.

Calculus has little to do with this kind of problem. You should study theoretical computer science, in particular computability theory, to understand the article. Many CS undergraduate programs will have courses with public resources you can follow.

Re: BB(3, 3) is Hard

#54

Post by kybernetikos »

joshxyz wrote: post #49

This is too much nerd for me. Can anyone tell me what is the required pre-requisite of knowledge to understand things like this? Like will knowing basic calculus be enough? What specific topics or subjects will give me good fundamentals on these things? Thank you.

This [1] is a really accessible introduction to busy beaver numbers.

[1] https://www.scottaaronson.com/writings/bignumbers.html

Re: BB(3, 3) is Hard

#55

Post by unhammer »

joshxyz wrote: post #49

This is too much nerd for me. Can anyone tell me what is the required pre-requisite of knowledge to understand things like this? Like will knowing basic calculus be enough? What specific topics or subjects will give me good fundamentals on these things? Thank you.

More like discrete math and automata theory https://en.m.wikipedia.org/wiki/Automata_theory or theory of computation. Hopcroft & Ullmann's intro book is nice. But there's so much related stuff here, it's just a starting point.

Re: BB(3, 3) is Hard

#56

Post by l33t7332273 »

meithecatte wrote: post #46
l33t7332273 wrote: post #42

Earlier quoted context omitted.

I don’t think that’s it. I think it’s easy to take such a machine and make a new one that halts iff ZFC is consistent. Call the machine that halts iff ZFC is inconsistent A. Now consider the machine which computes the following algorithm: Run A BB(754) times. If A halts, then run forever, else halt. If A halts then our machine runs forever, and vice versa. Thus, our machine halts when ZFC is consistent and our machin…

How do you make the new machine compute BB(754)? BB is the canonical example of an uncomputable function, precisely because you can decide the halting problem if you can compute it (or any upper bound). Granted, BB may be computed for specific arguments, as OP mentions for 1–4, but the existence of the ZFC-dependent machine is, at least to me, a very good argument that the boundary of what's possible is much lower.

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.

Re: BB(3, 3) is Hard

#57

Post by dandanua »

modeless wrote: post #44
dandanua wrote: post #33

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.

Right, we don't know the value BB(748), and moreover, "knowing" it is not enough, we would still need a proof that a certain number matches BB(748). And such a proof is not easier than a direct proof of ZFC consistency, I presume.

BTW, a value can't be uncomputable, only a function can.

Re: BB(3, 3) is Hard

#58

Post by kuboble »

tybug wrote: post #27
Filligree wrote: post #24

Earlier quoted context omitted.

So… what if BB(748) is uncomputable? Or rather, didn’t you just prove that it is?

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).

Re: BB(3, 3) is Hard

#59

Post by acmiyaguchi »

jdthedisciple wrote: post #51
joshxyz wrote: post #49

This is too much nerd for me. Can anyone tell me what is the required pre-requisite of knowledge to understand things like this? Like will knowing basic calculus be enough? What specific topics or subjects will give me good fundamentals on these things? Thank you.

This fits squarely into theoretical computer science. Going through any introductory TCS textbook will help you understand most of this stuff. CS students do this in their first or second year of their studies, and yes it's tough (at my uni this was among the most feared exams).

A first or second year (undergrad) student doing theoretical science to this level is astounding to me. It was an upper-division course for me, albeit a prerequisite for things like compilers and cryptography, so I'm sure it could be put earlier in the journey.

Sipser's "Introduction to the Theory of Computation" was the book I had to read, and it certainly makes this post more accessible.

Re: BB(3, 3) is Hard

#60

Post by thethimble »

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…

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?
Post reply on HN