we have finished the running time calculations and algorithms
complexity section of the course and we are now working on the last section of
the course: uncomputable functions, which is really confusing.
we first started
talking about the halting problem which is really one of these mathematical
paradoxical situations which makes you very confused just by talking about it.
so here is what it is all about in a
nutshell:
We know that some
algorithms/programs halt while others don't. (halt meaning that the
algorithm/program either give an outcome or raise an exception; in other words,
it just stop working at some point while an algorithm that doesn't halt will
loop forever.) and no one was ever able to implement an algorithm that checks if the function halts or not and
turns out that no one would ever be able to find one (it is proved!). That
makes halt a non-computable function.
Interestingly,
halt is not the only non-computable function; there are many more and you can
prove that they are not computable by using them to implement halt.
This section is getting even more complicated. (I really need to keep up with the material)
No comments:
Post a Comment