Fallacies? Paradoxes? Impossible! ~epilogue

Hey there netizens!

CSC236 has led me to think about paradoxes, fallacies, and impossibilites and the limits of induction.
And so, outside of the blog, I've looking into some fallacies and paradoxes, and unsolvable problems. They're very interesting. The most famous one every computer scientist has heard of is the Halting Problem. For those who don't know about it, it is basically the dilemma of finding an answer to whether an arbitrary program will halt some time or run forever. Computer geeks enthusiasts will also know that in 1936, Alan Turing proved that an algorithm to solve this problem does NOT exist. A great man, Alan Turing.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Well, I'm not sure what to put here, since most problems are already solved or way beyond me. Anyhow, I'll still take a crack at these problems in my spare time (when I'm not gaming). I may even continue updating this blog as well ^^. I might even start a problem of the week kind of thing on this blog. (Why didn't I think of this at the start of the course? orz)

So this is it huh. What a long journey's it's been.
Thanks Danny for letting me start this blog. Thanks CSC236 for beating some logic into me. And thank you, for reading through all my rambling.

Adios netizens! May we meet again!

Proof Works (II)

Hey there! Now then, let's get down to business.

I'd like to talk first about a question from the recent assignment. For the first question, we were supposed to prove that a DFSA that accepts L, where L = {x ∈{0, 1}* | fourth-last symbol in x is 0} has at least 16 states. I tried to design such a DFSA. I'm sooo close to making one. I was able to design a DFSA that accepts L, where L = {x ∈{0, 1}* | third-last symbol in x is 0}, which I'll post here.

While working on this problem, I think I've figured out how to prove the claim- unfortunately AFTER the assignment was due. (Orz) A good way to approach questions about finite state automata, as I've learned in tutorials, is to draw out every possibility as one state, then draw transition arrows between them. This sounds pretty logical, but before learning this, I would usually just charge head-on into a problem (a.k.a. the stupid approach). Anyway, for this question, here is what I SHOULD have done:

The combinations of all 16 4-bit strings containing 0s and 1s:

*each arrow represents one change in the binary string

From the diagram we can see that we need 16 states to represent each 4-bit string. If one state is missing, say 1101, some states will not be accounted for, and some strings, like 1100 and 1111, will end up being accepted, contradicting the definition of the language!

Ah, I wish I thought of this before the due date.. orz

Mmm I'm still working on the machine that accepts strings with a 0 in the fourth last position. Many frustrated hours were poured into this question (since I read the question wrong at the beginning and struggled to design this machine). Danny said that designing such a machine would be good for the soul (haha), so I might as well cleanse my soul and keep working on it...

Almost there

It seems I was mistaken. Friday's class was the last lecture! However, it's not over yet. There's the final exam. *plays ominous music* After that, this semester of Fall 2012 will be over ; ^ ;

As for class material, we've wrapped up the course with more finite state automata and regular expressions. The last tutorial really helped my understanding of the differences between NFSAs and DFSAs, and converting between DFSAs and regex.

~~~~~~~~~~~~
As promised, I'll be working on a proof here....but on second thought, I'm going to start a new post for it, since it might get long. See you in the next post!

T minus 1 Class?

Well, I'm still working on assignment 3. I barely have time to work on it- I chain-comboed 3 days of lack of sleep for a project for another course that was due today. Although, it seems I was on the fortunate side; some of my fellow classmates have not had any sleep for the past day or two. But now that that's over, I can finally concentrate on my CS assignments. Yes, sadly, assignmentS. (sigh)

Anyway, there's only 1 more class until the end of the semester! (I'm not sure yet if we have to go to class on Makeup Monday (aka: Wednesday)) Boy, time sure flies by fast. We're wrapping up with NFSAs and Regex and DFSAs and converting between the lot. I'm not a big fan of regular expressions so much, but I admit that they are pretty handy. I have a feeling this material will come up a lot in other courses, so I should really get it memorized and understood.

Next time, I will put up a post of a proof. Look forward to it ;)

Dat Fascinating Automata

Wow, I think I skipped a week's post. Reading week really messed up my inner clock, but at least I've got my energy back. To make up for this, I'll try to put up another post after Wednesday's lecture.

So, what's been going on the past two weeks? Nothing other than DFAs! (or DFSAs)- which, by the way, I find quite stimulating. Of course, I'm also an arts major, so I really appreciate the visuals. And it seems that all three of my CS courses have been talking about regular expressions and finite state automata recently. What a suspicious coincidence.

Anyhow, I've been working on A3 this weekend. I've got #2 and 3 pretty much down, but am struggling a bit on #1. I've been able to design a machine that accepts strings whose 3rd last bit is a 0, but I'm still working out the kinks for a machine that accepts strings whose 4th last bit is a 0. Danny dropped some hints last lecture- which are helpful for the proof portion of the question, but not so much for the design phase. Or perhaps I've overlooked something. Hmm...

Well, back to work! Logging out. Peace!

Reading week!

Yes! I'm officially over my mid-term blues! And not to mention it's reading week 2 days. I'm trying to spend it recuperating and catching up. As for the lectures, I think I'm alright on our current topic: proving correctedness. You just have to think more logically, i.e.: concentrate on what must be true at one point? Maybe I'll post a proof on correctedness in the near future.

Also---
Finished our second mid-term! Hooray! It wasn't easy, but it could have been a lot worse. I realized that I overlooked an important detail in the second question 10 minutes before the test was over, and spent the rest of the time frantically trying to correct it. If that hadn't happened, I would probably have enough time.  I think that the tests in general are pretty fair and not too long. Some of my other courses have exams and tests that are far too long, so I have nothing to complain about here.

Well, that's all for this week. Catch you later~

Mid-term Blues

And so, assignment 2 was over.

But the next test is just around the corner. Got to prepare myself!

Not really much to say this week, except that I have a case of the mid-term blues. Hopefully just a mild case though. I really need a holiday!! Reading week (aka: reading days) seems so far away.

Hopefully I won't end up like him:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
I'll probably put up a post soon after the test since I don't have much to talk about today.