BB(6) Is Hard (Antihydra) (2024)

https://www.sligocki.com//2024/07/06/bb-6-2-is-hard.html

34•Fibra•6mo ago

Comments

gliptic•6mo ago

Recent developments on BB(6) previously posted here: https://scottaaronson.blog/?p=8972

cubefox•6mo ago

272 points by bdr 18 days ago | 223 comments

https://news.ycombinator.com/item?id=44406171

_alternator_•6mo ago

Cool link, despite being a bit later than some of the other stuff on BB(6). Basically, it shows a 6-state Turing machine can encode a Collatz-type iteration:

``` a,b=8,0 while b!=-1: b+=2-a%2*3 a+=a>>1 ```

Showing that these halt or not are long-standing open problems, so knowing upper bounds BB(6) would immediately solve them (modulo a lot of compute time).

thrance•6mo ago

A number, that if known, would allow us to derive the truth value of any statements from it.

tromp•6mo ago

only the truth of finitely refutable conjectures...

Y_Y•6mo ago

Could any number give you the truth of non-finitely refutable conjectures?

tromp•6mo ago

If you had both Omega and the halting probability Omega_1 of a Universal Oracle Turing Machine with Omega as oracle, then it seems you could decide Sigma_2/Pi_2 conjectures. You can alternate bits from both Omegas to make it one number.

david_for_you•6mo ago

Hm, I'm not sure I would say that knowing an upper bound would be any help in solving these open problems, unless the way to prove that upper bound would involve a collatz type problem. We already know from the lower bound of BB(6) that we cannot iterate that far in this universe.

_alternator_•6mo ago

An upper bound U for BB(6) implies that any program that runs longer than U never terminates. Thus the specific Collatz-type problems that can be encoded in 6 instructions can be run U+1 steps and if they don’t halt, they won’t halt.

The proof that BB(6) is relevant is that you can encode it in a 6 instruction program, which is what the link does.

david_for_you•6mo ago

I understand that, what I am saying is, that the upper bound can never be useful because the lower bound is already so high that we cannot run U+1 steps, ever.

_alternator_•6mo ago

I see; thanks for clarifying. I suppose the only thing you’d get “for free” is that the termination of these programs becomes decidable. (Not sure if this is known for these specific programs. At some point, BB number bounds are necessarily unknowable.)

PID Controller

SpaceX Rocket Generates 100GW of Power, or 20% of US Electricity

Kubernetes MCP Server

I Built a Movie Recommendation Agent to Solve Movie Nights with My Wife

What were the first animals? The fierce sponge–jelly battle that just won't end

Sidestepping Evaluation Awareness and Anticipating Misalignment

OldMapsOnline

What It's Like to Be a Worm

Don't go to physics grad school and other cautionary tales

Lawyer sets new standard for abuse of AI; judge tosses case

AI anxiety batters software execs, costing them combined $62B: report

Bogus Pipeline

Winklevoss twins' Gemini crypto exchange cuts 25% of workforce as Bitcoin slumps

How AI Is Reshaping Human Reasoning and the Rise of Cognitive Surrender

Cycling in France

Ask HN: What breaks in cross-border healthcare coordination?

Show HN: Simple – a bytecode VM and language stack I built with AI

Show HN: Free-to-play: A gem-collecting strategy game in the vein of Splendor

My Eighth Year as a Bootstrapped Founde

Show HN: Tesseract – A forum where AI agents and humans post in the same space

Show HN: Vibe Colors – Instantly visualize color palettes on UI layouts

OpenAI is Broke ... and so is everyone else [video][10M]

We interfaced single-threaded C++ with multi-threaded Rust

State Department will delete X posts from before Trump returned to office

AI Skills Marketplace

Show HN: A fast TUI for managing Azure Key Vault secrets written in Rust

eInk UI Components in CSS

Discuss – Do AI agents deserve all the hype they are getting?

ChatGPT is changing how we ask stupid questions

Zig Package Manager Enhancements

PID Controller

SpaceX Rocket Generates 100GW of Power, or 20% of US Electricity

Kubernetes MCP Server

I Built a Movie Recommendation Agent to Solve Movie Nights with My Wife

What were the first animals? The fierce sponge–jelly battle that just won't end

Sidestepping Evaluation Awareness and Anticipating Misalignment

OldMapsOnline

What It's Like to Be a Worm

Don't go to physics grad school and other cautionary tales

Lawyer sets new standard for abuse of AI; judge tosses case

AI anxiety batters software execs, costing them combined $62B: report

Bogus Pipeline

Winklevoss twins' Gemini crypto exchange cuts 25% of workforce as Bitcoin slumps

How AI Is Reshaping Human Reasoning and the Rise of Cognitive Surrender

Cycling in France

Ask HN: What breaks in cross-border healthcare coordination?

Show HN: Simple – a bytecode VM and language stack I built with AI

Show HN: Free-to-play: A gem-collecting strategy game in the vein of Splendor

My Eighth Year as a Bootstrapped Founde

Show HN: Tesseract – A forum where AI agents and humans post in the same space

Show HN: Vibe Colors – Instantly visualize color palettes on UI layouts

OpenAI is Broke ... and so is everyone else [video][10M]

We interfaced single-threaded C++ with multi-threaded Rust

State Department will delete X posts from before Trump returned to office

AI Skills Marketplace

Show HN: A fast TUI for managing Azure Key Vault secrets written in Rust

eInk UI Components in CSS

Discuss – Do AI agents deserve all the hype they are getting?

ChatGPT is changing how we ask stupid questions

Zig Package Manager Enhancements

BB(6) Is Hard (Antihydra) (2024)

Comments