0

The title says it all: Are halting and terminating synonyms in the context of computability theory?

6

Well, it's not called the Terminating Problem; it's called the "Halting Problem."

Given that:

while(true) { }

does not halt, but you could "terminate" it by kicking the power cord out of the wall (or clicking "End Task" in Task Manager), I would say, no, they are not synonyms.

  • and how exactly do you predict that someone will pull the power cord out of the socket? ;) – jk. Mar 27 '12 at 18:52
4

http://en.wikipedia.org/wiki/Divergence_(computer_science)

In computer science, a computation is said to diverge if it does not terminate or terminates in an (unobservable) exceptional state. Otherwise it is said to converge.

More specifically relevant to halting,

In the lambda calculus an expression is divergent if it has no normal form.

So the difference between halting -- process does not continue indefinitely -- and terminating is that terminating implies returning a normal result. Not finishing abruptly (with an error or exceptional condition) or wedging itself in a state where no reduction rule applies.

This problem can be illustrated in the λ-calculus extended with booleans and numbers used by Benjamin Pierce:

(λx.if x then x else x)(1)

which will not reduce because it gets stuck at

(if 1 then 1 else 1)

which does not match any reduction rule since the only rules that apply to if are

  1. if true then v else tv
  2. if false then t else vv

and 1 is neither true nor false.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.