Source code online books for professionals by professionals

a NeVereNDING StOrY
there’s more to this story. there’s actually so much more to this story, you wouldn’t believe it. Complexity theory 
is a field of its own, with tons of results, not to mention complexity classes. (For a glimpse of the diversity of 
classes that are being studied, you could visit the Complexity Zoo, 
https://complexityzoo.uwaterloo.ca
.)
one of the formative examples of the field is a problem that is much harder than the np-complete ones: alan 
turing’s halting problem (mentioned in Chapter 4). It simply asks you to determine whether a given algorithm 
will terminate with a given input. to see why this is actually impossible, imagine you have a function 
halt
 that 
takes a function and an input as its parameters so that 
halt(A, X)
 will return true if 
A(X)
 terminates and false 
otherwise. now, consider the following function:
 
def trouble(A):
    while halt(A, A): pass
 
the call 
halt(A, A)
 determines whether 
A
 halts when applied to itself. still comfortable with this? What happens 
if you evaluate 
trouble(trouble)
? basically, if it halts, it doesn’t, and if it doesn’t, it does … We have a paradox 
(or a contradiction), meaning that 
halt
 cannot possibly exist. the halting problem is undecidable. In other words, 
solving it is impossible.
but you think impossible is hard? as a great boxer once said, impossible is nothing. there is, in fact, such a thing 
as highly undecidable, or “very impossible.” For an entertaining introduction to these things, I recommend david 
harel’s Computers Ltd: What They Really Can’t Do.