Happy Birthday, Magritte!

At the end of the lecture we were left with a tantalizing little puzzle to think about (which is great for me, because it gives me something to think about during the walk home - I feel much more efficient that way). Prof. Heap, near the end of class, told us that the language with an equal number of zeros and ones couldn't be expressed by any regular expression, so I took it upon myself to think of a proof on the way home.

Let L be said language, and let Q be a DFSA that expresses L. Let n be the number of states in Q (there must be a finite number, by the 'F' in DFSA).

Let x be the string consisting of n+1 0's concatenated.
I assert that there must be at least n+1 states between the state at x, and the accepting state. This string is able to reach the accepting state, we know, if n+1 1's are appended to it.

We can prove this result by contradiction. Let j and k be strings consisting entirely of 1's, both of whose lengths are greater than 0 and less than n+1, and such that |j| < |k|, and sigma(xj1) = sigma(xk1) = q0. Then let q1 = sigma(q0, 1), q2 = sigma(q1, 1), q(m+1) = sigma(qm, 1)

let p (running out of letters here) equal (n+1) - |k|. then qp must be the accepting state, since it represents n+1 0's, concatenated with |k| + [(n+1) - |k|] = n+1 1's. However, this state also accepts the string that is n+1 0's concatenated with |j| + [(n+1) - |k|] < n+1 1's. Here, the number of 1's and 0's are obviously not equal, so we've arrived at a contradiction.

Then the DFSA passes through at least n+1 states. However, this contradicts our assumption that the DFSA has only n states. Therefore, L cannot be represented by a DFSA, and by extension, cannot be represented by a regular expression.

Man, that was a kinda ugly proof, in no small part because of the alphabet soup. Maybe it would just be easier to explain my insights informally. My idea was simply that, to represent the language would require an infinite number of states (I found it easier to envisage as a DFSA than a regex), since there would need to be at least one state for each difference in 0's and 1's (intuitively, anyways).

If there were such a thing as a deterministic infinite state automata (hey, it doesn't sound as crazy as being nondeterministic), it seems like it would be pretty easy to write. It could just be a ladder climbing infinitely in both directions with one symbol taking you up and another taking you down, and the accepting state being right in the middle.

Test 2

Everything's just been hunky-dorey.


...

I guess that wouldn't be an acceptably meaty Slog post, would it? Really though, I've just been sailing through. I love the material, I love the assignments and the problem sets, I have nothing to complain about.

I just came back from term test 2, so I suppose I'll talk about that briefly, for lack of anything better to pontificate on. It went pretty well, except for the last question, which was about proving the termination of a loop. I think my logic was correct, but I leapt into the proof without looking first, and so I know the approach I took was inelegant (and probably had some gaps). For some reason, I decided to make a function that takes valid loop indices as its domain, and spits out the value of n at that index. Then I proved that it was decreasing, and always natural. I only mentioned loop invariants in passing, which was kind of silly.

It's a mistake that I've made a lot in tests, of getting antsy about the time limit, and feeling obliged to start writing stuff down as soon as I see the question, not wanting to "waste time" planning out a proof. For that reason, I often end up writing out base cases that turn out to be redundant, or make some claims without the appropriate intermediate steps, and turn my paper into a roadmap of arrows, inserting lines in the cracks where they're needed. So I suppose something to work on in the future would be remembering to take time to make a quick mental plan of where I want the proof to go, rather than blindly filling in a predicate and some base cases, and hoping that they'll lead me to inferences, that will lead me to inferences, that will lead me to the conclusion I want.

Midterm, A1, etc.

As I was writing up a solution to Problem Set 3, I realized I'd been neglecting my SLoG so I should give an update on my adventures in 236.

The mid-term went well. I was surprised that it seemed to be all on induction, but that was fine with me since I feel very comfortable with it by now (which I wouldn't have thought possible a year ago). I just now saw the grades posted, and am pretty happy that I'm one of the five who aced it (we should form a posse), and am delighted that the number of people enrolled in the class is a power of 2. I decree that no-one is allowed to drop the course now (unless it's an exodus of 64 people).

I got my A1 back, and was pretty happy with how it turned out. I'd be lying if I said I wasn't saddened when some cruel TA who sipped the wine of life and found it to be bitter said that my cherished procedure for question 2 was "not the simplest", but "okay". Ouch. On the other hand, they were quite generous in giving me full marks for question 3, when my part a was needlessly long and circuitous and I made a small error in reasoning in part b. So I guess I came out even?

(Actually, after going back and re-reading the assignment handout, I realise that I probably came out ahead. I talked with Prof. Heap briefly about question 2 last week and he mentioned that at least one TA was taking off marks for not starting with a base case of 0, which I did, while he thought that 2 was the only appropriate base case. I had thought that the premise was that the menus could differ by no more than one meal, when in fact the handout said "exactly one" meal. So really, I should have lost a mark there, if not for my merely "ok" procedure)

I'd still be curious to know how many different approaches people used in question 2, and how they were distributed. I've enjoyed reading the TAs' posts on the message boards where they do something similar, going over the solutions to in-class problems or problem sets, along with an analysis of how many students solved it, common mistakes that were made, and alternate solutions.

I think that's all there is to report. It's a sad irony that the course that is, by far, my favourite this semester, is the only one where I have a platform to complain. If I had a SLoG for, say, STA247, let me tell you...

"Interesting" being a relative term

The deadline for A1 has passed, and I feel pretty confident about the answers I submitted. I did notice a few interesting discrepancies between the sample solutions and mine though:

1) The sample solutions consisted of fewer than half as many lines as mine, which reaffirms my fear that my proofs are too long. I think this was partially - in question 3 specifically - from my proof taking a circuitous path. In general though, I may have tried to be more precise than was necessary. I think switching to a more, um, prosey (my proofs are anything but prosaic) style cut down on their size a good bit, but I'm still working on cutting out more redundant or obvious stuff.

2) My solution to question 2 was completely different from the sample solution, which I thought was pretty cool. The technique in the sample solution is a bit easier to follow, but I like mine (which consisted of splitting the nth cycle into 2^n-1 pairs, and inserting a pair of new values in the middle of each one) just fine. I'd be really curious to know how many people used my solution, and how many used the other, and if there are even more techniques that work that people submitted.

3) The solution to question 3b made me realized that I had made the careless mistake of conflating "cannot be expressed as a ratio of natural numbers" and "irrational". This didn't actually meaningfully affect my proof, which would apply if I went back in time and replaced the latter term with the former, so I hope I won't be punished too harshly for my slip-up.

