Building a BB/TM community and research…

[Terry Ligocki]

First, I LOVE that things are heating up with all the BB related investigations! It’s wonderful to have an active community whatever the size. Shawn and I are fans of open software, research, etc. I think adding Pavel’s work to this would be great - at his discretion, of course. I agree with Shawn and Nick that we can make sure credit is shared in a reasonable way. 

I retire at the end f May and it has been hard to focus on the mundane details of that while the BB work has been rekindled but I know I’ll soon get the chance to investigate more.

Shawn and I would like to finish off the (2,4) work that got us started - it’s completely doable, we just have to finish it and report it. I’m always interested in the non-(x,2) cases because they have a bit of a different flavor and (x,2) insights don’t seem to work as well there. I think there’s things to be discovered.

I also want to create a TM database to store all that has been enumerated and classified so people can easily look up TMs, classes of TMs, and query things about them to get distributions, etc.

Finally, I think we’re in a position to solidify what some people have already done to document all this and add to it in a meaningful way!

Sent by modern magic - TJL

On May 17, 2022, at 8:48 AM, Shawn Ligocki <slig...@gmail.com> wrote:



Pavel, for what it's worth, my dad and I made our code public several years ago and I have been very happy with the result, which has mostly been that now Nick runs it in various ways I had not expected and we motivate each other to think of new ideas. Of course, maybe this is easier for me to say when I have access to a 40-node cluster :) I'm not sure how I would feel if someone used my code to find a new champion, maybe both jealous and proud? Perhaps we should give credit to the code author as well as the person who found a machine in some way? In general, I am very excited about growing and nurturing the Busy Beaver community by providing tools that make it easier for new folks to get involved. But, of course, I also want to win :)

It's very exciting to hear about your process. Before your confirmation email, I was not sure if you were still doing Busy Beaver things (or if your email was still working), but now I find out that you were following along on my journey and even anticipated that I might get a 6x2 record, very sneaky! I get a sense that after a decade of quiet, the competition might become heated again :)

On Tue, May 17, 2022 at 6:03 AM <uni...@fu-solution.com> wrote:

On 2022-05-16 19:30, Nicholas Drozd wrote:
> Pavel, is there any chance you could put your code online? I
> google-translated your old thesis, but that only got me so far :)

it should be possible to download my old code somewhere along the
thesis, but as you experienced with the text - even for me it was easier
to invent it from scratch than to understand myself from a decade ago -
it's really horrible experimental c++. and it's overly complicated and
ineffecient compared to what it can handle in the end => so i started
new version in rust :).

i can opensource my new code, but:

* it will not help you right now - 2 most important parts - computing
nested minima & divisibility conditions are not yet right. i
simplified/optimized that part compared to old code, but it's tricky to
get it right - that was the place i left that code 1.5y ago - i needed
gui to debug it and gui is one of the last things that doesn't have a
success story in rust yet. but I finally hacked one :)

* rado's `busy beaver competition` would lost its `competition` part.
any idea how to frame collaborative effort afterwards?

however, science is about making progress, not winning, and my code is a
good starting point from where to hunt interesting machines - for
example doomsday variation of those machines Shawn is searching for - a
machine that halts, but it's not possible to compute the number. (the
new code has been shaped to make it easier to implement the 'rozbor
pripadov' section from my thesis to make it possible). plus there are
more things i would like to see implemented, but it would probably
exceed my time budget for this "round" - happy to share the load.

and the final quest - it's time to finalize BB(5) and get close to BB(6)
- but there are real monsters that would need yet another proof/tape
representation.

--
You received this message because you are subscribed to the Google Groups "Busy Beaver Discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to busy-beaver-dis...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/busy-beaver-discuss/b57409b6de33bc3a6b2888c4e5349530%40fu-solution.com.

--
You received this message because you are subscribed to the Google Groups "Busy Beaver Discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to busy-beaver-dis...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/busy-beaver-discuss/CADhnJ7Brq_o9umZfeCb%3DBD0ujj4XpqJwOBhzn4sQ%2B%2BQr9OT8_g%40mail.gmail.com.

[uni...@fu-solution.com]

On 2022-05-18 07:01, Terry Ligocki wrote:
> I’m always interested in the non-(x,2) cases because they
> have a bit of a different flavor and (x,2) insights don’t seem to
> work as well there. I think there’s things to be discovered.

hmmm, it it because they have inherent `counter` behaviour? (== what
(x,2) needs to simulate with bigger symbol (00, 01, 10, 11), they
already have by default?)

