Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer
    
and how exactly do you predict that someone will pull the power cord out of the socket? ;) –  jk. Mar 27 '12 at 18:52
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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