When students are wrong but have a valid point, encourage them

Computational Complexity 2018-03-12

I often have the class VOTE on a statement (the choices are usually TRUE/FALSE/UNKNOWN TO SCIENCE/Stewart-Colbert-2020) I ask the students who voted incorrectly (some say anything except Stewart-Colbert-2020 is an incorrect vote, though I'm partial to Bee-Oliver, though John Oliver was not born in this country so he's not eligible, though our current president might say that neither was Obama so thats not a bar to the presidency) why they vote the way they do to get a good discussion going. I give some examples. I use real first names but decided to not give last names for reasons of security. The people involved all agreed. If you have examples of students being WRONG but HAVING A POINT, leave an intelligent comment about it! 1) In Discrete Math they  vote on: is Q, the rationals, countable?One of the NO votes was named Alice (really!). Alice: The rationals, like there are SO many of them. They are just so crammed in their. I mean really! Bill: I think you want to say that between any two rationals is a rational. Alice: Thats what I said!! Bill: Great! And realize that  a set is countable if there is a bijection from the  set to N. So what you are really saying is----- Alice: There is a bijection between N and Q but not an order preserving Bijection! 2) In Formal Lang theory they vote if alpha is a reg expression and L(alpha) is the lang generated by alpha then is there a reg exp beta such that L(beta) is the complement of L(alpha). One of the NO votes was named Andrea (nickname Andy). Andy: Given alpha I just don't see an easy way, or for that matter any way, to create beta. Bill: I will soon prove that regular expressions are equivalent  to DFA's. So what one would do is take the L(alpha), form the DFA, complement the DFA, then convert back to a regular expression. Andy: Oh, yes that works, but it seems complicated. Bill: It is! You though it would be complicated so it was false. Even though its true, your intuition that its complicated is correct! In fact, there are reg expressions of length n such that the complement lang has a rather large reg expression. 3) Formal Lang theory again. Not a vote this time. I had on the board the regular expression (a UNION b)(a UNION  b )^* A student Dolapo thought it could be simplified: Dolapo: Can't you write that as the regular expression (a union b)^+ ? Bill: Yes and no. Yes the lang is (a UNION b)^+, but + is not allowed in regular expressions. Dolapo: Why not? Bill: First off, they really could have been defined that way and perhaps should have. So why weren't they? I go with historical accident, but some people disagree- see my blog post here