Decider: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
m (update far link) |
||
| (7 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
[[Category:Deciders]] | |||
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]]. | ||
| Line 6: | Line 7: | ||
* [[Translated Cycler]] | * [[Translated Cycler]] | ||
* [[ | * [[Backward Reasoning]] | ||
* [[Closed Position Set]] | * [[Closed Position Set]] (CPS) | ||
* [[Closed Tape Language]] | * [[Closed Tape Language]] (CTL) | ||
* [[Finite Automata Reduction]] | * [[Finite Automata Reduction]] (FAR) | ||
* [[Inductive Proof]] | * [[Inductive Proof System]] | ||
* [[Bouncer]] | * [[Bouncer]] | ||
* [[Halting Segment]] | * [[Halting Segment]] | ||
Latest revision as of 08:35, 25 August 2025
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, Backwards 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