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)...