Decider
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
- Backwards Reasoning
- Closed Position Set
- Closed Tape Language
- Finite Automata Reduction
- Inductive Proof System
- Bouncer
- Halting Segment