search

bbchallenge / bbchallenge-deciders

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

Debug backward reasoning bug found by lijil #8

Closed tcosmo closed 2 years ago

tcosmo commented 2 years ago

There was a bug on the depth stack due to misuse of go's operator := with slices.

To correct this bug, I merged the depth stack with the configuration stack to simplify the code.

Note that now running to depth 300 is not feasible anymore (too long). @sligocki and @lijil reported max depth of 29, hence we'll run with 50.

sligocki commented 2 years ago

Fwiw, I'm not sure 29 is the max. Just that the machine @lijil listed only needed depth 29. But most are found with depth like 2, so this should be a good first pass :)

sligocki commented 2 years ago

It will be interesting to see if this rerun (with the bug fix) leads to any different results. Can you compare the results after bug fix to before? From what you were saying it seems like the results should be the same (if the only bug was in depth calculation) or maybe that the new run will be more effective? I guess the new run could be less effective due to the max depth decrease.

tcosmo commented 2 years ago

Yes it is exactly what happened! Same exact set of machines, less efficient execution. Longest backtracking tree is of depth 28 for machine 11663412.