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

France's homegrown open source online office suite

British drivers over 70 to face eye tests every three years

Start all of your commands with a comma (2009)

Leisure Suit Larry's Al Lowe on model trains, funny deaths and Disney

Hoot: Scheme on WebAssembly

Stories from 25 Years of Software Development

OpenCiv3: Open-source, cross-platform reimagining of Civilization III

Reinforcement Learning from Human Feedback

First Proof

The Waymo World Model

Coding agents have replaced every framework I used

Vocal Guide – belt sing without killing yourself

Software Factories and the Agentic Moment

A Fresh Look at IBM 3270 Information Display System

StrongDM's AI team build serious software without even looking at the code

Unseen Footage of Atari Battlezone Arcade Cabinet Production

72M Points of Interest

Making geo joins faster with H3 indexes

Show HN: Look Ma, No Linux: Shell, App Installer, Vi, Cc on ESP32-S3 / BreezyBox

Ga68, a GNU Algol 68 Compiler

Monty: A minimal, secure Python interpreter written in Rust for use by AI

Hackers (1995) Animated Experience

Sheldon Brown's Bicycle Technical Info

Show HN: I spent 4 years building a UI design tool with only the features I use

Show HN: Kappal – CLI to Run Docker Compose YML on Kubernetes for Local Dev

What Is Ruliology?

Show HN: If you lose your memory, how to regain access to your computer?

An Update on Heroku

Microsoft open-sources LiteBox, a security-focused library OS

Female Asian Elephant Calf Born at the Smithsonian National Zoo

France's homegrown open source online office suite

British drivers over 70 to face eye tests every three years

Start all of your commands with a comma (2009)

Leisure Suit Larry's Al Lowe on model trains, funny deaths and Disney

Hoot: Scheme on WebAssembly

Stories from 25 Years of Software Development

OpenCiv3: Open-source, cross-platform reimagining of Civilization III

Reinforcement Learning from Human Feedback

First Proof

The Waymo World Model

Coding agents have replaced every framework I used

Vocal Guide – belt sing without killing yourself

Software Factories and the Agentic Moment

A Fresh Look at IBM 3270 Information Display System

StrongDM's AI team build serious software without even looking at the code

Unseen Footage of Atari Battlezone Arcade Cabinet Production

72M Points of Interest

Making geo joins faster with H3 indexes

Show HN: Look Ma, No Linux: Shell, App Installer, Vi, Cc on ESP32-S3 / BreezyBox

Ga68, a GNU Algol 68 Compiler

Monty: A minimal, secure Python interpreter written in Rust for use by AI

Hackers (1995) Animated Experience

Sheldon Brown's Bicycle Technical Info

Show HN: I spent 4 years building a UI design tool with only the features I use

Show HN: Kappal – CLI to Run Docker Compose YML on Kubernetes for Local Dev

What Is Ruliology?

Show HN: If you lose your memory, how to regain access to your computer?

An Update on Heroku

Microsoft open-sources LiteBox, a security-focused library OS

Female Asian Elephant Calf Born at the Smithsonian National Zoo

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

Comments