Also, no matter how many times I look at the solution to question 3b, I can't make sense of it. I can't decide whether it's more likely that this is the result of a mistake or transcription error on the part of the author, or if I'm just missing something stunningly obvious.

Speaking of missing the stunningly obvious, I almost fell for the pseudo-proof of the six-sidedness of hexagons during yesterday's lecture. It wasn't until after a minute or two that I thought to myself "it sure is neat that he proved that without using any properties of hexagons", and then the inevitable "wait a minute...". I'm embarrassed to admit that I briefly fell for a proof that could easily be adapted to "prove" that all horses are the same colour.

Rethinking my proof style

I was surprised by the sample solutions that were posted recently for Problem Set 1. I had assumed that the proofs we were doing would follow the format from 165 (Assume, indent... then... then... assume, indent... then... then... dedent... then... dedent... then for all...). However, the sample solutions posted seemed much less formal than those from 165, and made much use of prose over symbols. I think I like the idea of writing a proof in paragraph form, given the difficulties I've been having with Assignment 1. In some ways, I've been having more problems expressing myself clearly than in actually understanding and finding a solution for the problems. My proofs to the first two questions look like someone spilled a bowl of alphabet soup on my monitor - way too many subscripts and variables. I think one of the reasons for that was that, if I wanted to discuss a subset of a certain set, without doing anything to the set itself, I would still have to declare and justify the existence of both, whereas if I were doing a more prosaic proof, I could describe the properties of the set and then move on to what interested me, only giving an explicit representation to the things that I was going to use.

If that makes sense.

I'm almost tempted to rewrite my proofs to the first two questions in the style of the sample solutions. I'm loath to erase the <100 lines I've already committed to them, though. I know I'll definitely be adopting a less formal technique for the last two questions, and the second problem set though.

Weeks 1 and 2

"Slog", "Blog", such ugly guttural words. Anyways.

I'm glad to be back. I've been looking forward to CSC 236, because I so enjoyed 165 last year. It's strange - I did pretty awfully in MAT137 last year, but when I'm doing logic and proofs I just feel right at home. Maybe it's because every math class I've taken in my life has focused on "calculations of the grocery-bill variety" (a phrase cribbed from Uncle Petros and Goldbach's Conjecture which I reread over the summer), whereas 165 and 236 have felt like they required a lot more independent thought, and not just memorization and repeated application of formulas and procedures. For that reason, I found solving proofs in 165, and now 236, a lot more satisfying. But maybe that's just me explaining away my incompetence at calculus.

I feel like I've done pretty well with the material during these first two weeks. It's taken me a while to warm up to induction since last year, but at this point I feel quite comfortable with it. The explanation the book gives in section 1.2, reconciling the principles of simple and complete induction with induction as proof technique by expressing the natural numbers for which a predicate is true as a subset of the natural numbers, and then using the principle of induction to show that that set is a superset of the natural numbers (and hence, exactly equal to them).

My only difficulty in solving the first problem set came in the second question, trying to decide the degree of rigour with which I would need to justify a certain statement. Specifically, I had partitioned the set of pairs for {0, 1... n+1}, Dn+1 = {{1, 2}, {1, 3}, {2,3}... {n, n+1}} into Y: {s \in Dn+1, n+1 \in s} and N: {s \in Dn+1, n+1 ~\in s}, and was trying to prove that the cardinality of Y was equal to n, which seemed obvious to me, but somewhat messy to prove. My solution was just to add an appendix to the end of the proof, with what ended up being about a page of writing, elucidating the reasoning behind those two lines, with a note to the marker that they could refer to it if they found the lines alone insufficient.

Wasn't that an interesting story? There are more where that came from. Stay tuned for next week.