Decider: Difference between revisions
Jump to navigation
Jump to search
(Created page with "A '''Decider''' 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...") |
No edit summary |
||
| Line 1: | Line 1: | ||
A '''Decider''' 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, [[Backwards Reasoning]] and [[Closed Set]] methods. | There are a wide variety of methods used to construct deciders. Some broad categories are: [[Accelerated Simulator]]s, [[Backwards Reasoning]] and [[Closed Set]] methods. | ||
| Line 13: | Line 13: | ||
* [[Bouncer]] | * [[Bouncer]] | ||
* [[Halting Segment]] | * [[Halting Segment]] | ||
== See also == | |||
https://bbchallenge.org/method#deciders | |||
Revision as of 14:50, 14 June 2024
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
- Bouncer
- Halting Segment