sligocki

7 ms·

1.
by sligocki 11mo ago
I see, so you are using a different model for computation that does not use rational numbers, but instead pairs of integers. From a computational point of view, that makes a lot of sense, disallowing catalysts is quite annoying, but I would
2.
by sligocki 11mo ago
Not sure if this is a joke, but actually that is guaranteed to be true. It is proven that for all n: BB(n+1) >= BB(n) + 3. But it is not proven that BB(n+1) >= BB(n) + 4, haha.
3.
by sligocki 11mo ago
And 297/275 to 27/25?
4.
by sligocki 11mo ago
50/18 reduces to 25/9 right?
5.
by sligocki 2y ago
Can you clarify what you mean by BBλ being "provably optimal"? IIUC BB functions for any Turing-complete computation model should be equivalent up to a constant. Maybe something like: there exists N, c: forall n >= N: BBλ(n) &l
6.
by sligocki 2y ago
Yes, it seems that BB(3, 4) >>> BB(5, 2) (BB(5) = BB(5, 2)). This is not too surprising since BB(3, 4) has 12 transitions in it's table (3*4), while BB(5, 2) only has 10. But it seems that also BB(3, 4) >> BB(6, 2) (whi
7.
by sligocki 2y ago
Counting the number of distinct TMs is not a simple task. The way you count it is the most broad (the count of all tables of values where each cell can have any (symbol, direction, state) combination). But this is a significant overcount of
8.
by sligocki 3y ago
You are right that every TM can be converted into a Collatz-like problem using Conway's Fractran compilation. So technically the statement "Solving the BB(n, k) problem is at least as hard as solving a Collatz-like problem."
9.
by sligocki 3y ago
The Busy Beaver problem sits somewhere on the range from "intellectual curiosity" to "lens that allows us to view the edges of uncomputability". I would guess that the majority of people doing work here are hobbyists (in
10.
by sligocki 3y ago
His survey 3 years ago has kicked off quite a flurry of Busy Beaver activity of which my entire blog and https://bbchallenge.org/ are a couple examples.
11.
by sligocki 3y ago
Thank you! I'm so glad to hear!
12.
by sligocki 3y ago
Yeah, I've oversimplified a bit with this title. The more accurate statement is in the first paragraph of the article: "Solving the BB(3, 3) problem is at least as hard as solving this Collatz-like problem." I also agree some
13.
by sligocki 3y ago
The issue is the "run the turing machine for BB(748) steps" part. We don't know what BB(748) is. If the god of busy beavers came to us and told us that value, then we could (in theory) run the TM that long and just like you s
14.
by sligocki 4y ago
I'm the author. That's a great summary of the background, thanks! As you say, this post is extremely in the weeds analyzing a single Turing Machine's behavior. I wrote this post mainly aimed at people in the bbchallenge.org p
15.
by sligocki 4y ago
Yes, that's correct. https://www.sligocki.com/2021/07/17/bb-collatz.html has a bit of background that's probably relevent here ... but this content is quite niche, heh :)
16.
by sligocki 4y ago
Thanks! I just figured out how to get MathJax working with github pages and used it to its full extent!
17.
by sligocki 4y ago
It's a good question. Yes and no. If the "God of Busy Beaver" told us a value of BB(n) (for large enough n) then that would reduce some math problems to "simply" running a TM for that many steps and seeing if it hal
18.
by sligocki 4y ago
Hello, I'm the author. Ask me anything :) Thanks fn-mote for providing some context. In fact, I think you could appreciate most of this article without even knowing anything about Turing Machines. I spend almost the entire article just