Halting Equivalent

Shorthand for "eqivalent to the HaltingProblem". In other words, not decideable (in finite time on a TuringMachine or a TuringEquivalent device) for all possible inputs.

Note that many HaltingEquivalent problems are decideable for a subset of their inputs; in many case the subset is a useful one. Also note that being decideable does not necessarily mean tractable; computation of the AckermannFunction is decideable for all values, but you'll need a rather large and fast computer to compute A(4,4)...


EditText of this page (last edited June 3, 2005) or FindPage with title or text search