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

Show HN: MCP to get latest dependency package and tool versions

The better you get at something, the harder it becomes to do

Show HN: WP Float – Archive WordPress blogs to free static hosting

Show HN: I Hacked My Family's Meal Planning with an App

Sony BMG copy protection rootkit scandal

The Future of Systems

NASA now allowing astronauts to bring their smartphones on space missions

Claude Code Is the Inflection Point

Show HN: MicroClaw – Agentic AI Assistant for Telegram, Built in Rust

Show HN: Omni-BLAS – 4x faster matrix multiplication via Monte Carlo sampling

The AI-Ready Software Developer: Conclusion – Same Game, Different Dice

AI Agent Automates Google Stock Analysis from Financial Reports

Voxtral Realtime 4B Pure C Implementation

I Was Trapped in Chinese Mafia Crypto Slavery [video]

U.S. CBP Reported Employee Arrests (FY2020 – FYTD)

Show HN: I built a free UCP checker – see if AI agents can find your store

Show HN: SVGV – A Real-Time Vector Video Format for Budget Hardware

Study of 150 developers shows AI generated code no harder to maintain long term

Spotify now requires premium accounts for developer mode API access

When Albert Einstein Moved to Princeton

Agents.md as a Dark Signal

System time, clocks, and their syncing in macOS

McCLIM and 7GUIs – Part 1: The Counter

So whats the next word, then? Almost-no-math intro to transformer models

Ed Zitron: The Hater's Guide to Microsoft

UK infants ill after drinking contaminated baby formula of Nestle and Danone

Show HN: Android-based audio player for seniors – Homer Audio Player

Starter Template for Ory Kratos

LLMs are powerful, but enterprises are deterministic by nature

Make your iPad 3 a touchscreen for your computer

Show HN: MCP to get latest dependency package and tool versions

The better you get at something, the harder it becomes to do

Show HN: WP Float – Archive WordPress blogs to free static hosting

Show HN: I Hacked My Family's Meal Planning with an App

Sony BMG copy protection rootkit scandal

The Future of Systems

NASA now allowing astronauts to bring their smartphones on space missions

Claude Code Is the Inflection Point

Show HN: MicroClaw – Agentic AI Assistant for Telegram, Built in Rust

Show HN: Omni-BLAS – 4x faster matrix multiplication via Monte Carlo sampling

The AI-Ready Software Developer: Conclusion – Same Game, Different Dice

AI Agent Automates Google Stock Analysis from Financial Reports

Voxtral Realtime 4B Pure C Implementation

I Was Trapped in Chinese Mafia Crypto Slavery [video]

U.S. CBP Reported Employee Arrests (FY2020 – FYTD)

Show HN: I built a free UCP checker – see if AI agents can find your store

Show HN: SVGV – A Real-Time Vector Video Format for Budget Hardware

Study of 150 developers shows AI generated code no harder to maintain long term

Spotify now requires premium accounts for developer mode API access

When Albert Einstein Moved to Princeton

Agents.md as a Dark Signal

System time, clocks, and their syncing in macOS

McCLIM and 7GUIs – Part 1: The Counter

So whats the next word, then? Almost-no-math intro to transformer models

Ed Zitron: The Hater's Guide to Microsoft

UK infants ill after drinking contaminated baby formula of Nestle and Danone

Show HN: Android-based audio player for seniors – Homer Audio Player

Starter Template for Ory Kratos

LLMs are powerful, but enterprises are deterministic by nature

Make your iPad 3 a touchscreen for your computer

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

Comments