Hello, world. I'm posting this blog post after exams, so this post is not really an entry for the course SLOGs.... it's more like a Dear Diary entry where I pour out the contents of my aching heart. A soliloquy of my despair.
I'm currently in a state of panic. I went into the exam feeling fairly confident. I mean, I was able to answer all of the questions from the 2010/2013 exams, how bad could it possibly be? As long as I got over 40%, I'd still end up with a mark in the 70s. I prepared so much for it. My cheat sheet was crammed full of all of the possible questions from the assignments, tests, and lecture notes.
*echoing* Prepared so much for it. Prepared so much for it. Prepared so much for it *echoing*
On a scale of 1-10, I bombed that exam with a 100. I don't think I could have possibly messed up more than I did on that exam, besides like.... not showing up for the exam at all. All of the questions I thought would be on the exam, all of the questions that I prepared for.... were not on the exam. No halt (!!) , no generic big-Oh, no conversion of statements (Not all, Any). Nope. Nope. Nope.
I pretty much threw a course worth of achievements (I was so, so proud of my grade in the course... a mark in the high 90s) into a pile of feces.
I was expecting delta-epsilons to be on the exam, but I wasn't expecting TWO such questions to be on the exam. And they weren't ones I was familiar with. As soon as I saw the two, my mind went blank. Then I realized I couldn't solve both. I entered this state of complete and utter panic. I started sweating. My mind went blank. I'm actually fairly certain I was shaking at one point.
All of the questions I successfully answered, I somehow managed to misread the questions, and actually answer the wrong question. You're not reading that wrong. All of the questions that I SHOULD have gotten right, I somehow managed to prove something... that didn't even answer the question they asked. So I bombed the exam. Thoroughly.
How does one do this? How does one throw away a semester's worth of efforts in the matter of 3 hours. I failed that exam, without a matter of a doubt. We will be receiving our marks before Christmas, but I already know the result.
I went into the exam with high 90s, and now I'm not going to meet the minimum requirement for passing the course. I am going to have to repeat this course. I don't think words exist to describe how sad I am right now.
What is life.
Friday, December 12, 2014
Tuesday, December 2, 2014
That last minute struggle
After creeping and commenting on people's SLOGs over the course of this semester, I have to say that it's remarkable how people have gone from 2 posts all semester long (and this was the case for most people's SLOGs even 2 weeks ago!!!), to walls of texts. Oh, University, how is it that you are able to bring out the procrastinator that lies deep within all of our hearts.
Overall, I feel that the SLOGs are an excellent way of proving to yourself that you know what you're talking about. It's one thing to understand a concept, and another to demonstrate that you actually do understand the concept that you claim to understand. Was that statement extremely convoluted? Yes. But you know what I mean.
Throughout this semester, I've often gone from assuming that I understood a concept-- to realizing that I didn't. This was helped in part by reading SLOGs. I found it helpful to utilize other student's SLOGs to gain a better understanding of certain concepts. You often learn more from people who are also learning the material themselves. Good times.
Another thing that I have noticed is that I have spent a disproportionate amount of time in this course convincing others to realize why their proofs are insufficient or wrong. I'm not normally a confrontational person, but it can be a little exasperating at times when you're arguing with group members. You cannot prove a statement by restating it -- and you also cannot prove a statement by cleverly manipulating your proof so that it proves your statement, but only in certain cases. I'm not telling you that my answer is correct, but I'm most certainly pointing out why your proof cannot be correct.
After spending a semester taking CSC165, I have come to the realization that, although I have difficulty actually proving proofs, I have a strong foundation -- I can almost always tell when a proof is insufficient or wrong. I have also done enough practice proofs and studying to ensure that I am able to write proofs for the vast majority of proofs I should encounter in the exam. Hopefully this statement holds true for the actual exam. I also hope that, in the future, I will be able to devise proofs to problems with which I have not had prior experience with. Perhaps hone my intuition and induction skills?
Overall, it's been a great run. I can honestly say that this is most probably the only kind of course in which I would hear two students arguing over office hours with interjections of "BUT MY PROOF IS MORE ELEGANT" <-- legitimately, this was screamed aloud during Larry's office hours. Oh, UofT, you really, truly amaze me sometimes.
Anyways, I would 10/10 take this course again, and I would highly recommend it to any student - regardless of their major. Informative, educational, and enjoyable. Unfortunately, this SLOG will be seeing its imminent demise after the due date tomorrow, but it's been a great run.
Adieu!
Overall, I feel that the SLOGs are an excellent way of proving to yourself that you know what you're talking about. It's one thing to understand a concept, and another to demonstrate that you actually do understand the concept that you claim to understand. Was that statement extremely convoluted? Yes. But you know what I mean.
Throughout this semester, I've often gone from assuming that I understood a concept-- to realizing that I didn't. This was helped in part by reading SLOGs. I found it helpful to utilize other student's SLOGs to gain a better understanding of certain concepts. You often learn more from people who are also learning the material themselves. Good times.
Another thing that I have noticed is that I have spent a disproportionate amount of time in this course convincing others to realize why their proofs are insufficient or wrong. I'm not normally a confrontational person, but it can be a little exasperating at times when you're arguing with group members. You cannot prove a statement by restating it -- and you also cannot prove a statement by cleverly manipulating your proof so that it proves your statement, but only in certain cases. I'm not telling you that my answer is correct, but I'm most certainly pointing out why your proof cannot be correct.
After spending a semester taking CSC165, I have come to the realization that, although I have difficulty actually proving proofs, I have a strong foundation -- I can almost always tell when a proof is insufficient or wrong. I have also done enough practice proofs and studying to ensure that I am able to write proofs for the vast majority of proofs I should encounter in the exam. Hopefully this statement holds true for the actual exam. I also hope that, in the future, I will be able to devise proofs to problems with which I have not had prior experience with. Perhaps hone my intuition and induction skills?
Overall, it's been a great run. I can honestly say that this is most probably the only kind of course in which I would hear two students arguing over office hours with interjections of "BUT MY PROOF IS MORE ELEGANT" <-- legitimately, this was screamed aloud during Larry's office hours. Oh, UofT, you really, truly amaze me sometimes.
Anyways, I would 10/10 take this course again, and I would highly recommend it to any student - regardless of their major. Informative, educational, and enjoyable. Unfortunately, this SLOG will be seeing its imminent demise after the due date tomorrow, but it's been a great run.
Adieu!
Computability
I promised, and I shall deliver.
When we disprove the existence of a working halt function, what we are doing is claiming that not only has a working function not been written, but that a halt function cannot possibly exist. The disproof outlined in the coursenotes uses proof by contradiction.
First, assume that the halt function exists.
In this example, the author has cleverly constructed a function, confused, where if confused is passed itself as an argument, one can deduce that there will be two cases here: that the function confused(), when passed itself as an argument confused(confused) will either halt, or it will not halt. Now, this is where things were a little confusing. To completely the paradox, one must pass confused as an argument on itself. Not just any two functions will do. By doing so, we arrive at a contradiction.
Case 1: Assume confused(confused) halts:
Then halt(confused,confused) returns True.
Then confused(confused) goes into an infinite loop.
So, confused(confused) halts ==> confused(confused) does not halt.
Case 2: Assume confused(confused) does not halt:
Then halt(confused, confused) returns False.
Then confused(confused) halts.
So, confused(confused) does not halt ==> confused(confused) halts.
From this, we can conclude that confused(confused) halts <==> confused(confused) does not halt.
Thus P <==> not P. This is a contradiction. Therefore, the halt function is non-computable.
_________________________________________________________________________________
Reductions are a way to prove the non-computability of a function.
In a reduction, we first assume that our function is computable, and derive a proof by contradiction. By doing so, we prove that if our function is computable, then the halt function is computable. Since we have already proven that the halt function is not computable, we arrive at the contrapositive of our derived implication: that our function must be non-computable. The trick is to create a function f_prime() that utilizes the function f(i) within its body in a cleverly constructed way. If we are able to reduce halt to the meaning of life, we have produced a valid implementation of the halt function using our function. i.e we are able to utilize our function with arguments f_prime and i to determine whether or not a function halts on an input i. We know that this is not possible.
A function f is computable iff it is well-defined and we can tell how to compute f(x) for every x in the domain. In general, a function that remarks on the behaviour of another function will be non-computable.
When we disprove the existence of a working halt function, what we are doing is claiming that not only has a working function not been written, but that a halt function cannot possibly exist. The disproof outlined in the coursenotes uses proof by contradiction.
First, assume that the halt function exists.
In this example, the author has cleverly constructed a function, confused, where if confused is passed itself as an argument, one can deduce that there will be two cases here: that the function confused(), when passed itself as an argument confused(confused) will either halt, or it will not halt. Now, this is where things were a little confusing. To completely the paradox, one must pass confused as an argument on itself. Not just any two functions will do. By doing so, we arrive at a contradiction.
Case 1: Assume confused(confused) halts:
Then halt(confused,confused) returns True.
Then confused(confused) goes into an infinite loop.
So, confused(confused) halts ==> confused(confused) does not halt.
Case 2: Assume confused(confused) does not halt:
Then halt(confused, confused) returns False.
Then confused(confused) halts.
So, confused(confused) does not halt ==> confused(confused) halts.
From this, we can conclude that confused(confused) halts <==> confused(confused) does not halt.
Thus P <==> not P. This is a contradiction. Therefore, the halt function is non-computable.
_________________________________________________________________________________
Reductions are a way to prove the non-computability of a function.
In a reduction, we first assume that our function is computable, and derive a proof by contradiction. By doing so, we prove that if our function is computable, then the halt function is computable. Since we have already proven that the halt function is not computable, we arrive at the contrapositive of our derived implication: that our function must be non-computable. The trick is to create a function f_prime() that utilizes the function f(i) within its body in a cleverly constructed way. If we are able to reduce halt to the meaning of life, we have produced a valid implementation of the halt function using our function. i.e we are able to utilize our function with arguments f_prime and i to determine whether or not a function halts on an input i. We know that this is not possible.
A function f is computable iff it is well-defined and we can tell how to compute f(x) for every x in the domain. In general, a function that remarks on the behaviour of another function will be non-computable.