search

bbchallenge / bbchallenge-deciders

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

Debuggin Shawn's bug #7

Closed tcosmo closed 2 years ago

tcosmo commented 2 years ago

For the discovery of the bug please refer to: https://discuss.bbchallenge.org/t/skelet-10-backtracking/57

I had overlooked the string-style tape management part of https://github.com/bbchallenge/bbchallenge-deciders/pull/5 in my review of that PR. Unfortunately, the tape management was buggued. I corrected the bug by reverting back to my style of tape management with maps, like done for Cyclers and Translated Cyclers.

I added more tests.

sligocki commented 2 years ago

I'm not sure if I'll have a chance to look into this, but while you're at it, would you be willing to add some stats to this for debugging (max depth/steps needed, number of nodes in search tree and max search tree width are the ones I include in my code ... but width only makes sense if you do BFS). If you do, then that would help in comparing the results from our independent codes (for further verification).

tcosmo commented 2 years ago

I added some debugging info yes! We are doing a DFS in this implem

sligocki commented 2 years ago

Cool, comparing DFS in golang written recently by y'all vs. BFS in python written a decade ago by me feels like these should have pretty independent bugs and thus be good for verifying each other :)