Is there a difference in usage between halting and terminating?

Question

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

Answer 1

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.

Answer 2

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 t → v
2. if false then t else v → v

and 1 is neither true nor false.