Thursday, April 14, 2011

Going off topic in class: I think it worked--- this time

Recently I went off topic in a class. I think it was okay but I want YOUR thoughts.
  1. On Monday I
    1. defined Primitive Recursive functions
    2. showed them that addition, mult, exp are all primitive recursive,
    3. talked a little bit about TOWER and WOWER, both primitive recursive,
    4. constructed by diag a computable function that was not prim rec,
    5. noted that this function is not natural
    6. noted that there are natural computable functions that are not prime rec (NOTE that I noted this),
    7. made the point that I can do the same diag argument for ANY reasonable system of (total) computable functions.
  2. On Wednesday I was all set to start Turing Machines when a student named Amber said You promised to show us a natural example of a computable function that is not primitive recursive! I didn't recall exactly promising that but I very well might have and if a student cares about these things you want to nurture that curiosity.
  3. I told the class that I would toss out today's lesson plan and talk about this, but I would be informal and some of what I said might not be quite right, but would get the idea across.
  4. I asked one of the students who had his laptop up to stop surfing porn and look up Ackermann's function for me, so I could get the definition right.
  5. I talked about the Union-Find Data Structure that has amortized O(n INVERSE-ACK(n)) running time for n operations. I noted that this would not be an impressive use of the Ackermann's function if Amber could find an O(n) structure. I had the class vote on if Amber could do that. This was about fifty-fifty. I then told them that Amber could not, not because she is not a fine programmer, but because there is a lower bound proof that nobody can do better. That is, the lower bounds has been proven.
  6. I then talked about Goodstein Sequences which lead to computable functions that are not primitive recursive.
I went off topic. I am one lecture behind. Was it worth it?
  1. This class is not a prereq to anything else so I do not HAVE TO COVER everything.
  2. If I don't cover the topics on the syllabus then the guy who made up the syllabus, Gasarch, might get mad at me. This does not worry me.
  3. I doubt I will end up cutting anything important. I usually spend the last few lectures on misc topics (e.g., sparse sets cannot be NPC unless P=NP) which I can skip.
  4. They were interested in this. Not just Amber, but the whole class. That makes it worthwhile.
  1. I told the linguistics major in the class that Ackermann's function has applications in linguistics. He believed me until I told him YOU"VE BEEN PUNK'D!!
  2. Ackerman's function gets 2,870,000 hits on Google. Ackermann's function gets 6,740,000 hits on Google. Does that make Ackermann correct? What if the wrong spelling got more hits?


  1. Wow, interested students... I'd love to have a full class of them, one day. The classes I'm TA-ing usually have two or three people who understand and like the concepts (this is a good 10%), and they're enough for me to feel useful, but a whole class would be so interactive !

  2. Seems odd that you would cover this in an undergraduate class on computability. My gut reaction was that you should not have covered this material:

    (1) How many students (including Amber) were able to follow the discussion?

    (2) Sure there is nothing you must cover, but there are plenty of things you could cover. Presumably one goal of the class is to get students interested in TCS. Does discussing these types of topics accomplish that goal?

    Actually, the above should be viewed as non-rhetorical questions. If students could follow it, and genuinely seemed excited by the material, then it seems fine to cover it. Otherwise, I would not.

  3. Cadilhac: It helps that this course is optional so the students in it want to be in it (or they hate programming).

    Anon: The students were interested; however,
    you raise another question: is Prim Rec Functions and Ackermann's function appropriate for this course? I would say yes as an optional topic (I didn't cover it last time I taught the course).

  4. Gasarch is so this still a complexity blog?

  5. I think it is not bad to go off topic to get them interested as long as it only happens occasionally.

    con: I would guess that most of them didn't really get the things completely (you can check it by asking them about it in the next class) although most of them might think they did. In my experience it can also cause confusion about the basic material (for students doing below the average). It might have been better to leave talking about this to the last minutes of the class/after class/office hour so you are sure that most of students there are really interested.

  6. oh, shit. Gasarch started to itemize recursively!

  7. Anonymous 2:54 I am still LOL.
    Thanks for your contribution to
    International Moment of Laughter day!

  8. Sounds great. IMHO Turing Machines are a little over rated anyway (if you must go the machine route, unlimited register machines are so much nicer, as discussed in Cutland's classic text). Major props for pulling so many examples out of thin air with no advance warning, that is impressive.

  9. so wait, what is the rate of increase ?
    -factorial > exponential > geometric > arithmetic > blah blah

    but how fast does the ackerman values grow ?

    faster than factorial ? how fast? does that too have a name

  10. Yay!
    A professor that actually listens to his students and explains interesting things. 100% - if the students want to learn about a topic that is somewhat related to the course than you should teach it.

    Seems odd that you would cover this in an undergraduate class on computability.
    I hope I don't have you as a prof. Not teaching a topic because it an "undergrad" course is bad. I understand that certain material has to be covered, but if you have the time don't dumb it down for undergrads!

  11. Ackermann's function grows faster than any (a few exceptions) function you encounter in normal mathematics. Faster than factorial, faster than x maps to x to the x... to the x x times.

    `Ackermann-like growth' is a term you hear sometimes.

    How well did they get it? They DO know some factoids about some strange functions that grow really fast. They DO NOT know proofs of any of this stuff.
    Is that worth knowing? I think so.

  12. Make the extra lecture/material a 5pt bonus question on the final, something simple to see if anyone was really paying attention.

  13. I think we all should consider:

    "The algorithm that recognizes all algorithms that do not recognize themselves."

    Does it recognize itself?!?!

    Some say that the above sentence is worth 7 million dollars. Others say that this is the single true statement in all mathematics. Anything else is both true and false.


    Rafee Kamouna.

  14. The Ubiquitous Anonymous12:54 PM, April 16, 2011

    If any of Bill's students are reading here, please ignore Kamouna comments as more regular followers of the blog have learned to do.

  15. They should ignore me because this algorithm recognizes itself iff it does not recognize itself. Everybody knows what would happen thereafter.


    Rafee Kamouna.

  16. @Rafee: Can you show that constructing a HERP with the input of DERP will create a contradiction? I heard you work with something along these lines.

  17. Thos who try to be intelligent will tell you that this is an example of the halting problem. Tell them what about the program that runs all programs that do not run themselves.

    Or, the firewall that protects all networks that do not protect themselves.

    Probably better since viruses destroy computer systems, it may be beautiful to have the end of TCS by a virus. It is the virus that infects all programs that do not infect themselves.

    I leave it for you to formulate the Turing notions of running, protection and infection.


    Rafee Kamouna.

  18. That's

  19. Rafee Kamouna @

    what are you currently working on ? Any interest in collaborating on a new problem with me ? I am working on NP vs P and occasionally on P vs NP. Do u do that too ? would be awesome if we could write up the proof. Let me know.

  20. It is not the omnipotence paradox. When soemone claims that:"Can God create a stone that he cannot carry" is paradox. Yes, it is. But it didn't prove anything about God. It proves a property of language which is the self-referential self-negating statements lead to paradoxes.

    When you refer to algorithms or programs, they are written in formal languages. So, the above paradoxes prove properties of algorithms and programs unlike God.

    I hope that this clarifies your misunderstanding.


    Rafee Kamouna.

  21. @ Derrick

    You are most welcome to collaborate with me.

  22. Dear Derrick,

    You are welcome to collaborate with me. But P vs. NP is already over!

  23. Do you know for sure that the student was watching porn?