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 difference)
|
Revision as of 14:48, 14 June 2024
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.