Halting problem.....SO CoNfUsiNg

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)

News so far......

I know it has been a long time since the first post but that’s because I was preparing some cool program Danny had challenged us to do but since I am still not done yet (have not started actually J, it has been a busy week) and haven’t posted anything new, I figured it is time for me to post something before I actually tell you about the cool mental experiment we did in class (probably, I will have enough time by the reading weak). So wait for that, but for now, here is what has been happening in csc165 so far:

we have had our 3^rd tutorial this week and OUR FIRST ASSIGNMENT. I can’t describe the assignment as hard but I can’t describe it as easy either. Well, that’s the weird thing about this course. You might think your answer is right just because it makes sense to you and turns out it is completely wrong. That is why you must read what you have written from many different angles and try to prove yourself wrong (which is a common thing between all sciences). I hope I did well on the assignment.

As for the lectures, I really loved the part when we try to prove that one statement is equivalent to another statement (since now, you can actually know if your answer is right or wrong). We are starting proofs so I guess that should be fun and I am looking forward to it.