Decider: Difference between revisions
Jump to navigation
Jump to search
→List of Deciders: some more information on variants |
other computational models |
||
| Line 3: | Line 3: | ||
There are a wide variety of methods used to construct deciders. Some broad categories are: [[Accelerated Simulator]]s, [[Backward Reasoning]] and [[Closed Set]] methods. | There are a wide variety of methods used to construct deciders. Some broad categories are: [[Accelerated Simulator]]s, [[Backward Reasoning]] and [[Closed Set]] methods. | ||
The definition may be extended to other Busy Beaver function with different computational models. | |||
== List of Deciders == | == List of Deciders == | ||
Latest revision as of 21:31, 15 August 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.
The definition may be extended to other Busy Beaver function with different computational models.
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)