in my old code, i had separate path for detecting counters, but i intend
to somehow integrate `core counter transitions` into classic to handle
more flavoured behaviour around them (double sided, counter + linear,
switching behaviours). but this is a little bit harder to do with my
dynamic tape compression.

[Terry Ligocki]

That could have something to do with it. Our code(s) don't detect counter behavior directly - Shawn can correct me on this if I'm misremembering.

Also, the (2,n) TMs appear to be more "expressive" than the (n,2) TMs. One aspect of "more expressive" is that it appear that BB(2,n) is much greater than BB(n,2). One reason for this may be that more symbols can utilize the (unbounded) tape but more states "only" expand the transition table/state machine but this is only conjecture at the moment.

In any case, (2,n) TMs fascinate me in the same way, in general, that TMs with small transition tables fascinate most of us - how can something so small run for so long and then halt? The (2,n) TMs are like that but to the extreme - how can only 2 state TMs be so complex?

                                Terry J.

P.S. Also, non (n,2) TMs are also much less explored (at the moment) so sometimes it's fun to play there, :-)...

---

Arrogance

The best leaders inspire by example.
When that's not an option, brute intimidation works pretty well, too.

(Despair, Inc.)

[Nicholas Drozd]

For another thing, there's no method (at least that I'm aware of) for doing meaningful control flow static analysis on (2,n) programs.

