Recently I went off topic in a class. I think it was okay but
I want YOUR thoughts.

On Monday I

defined
Primitive Recursive functions

showed them that addition, mult, exp are all primitive recursive,

talked a little bit about TOWER and WOWER, both primitive recursive,

constructed by diag a computable function that was not prim rec,

noted that this function is not natural

noted that there are natural computable functions that are not prime rec
(NOTE that I noted this),

made the point that I can do the same diag argument for ANY reasonable system of (total) computable functions.

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.

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.

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.

I talked about the
UnionFind Data Structure that has
amortized O(n INVERSEACK(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 fiftyfifty.
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.

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?

This class is not a prereq to anything else so I do not HAVE TO COVER everything.

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.

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.

They were interested in this. Not just Amber, but the whole class.
That makes it worthwhile.
Misc:

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!!

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?
Wow, interested students... I'd love to have a full class of them, one day. The classes I'm TAing 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 !
ReplyDeleteSeems odd that you would cover this in an undergraduate class on computability. My gut reaction was that you should not have covered this material:
ReplyDelete(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 nonrhetorical questions. If students could follow it, and genuinely seemed excited by the material, then it seems fine to cover it. Otherwise, I would not.
Cadilhac: It helps that this course is optional so the students in it want to be in it (or they hate programming).
ReplyDeleteAnon: 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).
Gasarch is so weird...is this still a complexity blog?
ReplyDeleteI think it is not bad to go off topic to get them interested as long as it only happens occasionally.
ReplyDeletecon: 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.
oh, shit. Gasarch started to itemize recursively!
ReplyDeleteAnonymous 2:54 I am still LOL.
ReplyDeleteThanks for your contribution to
International Moment of Laughter day!
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.
ReplyDeleteso wait, what is the rate of increase ?
ReplyDeletefactorial > exponential > geometric > arithmetic > blah blah
but how fast does the ackerman values grow ?
faster than factorial ? how fast? does that too have a name
Yay!
ReplyDeleteA 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!
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.
ReplyDelete`Ackermannlike 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.
Make the extra lecture/material a 5pt bonus question on the final, something simple to see if anyone was really paying attention.
ReplyDeleteI think we all should consider:
ReplyDelete"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.
Best,
Rafee Kamouna.
If any of Bill's students are reading here, please ignore Kamouna comments as more regular followers of the blog have learned to do.
ReplyDeleteThey should ignore me because this algorithm recognizes itself iff it does not recognize itself. Everybody knows what would happen thereafter.
ReplyDeleteBest,
Rafee Kamouna.
@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.
ReplyDeleteThos 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.
ReplyDeleteOr, 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.
Best,
Rafee Kamouna.
That's http://en.wikipedia.org/wiki/Omnipotence_paradox
ReplyDeleteRafee Kamouna @
ReplyDeletewhat 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.
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 selfreferential selfnegating statements lead to paradoxes.
ReplyDeleteWhen 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.
Best,
Rafee Kamouna.
@ Derrick
ReplyDeleteYou are most welcome to collaborate with me.
Dear Derrick,
ReplyDeleteYou are welcome to collaborate with me. But P vs. NP is already over!
Do you know for sure that the student was watching porn?
ReplyDelete