Post Five

Big O, Omega, Theta, Halt and reduction

    These were by far my favorite topics in the course. Big O, Omega and theta especially because it managed to tie in everything from the course up until that point and tie it into computer science. Not that the prior knowledge wasn't useful or important in its own right but it was great being able to tie it all so neatly into something more distinctly computer science related.

    The interesting thing about the proof for why a function Halt does not exist was, at least for me, counter intuitive at first glance. Though as I began to understand it better it started to make more sense. Reduction was also somewhat confusing at first because the function that you are trying to show cannot exist is irrelevant. Eventually though it clicked for me that the important thing is what we know about Halt and not the function we are, in a given situation, trying to show is not computable.  That is, if we can implement Halt by assuming the given function is computable then by contradiction it cannot be computable (since we know Halt is not computable).