search

bbchallenge / bbchallenge-deciders

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

Backward reasoning #5

Closed tcosmo closed 2 years ago

tcosmo commented 2 years ago

@modderme123 found a bug in the initial implementation of backward reasoning

tcosmo commented 2 years ago

@modderme123 thank you for your work!

Main points:

  1. I agree that your implementation of backward transitions is the correct one, thank you very much!
  2. The seenStates map was useless because we are sure we will never loop configurations as otherwise we would not reach a halting state but keeping looping for ever.
  3. The transitionTreeDepthLimit was meant to track the depth of the stack and not the number of branches. I implemented this semantic thanks to an extra stack that maintain the depth of each configuration.