Backward Reasoning: Difference between revisions
Jump to navigation
Jump to search
(Used Template:Stub) |
(Added some information) |
||
| Line 1: | Line 1: | ||
{{Stub}} | {{Stub}} | ||
Backward Reasoning is a [[decider]] which simulates [[Turing machines]] backwards from all possible halting configurations until a contradiction (or an impossible step) is reached. If a contradiction is reached from all possible halting configurations, the TM is shown to be non-halting. The amount of backward steps which are simulated can also be called the depth with which Backward Reasoning was applied. | |||
==See also== | |||
See [https://github.com/bbchallenge/bbchallenge-proofs/blob/build-latex-pdf/deciders/correctness-deciders.pdf Section 4] of bbchallenge's deciders write-up. | See [https://github.com/bbchallenge/bbchallenge-proofs/blob/build-latex-pdf/deciders/correctness-deciders.pdf Section 4] of bbchallenge's deciders write-up. | ||
[[Category:Deciders]] | [[Category:Deciders]] | ||
Revision as of 22:34, 27 August 2025
Backward Reasoning is a decider which simulates Turing machines backwards from all possible halting configurations until a contradiction (or an impossible step) is reached. If a contradiction is reached from all possible halting configurations, the TM is shown to be non-halting. The amount of backward steps which are simulated can also be called the depth with which Backward Reasoning was applied.
See also
See Section 4 of bbchallenge's deciders write-up.