CourSe LOG Week 12 – Halt Function Proof

As mentioned in my last post, I am going to be speaking about the Halt proof and it’s usefulness in computer science. Alan Turing proved this in 1937 and we’ve referenced it ever since. In class, we had the opportunity to see how by using the contrapositive of this, we can show by using the idea of reduction, that other functions aren’t computable. This is probably one of the most powerful applications of this halt proof. As well, seeing as this is my last post, and in my first post, I mentioned Godel’s Incompleteness Theorem, it is fair to mention that the connection between these two ideas. As taken from the wikipedia page on the Haltting problem, we see the following connection explained:

The concepts raised by Gödel’s incompleteness theorems are very similar to those raised by the halting problem, and the proofs are quite similar. In fact, a weaker form of the First Incompleteness Theorem is an easy consequence of the undecidability of the halting problem. This weaker form differs from the standard statement of the incompleteness theorem by asserting that a complete, consistent and sound axiomatization of all statements about natural numbers is unachievable. The “sound” part is the weakening: it means that we require the axiomatic system in question to prove only true statements about natural numbers (it’s very important to observe that the statement of the standard form of Gödel’s First Incompleteness Theorem is completely unconcerned with the question of truth, and only concerns formal provability).

I cannot wait to explore these ideas much further in CSC240!

It’s been real!

~ R

CourSe LOG Week 11 – Computability

This week we had the opportunity to learn about computability. It is quite an amazing topic as it symbolizes the mixing of computer science and math. And more importantly, it as a branch of CS emphasizes the science part of the degree. Here, is where we learn whether our programs that we so non-chalantly try make, can actually be impossible to do so! And even better than that, we have the opportunity to show this via the proof techniques we’ve learnt so far.

Alan Turing, a great mathematician, logician and the father of computer science, (The Imitation Game is out in theatres soon!) came up with an ingenious proof of the halt function. This proof, I will discuss in my post next week!

CourSe LOG Week 10 – General Big Oh Proofs

This week in class we had the opportunity to learn about generalizing proofs about sets of functions instead of proving specific types of functions. As the professor outlined, this is the difference between saying: a burger from Lick’s is better than a burger from Harvey’s versus saying all food from Lick’s is better than all food from Harvey’s. We also had a chance to learn about computability, based on well-defined functions. And those are defined as the following – a function, f, is well-defined iff we can tell what f(x) is for every x in some domain. A function, f, is computable iff f is well-defined on some domain, and we can tell how to compute f(x) for every x in that domain. We learned how to do this by using reductions! And that, I’ll touch more on on next week’s sLOG post!

CourSe LOG Week 9 – Big Oh Proof

At the end of lecture this week, we got to do a relatively lengthy proof of Big O. This specifically involved showing that 2^n is not in O(n^2). We did this procedurally by breaking it down into reasonable steps:

1. Prove that the ratio of 2^n/n^2 goes to infinity as n goes to infinity
2. Translate this into it’s definition with c and n
3. Relate this back to the definition of Big Oh

This at first seemed a bit overwhelming, but after breaking it down into distinct intelligible steps, we saw that the proof was reasonable at the end. This is an important lesson to draw from when tackling big problems — break em down to smaller ones and conquer!

CourSe LOG Week 8 – Algorithm Complexity

When studying computer science, it is important to consider the complexity of the programs you are trying to create. This is what separates a computer programmer from a computer scientists. The algorithm complexity and the math behind it is what allows us to make progress in the practical world and software. We studied last week the complexity of merge sort versus bubble sort. Merge sort was in O(nlogn) where bubble sort was in O(n^2). The two are vastly different in large enough n. I look forward to learning more about different algorithm complexities and the analysis that is involved in them.

CourSe LOG Week 7 – Fermat’s Last Theorem

A lot of fellow students, friends and random strangers I’ve come across throughout my math education, always speak the words “math is so boring”, “math is so mechanical”. This is under the impression of the mechanical step by step math curriculum that is typically taught throughout highschool and frequents most first year calculus courses. The math which is beautiful, elegant and infinitely creative, deals with the nature of proofs. In this domain of mathematics, the mechanics are applied to use and be creative with abstract reasoning and abstract concepts. This is much like learning the alphabet, spelling and syntax of English (the mechanics of math) and then using that to write elegant beautiful prose (proofs). Fermat’s Last Theorem, a conjecture even understood by young children, an extrapolation on the pythagorean theorem, exemplifies this. After 7+ years, of being lost in the world wind of the creative process, Andrew Wiles proved this age-old conjecture. There was no set way to find the solution. 300 years of mathematicians couldn’t. But he widdled and woddled his way until it appeared to him, and finished the brushstrokes of his masterpiece. This is why I love and appreciate math! (especially because I could never produce any remotely interesting proofs!)

CourSe LOG Week 6 – More Proofs

We learnt more about developing a methodology for the intuition for proofs. For example, when we have a “For All P, ____” statement that we’re trying to disprove, a good strategy is to find a -P. This way, if we can find the existence of just this one case, it’ll disprove the entire statement.
Also, we got to explore more proofs on delta epsilon. It was enlightening to explore this again as I find the complications arise mostly because of expressing the assumption correctly. Understanding correctly that the predicate of something > or < delta is what is to be assumed and consequentially tinkered with is the key part to solving this problem. I look forward to doing more proofs with delta epsilon!

CourSe LOG Week 5 – Proofs

This week we started working on proofs: how to write them, the construction of them, and the logic behind solving them. Proofs, in my opinion are what make mathematics and consequently, the fields that it empowers, beautifully creative. To ponder of the great mathematicians that come up with proofs of theorems through the creative functioning of their minds gives me goosebumps. How did Euclid come up with the ingenious step of setting Px to the be the product of the imagined prime number – 1? This step in Euclid’s proof of there being infinite primes is what we ascribe genius thinking and a truly creative brain. This is in the same way we ascribe an artist’s individual brush strokes and consequential art piece, to be a marvel of their mind. I look forward to refining my tools in this domain of mathematics and attempting to empathize with the greatest minds in human history.

CourSe LOG Week 4 – Problem Solving!

This week we had the opportunity to tackle a unique problem solving task. The task involved finding a pattern with folding a piece of paper continuously. This was awesome! It provided a much more realistic view into how the real world works and the types of skills that are required in computer science jobs, academia, and everyday life. Some parameters are given, and some final statement is being asked to be reached, but there isn’t a direct methodology to solve it. There’s a bunch of trial and error that goes in: try method 1, it fails, but one part was successful and you incorporate that into method 2. Keep on going until something clicks. It’s not a smooth ride, and it’ll be jagged, but this is the type of uncomfortable feeling that one needs to get used to when dealing with complex problems with no obvious solutions. Can’t wait for more!

CourSe LOG Week 3 – Symbols & Parentheses

Symbols are important in mathematics. Rather, symbols are important in communication. This is the way we transfer information across massive distances and more importantly, through time. This week, in our discussion, a case we came across when discussing symbolizing English sentences was the notion of symbols and their uniqueness within parentheses.

1 is saying the same thing as 2. We often can get confused of this notion because we use the same symbols, respectively in 1). But, it is important to realize that within the parentheses, everything going on inside of it, stays inside of it.