Decider: Difference between revisions
Jump to navigation
Jump to search
→List of Deciders: added Repeated Word List |
→List of Deciders: some more information on variants |
||
| (One intermediate revision by the same user not shown) | |||
| Line 15: | Line 15: | ||
* [[Halting Segment]] | * [[Halting Segment]] | ||
* [[Cycler]] | * [[Cycler]] | ||
* [[Repeated Word List]] (RepWL) | * [[Repeated Word List]] (RepWL or RepWL_ES) | ||
* [[RWLAcc]], an accelerated simulator similar to Quick_Sim | |||
* [[NGram CPS|n-Gram Closed Position Set]] (n-Gram CPS) with the possible augmentations of Fixed-length history and Least Recent Usage history (LRU) | |||
== See also == | == See also == | ||
https://bbchallenge.org/method#deciders | https://bbchallenge.org/method#deciders | ||
Latest revision as of 14:38, 2 April 2026
A Decider (or a Filter) is a program which attempts to decide whether or not a given Turing machine (TM) will halt. Since the Halting Problem is uncomputable, no decider can decide all TMs, instead deciders categorize each TM into one of three categories: Halting, Proven Infinite, or Holdout.
There are a wide variety of methods used to construct deciders. Some broad categories are: Accelerated Simulators, Backward Reasoning and Closed Set methods.
List of Deciders
- Translated Cycler
- Backward Reasoning
- Closed Position Set (CPS)
- Closed Tape Language (CTL)
- Finite Automata Reduction (FAR)
- Inductive Proof System
- Bouncer
- Halting Segment
- Cycler
- Repeated Word List (RepWL or RepWL_ES)
- RWLAcc, an accelerated simulator similar to Quick_Sim
- n-Gram Closed Position Set (n-Gram CPS) with the possible augmentations of Fixed-length history and Least Recent Usage history (LRU)