search

bbchallenge / bbchallenge-deciders

Here we give programs that check if Turing machines halt or not.
10 stars 3 forks source link

Bikeshedding #3

Open milomg opened 2 years ago

milomg commented 2 years ago

I've been reading through https://skelet.ludost.net/bb/index.html and https://github.com/danbriggs/Turing/blob/master/doc/sweepmachines.md to try to understand current algorithms for detecting infinite machines. Something that would've been really helpful for me is a list of equivalent names for the same algorithm.

For example, Skelet's subdimension test is just https://github.com/bbchallenge/bbchallenge-seed/blob/main/lib_bbchallenge/simulate.go#L136-L144, and I believe his circle in place test is the same as the cyclers argument here (although I'm not particularly confident about that). And translated_cyclers seem similar to the shift recurrences written up here https://github.com/danbriggs/Turing/blob/master/src/machine/AllMachines.java#L752. If these assumptions are correct, would it make sense to add them to the README of this project?

tcosmo commented 2 years ago

That's a really good idea, however, it requires to be done very carefully as I expect differences to occur as soon as the decider is not "simple" (i.e. as soon as you are not dealing with cyclers).