Decider: Difference between revisions
Jump to navigation
Jump to search
m update far link |
other computational models |
||
| (5 intermediate revisions by one other user not shown) | |||
| Line 2: | Line 2: | ||
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]]. | 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 Simulator]]s, [[ | 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 == | ||
| Line 14: | Line 16: | ||
* [[Bouncer]] | * [[Bouncer]] | ||
* [[Halting Segment]] | * [[Halting Segment]] | ||
* [[Cycler]] | |||
* [[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 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)