Do you include coding assignments in an intro to complexity and computation course?

Question

In an introductory course on complexity and computing, I am thinking about including some programming tasks.

I wonder what types of tasks I could give the students beyond "construct" a Turing Machine in Python that determines whether a number p is prime.

Even though I am hesitant and unsure what type of programming tasks are going to spark their interest and help them learn, I believe that implementing stuff by hand will make them appreciate the subjects in Mike Sipser's book even more.

I would appreciate suggestions of tasks students might benefit from when implementing by hand in a modern programming language.

Answer 1

   ^{I'll use “TCS” — theoretical computer science — as the name of your course}

Should an introductory TCS course have coding assignments?

Yes and no.

Since there are two parts to that let me start with the third — the And!

Analogy:
When Johnny will only have candy and momma insists that spinach is good for him the result can be a difficult impasse. Yeah we all know because we've all been that Johnny/Debbie some time. And if we've grown well its because Momma is firm. And kind. And tells lies when needed. In the case of momma the lie may take the shape of some "tasty" — more likely colorful — jam added to the spinach.

Programming in a TCS course can be relevant, even central. Mostly its unhealthy but necessary jam. The point of this post is not to harp on the unhealthy jam but to remind about the underlying spinach!

Yeah the typical CS student resists theory/math. And the resistance can be as bad as Johnny above so that some artful lying helps. Here's a difficult story from the fringes, where I am sure that some of the kind of stuff you are trying to do would be helpful. But that it is helpful doesn't make it relevant.

Aside:

The first course I taught in the 80s was a discrete math course. I've never worked harder in my life. And students have never hated me more😆. So over years I changed my tack — less time on the course more on the engagement with students. You learn with time that education is not happening if engaging is not. So that has to become a priority. So then over time the tables turned and while students stopped complaining, even showed their enjoyment, colleagues sometimes expressed their resentment — You are charismatic. You can get away with murder. Doesn't mean what you are doing is right! The doing could be a wide variety of things… including teaching programming in a TCS course. And it can certainly help the larger teaching objective. But it doesn't make it right. Because its not relevant. To be fair maybe 98% students appreciated my ways. But there are the 2% who protest the irrelevant intrusions. And they are right in doing so.

So we need to explore what are the aims and purposes of a TCS course. Here are the basic ones that come to my mind:

1. Negative Results

I think these "Can't Do" results are the biggest and most significant content. You cannot…

1.1 Write a regular expression/DFA that accepts aⁿbⁿ

Even though the almost identical a^*b^* is trivial. Usually in TCS context that goes by the moniker pumping lemma.

So your "programming assignment". here would be (say): Write a python regexp that matches brackets. And of course the answer is NO CAN DO. The larger learning goal would be the appreciation of this classic regexp to match html tags

1.2 Subsume Syntax under Context Free Syntax

In CFG: If a language like C say is "statically" typed that means the type-system is syntax. So if it is syntax why is it not part of the CFG? Because while it is syntax its not context free syntax.

1.3 Detect whether an arbitrary Turing machine will halt

And of course the TM egs are most famous — You cant detect an infinite loop in the most general case. I find it amazing how even PhDs in CS from good universities don't get halting. I've sat in masters degree defenses where the great professor asks (in effect) Why did your compiler not prove correctness? If the student had a good grounding in TCS he would say: Well respected Sir… There's is the Rice theorem…

2. Universality Results

These are fuzzier — more philosophic than scientific — than the above. And yet closer to the heartbeat of the field.

A colleague who was teaching TCS made the following insightful observation :

CS is the conjunction of machines, computation, logic, languages and information theory. TCS should highlight these connections.

He candidly said that his course is light on logic and zero on information theory. Nevertheless it doesn't take more than a few minutes to 3-way connect Shannon, Information theory and the Bit.

Some of these profoundly wide-ranging ideas...

• Church Turing thesis
• The equivalence of widely different formalisms
• The relation of Turing-undecidability with Gödel-incompleteness with the lesser known Tarski undefinability
• The deep links of logic and computability...
• ...Going to the fact that Gödel is where it all starts, Turing is "just" an engineering improvement...
• ...To the use-mention distinction and why its central to CS.
  [I sometimes tickle my students with this "proof":
    Cat is a mammal.
    Mammal is a a 6-letter-word.
    Therefore cat is a 6 letter word
  ]

Perhaps mre recognizable in CS as the language-metalanguage distinction.

• To the giddy labyrinths of the famous Gödel-Escher-Bach [I recently learned that a large no of CS-ists of today became that because they read GEB 30+ years ago. Heh! I'm one of them!]
• The AI-TCS link. From Minsky back to Turing AI and CS has strong links. Coincidence?
• The matching of the Chomsky hierarchy with the machine hierarchy. Floyd Beigel is good here.

Do you really cover all this?!

As I said above its ok to lie 😉

No we cant do all of that, we cant do most of that. But if the teacher doesn't even have a sense of this direction I'd say the course has lost its way.

3. CS = Math

Turing was a mathematician, as was Church, von Neumann, Babbage, Ada Lovelace, Leibniz, Pascal… Is it simply coincidence that they are foundational in CS?? All the way back to al Khwarizmi whose book gives us algebra and whose name gives us algorithm!

In Turing's seminal paper "a computer" was a mathematician doing a computation that was so dumbed-down that it was mechanizable in principle.

Real computers made it so that that mechanizability goal would become practical as well

Unfortunately we've gone so far down that road that most of us find ourselves on the wrong side of Dijkstra's sneer:

And I don't need to waste my time with a computer just because I am a computer scientist.

One long term goal of having undergone a successful TCS course is that the student – later computer scientist – be firmly placed in the science side. Else default to the computer side!

How far does programming in there help?
Note that's not a rhetorical question!]

I do not wish to dissuade you from teaching programming in the TCS course… Just to give a feel for the sense of its relevance.

If you want a programming-centered course that is directly and fully relevant to the aims of TCS look at Neil Jones' Computability and Complexity from programming perspective.
Note: i am not recommending it! It's a monograph not a text and heavy going for the less than well-equipped and strongly motivated.

More historical math-logic-CS-programming stuff

[Yeah first three my writings...]

• CS Pre-history 0
• CS Early History
• Connections with Programming
• CS-ist = Math-ician List

4. The Human Context

Most of us accept that our modern world is largely based on something vaguely called "science". Notice the overlap "science" and "computer science"? And that this science is the creation of some remarkable individuals called "scientists". Maybe we teachers have some role to play in producing the scientists of tomorrow?

On the one hand...

Look at the typical CS curriculum. How much science is there?

• Some "surrounding" subjects eg discrete math, statistics...
• Some soft subjects eg management, economics...
• a great deal of technology which is typically classified as "core" eg programming in some fashionable langauge, databases and OS that showcase some technology and so on and so forth

In short you will find very little actual science in a typical CS curriculum... Other than the TCS course! So TCS teachers have a special responsibility.

On the other...

Beyond being CS-ists and teachers we're ultimately humans ... Participating in inducting our students into the fold of responsible adults.

CS has a rather dubious role on the human scene... In the larger CS curriculum, TCS a very special place toward this responsibility as follows:

No one needs to be told that humanity finds itself in a mess from its burgeoning self-destruction capability. And its hardly an exaggeration that this self-destruction capability is a direct consequence of our technological super prowess — nuclear winter? ecological disaster?? Pandemic mgmt for the big-corps not the living beings??? Just plain ol' drowning in our plastic garbage????

And computer technology is ever the servile hand-maiden of every world-destructive possibility

If we wish to contrinute to a world that will withstand our insane self destruction capability we need to have inhabitants that will withstand this insanity. And a key element of that is humans who can withstand the onslaught of so-called intelligent/AI systems that are mechanical at their core.

To be able to do that the future generation needs to understand the nature of this technological insanity without losing their humanity.

From the standard CS curriculum, a well-directed TCS can be one of the key components to that humane sane understanding.

Answer 2

I don't give many assignments in my coursework on that material, but I have a few important ones. I have them implement NFA, DFA, and PDA in Scheme. The function headers look like so:

(define (DFA input Sigma S s0 delta F)
 ...)

(define (NFA input Sigma Q q0 Delta F)
 ...)

(define (PDA input Sigma Gamma S s0 delta F)
 ...)

I will say that these activities are quite hard for the students. That is likely because I am making them do it in Scheme (because they have just learned functional programming and I want to expand on that skill), but their primary experience for years has been in Python and Java.

In particular, the stack-as-cons-boxes combined with nondeterminism is really hard for some of them to implement, so I have sometimes skipped the PDA assignment entirely. I waffle about this assignment because of its difficulty.

My main goal in all of these is really familiarity with the definitions of the functions. By the time they've implemented NFA and DFA, they know what (for instance) Sigma is, and our subsequent lessons in class reflect that fluidity.

For Turing Machines, in light of the difficulties they have with functional programming, I bring them back to Java. They implement a Turing Machine, and then use it for a contest that I call the Daring Duck.

Daring Duck is a variant on the Busy Beaver problem. The goal is that their function should output as many ones as possible on the tape, but it must halt on its own before the deadline!

While they must stick to the API for the Turing Machine, they are encouraged to think extremely creativity about the Turing Machine implementation in order to best support their contest entry. Importantly, while I specify the function call, I specify nothing about the format of the output, nor the internal memory representation of the tape. Creative and engaged students can achieve scores in the millions, billions, or beyond, even in the space of a two-week assignment.

For the duck assignment, since they can build any machine they wish with whatever starting input they wish, their final score is divided by the sum of:

• number of states
• cardinality of their chosen alphabet, and
• the number of cells already written to the tape as input.

(Null cells between the starting position of the head and some final character all count as input, so they can't just put a single stop character 3 billion spaces away and loop on null until they get there)

The contest isn't a major part of their grade, just a few points for an attempt, and a Rubber Duck Trophy for the winner.

Given how the score is calculated, I award a bit of extra credit on the overall assignment to anyone who manages to get a score above 1, because figuring out how to get past that particular hill is quite challenging, and requires them to think through Turing Machines and growth of functions in ways that they haven't before. Not everyone gets to the flash of insight that allows them to grow beyond their states, alphabet, and starting input.

I also participated in the first year of the contest! In subsequent years, I've keep my score an absolute secret until the end of the contest, but I promise a free 100% test grade to anyone who beats me. I know that that possibly sounds too generous, but in truth, none of my students have ever even come close to my score, so I'm okay with dangling that particular stick in front of them. The big prize gets kids excited and engaged, and it also enhances the spirit of fun to compete against the teacher.

Part of the reason I don't particularity grade the result of the contest is that there is brinkmanship among the top students, and sometimes they underestimate execution time, and so wind up with an unhalted machine at the deadline (Daring Duck score 0). There are also crashed laptops, old and slow machines, forced windows updates, and every other difficulty you might imagine. I don't want to penalize them for any of that stuff, much of which is out of their control. I also don't want to turn something fun into something stressful. I think it's a good learning activity, and a way to get them thinking about execution time in a new light, and that's good enough for me.

Answer 3

I've never taught this sort of course, but I'd start at the bottom of the Chomsky hierarchy:

1. Program a finite state machine: coke vending machine.
2. Program a pushdown automaton: parking garage with "is empty" indicator.
3. Linear bounded automata (Did you delete my comment?) are always the hardest. I think primality testing would be an example here.
4. By all means, have them program a Turing machine, do a "busy beaver" or so.

Answer 4

Yes - things like sorts, regexes, and virtualization are great ways of explaining complexity and CS theory

Sorts are a great example.

YouTube video with sorts animated

Implementing them myself in one of my courses let me experience n*log(n) vs n^2. Students will see bubble sort taking much longer than quick-sort as the sample arrays get larger.

So is regex. Maybe a complete regex engine would be too much, but a paired-down one could still demonstrate why tag matching HTML will never work.

I probably won't do a "build a touring machine in Python" project, but pick some sort of finite state machine problem and have them code it up.

In my first theory class the professor assigned everyone "Build a state machine of the elevator in this building." I think it was the first day of class. I remember he went over several assignments with the student's permission.

What I remember

1. No one modeled the fire key

2. Several people didn't model going up/going down, just went to the closes floor

3. No one modeled restricted roof access

It showed all the students how easy it was to make bad code because they hadn't looked at the problem and really thought about what the underlying problem was. Thinking about the underlying problem is what theory focuses on.