3n+1 Ep68: What do Busy Beavers compute?

Подписаться 1,1 тыс.

50% 1

Question: Which computer program of size n runs the longest before stopping? (Programs that run forever are disqualified.) Such a program is called a Busy Beaver of size n. Researchers have been able to locate small-sized Busy Beavers and, surprisingly, they turn out to compute 3n+1-like sequences. Are 3n+1 rules a good way to burn Turing Machine cycles? #collatz
References: "The Busy Beaver Frontier" (Scott Aaronson, 2020) and "The Busy Beaver Competition: a historical survey" (Pascal Michel, 2022).

Опубликовано:

11 сен 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 7

@mathkook 2 месяца назад

Update (July 3, 2024): BB(5) = 47,176,870! See bbchallenge dot org for how they did it!

@mathkook 4 месяца назад

Also: check out the Busy Beaver Challenge at bbchallenge dot org! When this video was posted (2024-05-09), only 2,833 five-state programs (out of ~88m) remained as possible challengers to the current BB(5) champion. It's amazingly hard to tell whether certain tiny programs will run forever, or eventually stop. We're used to this idea by now, though... n = 7; repeat "if odd(n), n = 5n+1; else n = n/2" until n==1. Does it run forever?

@sligocki 4 месяца назад

In the Busy Beaver community we've seen that a lot of the hardest TMs to decide are simulating Collatz-like problems! Unfortunately RU-vid keeps blocking my blog links about this :/ You might find them by searching "BB(3, 3) is Hard (Bigfoot)" and "BB(2, 5) is Hard (Hydra)"

@mathkook 4 месяца назад

Amazing. It's doubly amazing that you're not even discussing the behavior of a specific Collatz-like rule on all inputs (eg, Collatz conjecture), much less the behavior of classes of Collatz-like rules on all inputs (eg, Matthews-Watts conjecture) ... but rather the behavior of a single rule on a single input... like how Bigfoot behaves on input 0, or how the Conway map behaves on input 8, or how the 5n+1 rule behaves on input 7. "Simplest open problems in mathematics", I like that. I guess it's fair to claim that a decent amount of work has (essentially) gone into trying to show that input 7 fails to reach 1 under the 5n+1 rule. There's a straightforward 27-state, 2-symbol TM that puts 7 (in unary) on a blank tape and executes the 5n+1 rule, halting iff 1 is reached ... I'm sure a good TM programmer could make (has made?) a smaller one! It's a little strange to me how nature reserves its precious small machines for bizarre Collatz-like rules, instead of 3n+1 and 5n+1 :)

@PeterJnicol 2 месяца назад

This was great, really concise but thorough aa well as original and entertaining.

@sattawatsuntisurat6237 4 месяца назад

Has this conjecture been solved yet ? There are many people who claim they can do it on RU-vid but I don't hear about the news or progress about it from mathematical society.