If I'm currently in some state, the big questions are: how did I get here and where will I go next? With (n,2) programs, it's possible to get some answers. For example, consider Pavel's new champion. If I'm in state F, I know that I just came from state E, and before that from state D. I also know that next I will end up in state B, either by going there directly or by going to state A first and then (assuming we don't halt) to B.

All that can be figured out just by looking at the program, without running it.

But with just two states, what is there to say? If I'm in state B, I definitely came from state A at some point, and I will almost certainly end up there again. That's about all that can be said without actually running it. Increasing the number of colors does nothing to help.

Expressiveness and analyzability are inversely related, so I take this as evidence that (2,n) is more powerful than (n,2).

[Shawn Ligocki]

FWIW, I do know of one static analysis method that appears to be more effective for multi-symbol machines. In our code we call it Reverse_Engineering_Fitler.py (but this is a terrible name, sorry :( ). It is only a method for deciding if a machine cannot halt (Backwards reasoning). As far as I know, I invented the technique while misunderstanding a description of backtracking. It works this way:

• For each transition to halt in your machine (State s, symbol q) -> Halt  (Where symbol q is not the blank symbol)
• Do all other transitions into state s move in only one direction (say Left)
• Do all other transitions which write symbol q move in the same direction (also Left)
• If both of these are true, then we can never reach this (State s, symbol q) -> Halt transition (because all of the symbols q will be to the right of the TM head).

In general, this is not very useful for the 2-symbol case because the only way it can apply there is if the TM never has any 1s on one half of the tape which severely limits it's expressiveness (I think there's no possible way for such machines to do universal computation for example because they cannot preserve information while traversing across the tape).

However, for the 2-state case, you can actually have reasonably expressive TMs which always enter one of their two states in the same direction (I have not thought hard about it, but would guess that this class of TMs is universal).

From our TNF enumerations, this method was able to prove infinite:

• 20% (88k / 620k) of 4x2 TMs
• 28% (59k / 348k) of 2x4 TMs

And furthermore, of these machines:

• For 4x2: ~0.6% (585 / 88k) were not classifiable by a simple run through other filters (Lin Recur Detection 1k steps & Macro Simulator 10k steps)
• For 2x4: It's more like 5% (3k / 59k)

--

You received this message because you are subscribed to the Google Groups "Busy Beaver Discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to busy-beaver-dis...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/busy-beaver-discuss/CABAiW0qj5kb5bBpk4NPgmsQS2z2SwH5TFsBXCJOH929W_F8a5A%40mail.gmail.com.

[uni...@fu-solution.com]

it would be interesting to change my old simulator to handle more than 2
symbols & look at what "backtracking with proofs" would show for such
machines.

(99% i would not reimplement that monstrosity)

On 2022-05-18 19:59, Shawn Ligocki wrote:
> FWIW, I do know of one static analysis method that appears to be more
> effective for multi-symbol machines. In our code we call it
> Reverse_Engineering_Fitler.py (but this is a terrible name, sorry :(
> ). It is only a method for deciding if a machine cannot halt
> (Backwards reasoning). As far as I know, I invented the technique
> while misunderstanding a description of backtracking. It works this
> way:
>

> * For each transition to halt in your machine (State s, symbol q) ->

> Halt  (Where symbol q is not the blank symbol)
>

> * Do all other transitions into state s move in only one direction
> (say Left)
> * Do all other transitions which write symbol q move in the same
> direction (also Left)
> * If both of these are true, then we can never reach this (State s,

> symbol q) -> Halt transition (because all of the symbols q will be to
> the right of the TM head).
>
> In general, this is not very useful for the 2-symbol case because the
> only way it can apply there is if the TM never has any 1s on one half
> of the tape which severely limits it's expressiveness (I think there's
> no possible way for such machines to do universal computation for
> example because they cannot preserve information while traversing
> across the tape).
>
> However, for the 2-state case, you can actually have reasonably
> expressive TMs which always enter one of their two states in the same
> direction (I have not thought hard about it, but would guess that this
> class of TMs is universal).
>
> From our TNF enumerations, this method was able to prove infinite:
>

> * 20% (88k / 620k) of 4x2 TMs
> * 28% (59k / 348k) of 2x4 TMs

>
> And furthermore, of these machines:
>

> * For 4x2: ~0.6% (585 / 88k) were NOT classifiable by a simple run

> through other filters (Lin Recur Detection 1k steps & Macro Simulator
> 10k steps)

> * For 2x4: It's more like 5% (3k / 59k)

>> [1].

>
> --
> You received this message because you are subscribed to the Google
> Groups "Busy Beaver Discuss" group.
> To unsubscribe from this group and stop receiving emails from it,
> send an email to busy-beaver-dis...@googlegroups.com.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/busy-beaver-discuss/CADhnJ7AZB44TCWZ26PXef1%3DaZ%3DbuophA7OE2QN7DZTVuwTZmag%40mail.gmail.com
> [2].
>
>
> Links:
> ------
> [1]
> https://groups.google.com/d/msgid/busy-beaver-discuss/CABAiW0qj5kb5bBpk4NPgmsQS2z2SwH5TFsBXCJOH929W_F8a5A%40mail.gmail.com?utm_medium=email&amp;utm_source=footer
> [2]
> https://groups.google.com/d/msgid/busy-beaver-discuss/CADhnJ7AZB44TCWZ26PXef1%3DaZ%3DbuophA7OE2QN7DZTVuwTZmag%40mail.gmail.com?utm_medium=email&utm_source=footer

[Terry Ligocki]

Yeah, it's hard to resurrect big, old codes written under duress, :-)! In any case, lots of exploring to do...

                                Terry J.

---

When you sleep, where do your fingers go?

       - When You Sleep (Cake)

[Nicholas Drozd]

Speaking of backward reasoning, here's something I forgot to mention in the other thread. I also have a thing that checks to see if a machine can reach its halt state. It tries to reconstruct a path to the halt instruction. If such a path can be constructed, then maybe the machine halts. If every such path can be shown to be impossible, then the machine definitely doesn't halt. This approach works just as well for blank tape and spinning out too, which is pretty cool.

Anyway, the checker seemed to be working pretty well. Some false negatives, as expected, but no false positives (that is, it never says that something doesn't halt when in fact it actually does).

Shawn's three-day champion turned out to be a false positive! The checker says that it won't halt, but of course it does. One more reason why I wouldn't have found that one. On the other hand, Pavel's champ is handled as expected, with a verdict of "might halt".

So Shawn's machine is graph-complex and foils my backwards reasoner, while Pavel's machine is graph-simple and doesn't foil the reasoner. Pavel's machine is "better-behaved". All this exciting new evidence once again contradicts the Spaghetti Code Conjecture!

(This comes with all the usual disclaimers: this is not a proof of anything, the evidence we have is biased, etc.)

[Tristan Stérin]

Hello, 

You might be interested in our attempt to create such a database and community with https://bbchallenge.org/

For instance, as part of this project we have published open-source, proven correct, code for backward reasoning: 

• https://github.com/bbchallenge/bbchallenge-deciders/tree/main/decider-backward-reasoning
• https://discuss.bbchallenge.org/t/decider-backward-reasoning/35
  
• Proof: https://github.com/bbchallenge/bbchallenge-proofs/blob/main/deciders/correctness-deciders.pdf

I introduced https://bbchallenge.org/ in more detail here:

https://groups.google.com/g/busy-beaver-discuss/c/dx6cwJU8iFU

Thank you very much,