Decider: Difference between revisions
Jump to navigation
Jump to search
→List of Deciders: Added cyclers |
m Fixed misspelled link |
||
| 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. | ||
== List of Deciders == | == List of Deciders == | ||
Latest revision as of 15:48, 8 October 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, 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