<p>I've never taught this sort of course, but I'd start at the bottom of the Chomsky hierarchy:</p>
<ol>
<li>Program a finite state machine: coke vending machine.</li>
<li>Program a pushdown automaton: parking garage with &quot;is empty&quot; indicator.</li>
<li>Linear bounded automata (Did you delete my comment?) are always the hardest. I think primality testing would be an example here.</li>
<li>By all means, have them program a Turing machine, do a &quot;busy beaver&quot; or so.</li>
</ol>

CC BY-SA 4.0
2022-01-15T18:58:10.177Z
2022-01-15T18:58:10.177Z
Victor Eijkhout
<p><strong>Yes - things like sorts, regexes, and virtualization are great ways of explaining complexity and CS theory</strong></p>
<p>Sorts are a great example.</p>
<p><a href="https://www.youtube.com/watch?v=kPRA0W1kECg&amp;ab_channel=TimoBingmann" rel="nofollow noreferrer">YouTube video with sorts animated</a></p>
<p>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.</p>
<p>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.</p>
<p>I probably won't do a &quot;build a touring machine in Python&quot; project, but pick some sort of finite state machine problem and have them code it up.</p>
<p>In my first theory class the professor assigned everyone &quot;Build a state machine of the elevator in this building.&quot;  I think it was the first day of class.  I remember he went over several assignments with the student's permission.</p>
<p>What I remember</p>
<ol>
<li><p>No one modeled the fire key</p>
</li>
<li><p>Several people didn't model going up/going down, just went to the closes floor</p>
</li>
<li><p>No one modeled restricted roof access</p>
</li>
</ol>
<p>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.</p>

CC BY-SA 4.0
2022-01-16T23:54:09.957Z
2022-01-16T23:54:09.957Z
sevensevens
<p>   <sup>I'll use “TCS” — theoretical computer science — as the name of your course</sup></p>
<blockquote>
<p>Should an introductory TCS course have coding assignments?</p>
</blockquote>
<p>Yes and no.</p>
<p>Since there are two parts to that let me start with the third — the <em>And!</em></p>
<p>Analogy:<br />
<em>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 &quot;tasty&quot; — more likely colorful — jam added to the spinach.</em></p>
<p>Programming in a TCS course  <strong>can</strong> 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!</p>
<p>Yeah the typical CS student resists theory/math. And the resistance can be as bad as Johnny above so that some artful lying helps. <a href="https://matheducators.stackexchange.com/questions/24549/combative-students-in-proofs-classes">Here's</a> 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.</p>
<p>Aside:</p>
<blockquote>
<p>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 — <em>You are charismatic. You can get away with murder. Doesn't mean what you are doing is right!</em>  The <em>doing</em> 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 <em>are</em> the 2% who protest the irrelevant intrusions. And they are right in doing so.</p>
</blockquote>
<p>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:</p>
<h1>1. Negative Results</h1>
<p>I think these &quot;Can't Do&quot; results are the biggest and most significant content. You <strong>cannot…</strong></p>
<h2>1.1 Write a regular expression/DFA that accepts a<sup>n</sup>b<sup>n</sup></h2>
<p>Even though the almost identical a<sup>*</sup>b<sup>*</sup> is trivial. Usually in TCS context that goes by the moniker <em>pumping lemma.</em></p>
<p>So your &quot;programming assignment&quot;. here would be (say): <em>Write a python regexp that matches brackets.</em>  And of course the answer is <strong>NO CAN DO.</strong> The larger learning goal would be the appreciation of this classic <a href="https://stackoverflow.com/a/1732454/3700414">regexp to match html tags</a></p>
<h2>1.2 Subsume Syntax under Context Free Syntax</h2>
<p>In CFG:
If a language like C say is &quot;statically&quot; typed that means the type-system <strong>is syntax.</strong> So if it is syntax why is it not part of the CFG? Because while it is syntax its not <em>context free syntax</em>.</p>
<h2>1.3 Detect whether an arbitrary Turing machine will halt</h2>
<p>And of course the TM egs are most famous — You cant detect an infinite loop <strong>in the most general case.</strong>  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) <em>Why did your compiler not prove correctness?</em> If the student had a good grounding in TCS he would say: <em>Well respected Sir… There's is the  <a href="https://en.wikipedia.org/wiki/Rice%27s_theorem" rel="nofollow noreferrer">Rice theorem</a>…</em></p>
<h1>2. Universality Results</h1>
<p>These are fuzzier — more philosophic than scientific — than the above. And yet closer to the heartbeat of the field.</p>
<p>A colleague who was teaching TCS made the following insightful observation :</p>
<blockquote>
<p>CS is the conjunction of machines, computation, logic, languages and information theory. TCS should highlight these connections.</p>
</blockquote>
<p>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 <a href="https://en.wikipedia.org/wiki/Bit" rel="nofollow noreferrer">Bit</a>.</p>
<p>Some of these profoundly wide-ranging ideas...</p>
<ul>
<li>Church Turing thesis</li>
<li>The equivalence of <a href="https://en.wikipedia.org/wiki/Turing_completeness#Examples" rel="nofollow noreferrer">widely different formalisms</a></li>
<li>The relation of Turing-undecidability with Gödel-incompleteness with the lesser known <a href="http://qubd.github.io/files/TarskiUndefinability.pdf" rel="nofollow noreferrer">Tarski undefinability</a></li>
<li>The deep links of logic and computability...</li>
<li>...Going to the fact that Gödel is where it all starts, Turing is &quot;just&quot; an engineering improvement...</li>
<li>...To the <a href="https://en.wikipedia.org/wiki/Use%E2%80%93mention_distinction" rel="nofollow noreferrer">use-mention distinction</a> and why its central to CS.<br />
[I sometimes tickle my students with this &quot;proof&quot;:<br />
  Cat is a mammal.<br />
  Mammal is a a 6-letter-word.<br />
  Therefore cat is a 6 letter word<br />
]</li>
</ul>
<p>Perhaps mre recognizable in CS as the language-metalanguage distinction.</p>
<ul>
<li>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!]</li>
<li>The AI-TCS link. From Minsky back to Turing AI and CS has strong links. Coincidence?</li>
<li>The matching of the Chomsky hierarchy with the machine hierarchy. <a href="https://cis.temple.edu/%7Ebeigel/book/LOM.html" rel="nofollow noreferrer">Floyd Beigel</a> is good here.</li>
</ul>
<h3>Do you really cover all this?!</h3>
<p>As I said above its ok to lie </p>
<p>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.</p>
<h1>3. CS = Math</h1>
<p>Turing was a mathematician, as was Church, von Neumann, Babbage, Ada Lovelace, <a href="https://en.wikipedia.org/wiki/Stepped_reckoner" rel="nofollow noreferrer">Leibniz</a>, <a href="https://en.wikipedia.org/wiki/Pascal%27s_calculator" rel="nofollow noreferrer">Pascal</a>…  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!</p>
<p>In Turing's seminal paper &quot;a computer&quot; was a mathematician doing a computation that was so dumbed-down that it was mechanizable in principle.</p>
<p>Real computers made it so that that mechanizability goal would become practical as well</p>
<p>Unfortunately we've gone so far down that road that most of us find ourselves on the wrong side of <a href="https://www.cs.utexas.edu/users/EWD/transcriptions/EWD13xx/EWD1305.html" rel="nofollow noreferrer">Dijkstra's sneer</a>:</p>
<blockquote>
<p>And I don't need to waste my time with a computer just because I am a computer scientist.</p>
</blockquote>
<p>One long term goal of having undergone a successful TCS course is that the student – later computer scientist – be firmly placed in the <em>science</em> side. Else default to the <em>computer</em> side!</p>
<p>How far does programming in there help?<br />
Note that's not a rhetorical question!]</p>
<p>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.</p>
<p>If you want a programming-centered course that is directly and fully relevant to the aims of TCS look at Neil Jones' <a href="http://hjemmesider.diku.dk/%7Eneil/comp2book2007/book-whole.pdf" rel="nofollow noreferrer">Computability and Complexity from programming perspective</a>.<br />
Note: i am not <em>recommending</em> it! It's a monograph not a text and heavy going for the less than well-equipped and strongly motivated.</p>
<h3>More historical math-logic-CS-programming stuff</h3>
<p>[Yeah first three my writings...]</p>
<ul>
<li><a href="http://blog.languager.org/2015/03/cs-history-0.html" rel="nofollow noreferrer">CS Pre-history 0</a></li>
<li><a href="http://blog.languager.org/2015/07/cs-history-2.html" rel="nofollow noreferrer">CS Early History</a></li>
<li><a href="http://blog.languager.org/2015/04/cs-history-1.html" rel="nofollow noreferrer">Connections with Programming</a></li>
<li><a href="https://en.wikipedia.org/wiki/List_of_pioneers_in_computer_science" rel="nofollow noreferrer">CS-ist = Math-ician List</a></li>
</ul>
<h1>4. The Human Context</h1>
<p>Most of us accept that our modern world is largely based on something vaguely called &quot;science&quot;. Notice the overlap &quot;science&quot; and &quot;computer science&quot;?
And that this science is the creation of some remarkable individuals called &quot;scientists&quot;. Maybe we teachers have some role to play in producing the scientists of tomorrow?</p>
<h3>On the one hand...</h3>
<p>Look at the typical CS curriculum. How much science is there?</p>
<ul>
<li>Some &quot;surrounding&quot; subjects eg discrete math, statistics...</li>
<li>Some soft subjects eg management, economics...</li>
<li>a great deal of technology which is typically classified as &quot;core&quot;
eg programming in some fashionable langauge, databases and OS that showcase some technology and so on and so forth</li>
</ul>
<p>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.</p>
<h4>On the other...</h4>
<p>Beyond being CS-ists and teachers we're ultimately humans ...     Participating in inducting our students into the fold of responsible adults.</p>
<p>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:</p>
<p>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????</p>
<p>And computer technology is ever the servile hand-maiden of every world-destructive possibility</p>
<p>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.</p>
<p>To be able to do that the future generation needs to understand the nature of this technological insanity without losing their humanity.</p>
<p>From the standard CS curriculum, a well-directed TCS can be one of the key components to that humane sane understanding.</p>

CC BY-SA 4.0
2022-01-16T08:01:48.643Z
Amazing answer. Mind reformatting a bit your English so it’s easier to read. For example I’ve and not “ive” unless you have tried to imitate the style of a young student or something.
0x90
CC BY-SA 4.0
2022-01-16T08:46:59.690Z
Just hurriedly typed on less than convenient kb... Sorry ! Need a few hours... Editing certainly needed. Also want to add one more section
Rushi
CC BY-SA 4.0
2022-01-16T16:25:41.440Z
Ive done a first quick bunch of cleanups @0x90.  I'll run through it more fine tomorrow. And also expand last <to-be-filled> section
Rushi
CC BY-SA 4.0
2022-01-16T18:30:59.123Z
What's the source of that Dijkstra quote? It doesn't really sound like him. You know that he was an excellent programmer?
Victor Eijkhout
CC BY-SA 4.0
2022-01-16T19:35:10.183Z
*"Write a python regexp that matches brackets. And of course the answer is NO CAN DO."* Beware: what Python calls a regex is not really a regular expression in the theoretical sense, and [matching balanced parentheses is possible](https://stackoverflow.com/q/26385984/12299000) using Python's `regex` library, because it supports recursive patterns. Most programming languages have so-called regexes which support backreferences, if not recursion, so you can match e.g. `{a^nba^n | n in N}` with a so-called regex like `(a*)b\1`. So be *very* careful with setting regex homework involving real code.
kaya3
CC BY-SA 4.0
2022-01-17T02:45:05.577Z
Thanks for asking that  @VictorEijkhout — I had quoted that Dijkstra-aphorism slightly differently. I have amended it to match exactly the original and inserted the link to the source.  Which also contains the next line [*[Medical researchers are not required to suffer from the diseases they investigate.]* to amplify his point.  If you want to delve deeper into why he says this and from what angle see eg https://www.cs.utexas.edu/users/EWD/transcriptions/EWD10xx/EWD1012.html\  Dijkstra is of course always simultaneously bullseye and excessive 
Rushi
CC BY-SA 4.0
2022-01-17T02:47:01.833Z
Oooops @kaya3!! Good catch.  I guess one could replace that by some more classical re engine like egrep (But I wouldnt be surprised if even that has been enhanced beyond the regular domain...)
Rushi
CC BY-SA 4.0
2022-01-17T04:54:47.607Z
@Rusi I wonder what Dijkstra was referring to here. He has a famous statement that computer science is as much about computers as astronomy is about telescopes, but I don't think he is sneering here. Considering that these are answers to questions from the audience, and in view of the previous question, I wonder if he's only talking to the fact that he doesn't necessarily want to use a computer for doing presentations.
Victor Eijkhout
CC BY-SA 4.0
2022-01-17T05:23:59.223Z
These are two independent axes @VictorEijkhout. Yeah he didn't think it hip to over use technology such as computers-ppt etc.  But here the point is different. And quite key to much of his work --- teach programming as mathematics. ie instead of "running around with the program counter" grok the program in terms of predicates -- invariants, pre/post conditions etc.  This is what he calls (in staid language) operational approach vs postulational approach [here](https://www.cs.utexas.edu/users/EWD/transcriptions/EWD10xx/EWD1012.html). His characteristic hyperbolic  "Being a CSist vs computer"
Rushi
CC BY-SA 4.0
2022-01-17T05:24:37.333Z
There is a conundrum in dealing with Dijkstra's ideas is that (a) he espouses **imperative programming** (2) **Approached declaratively**  He switched from this contradiction end of his life https://www.cs.utexas.edu/users/EWD/transcriptions/OtherDocs/Haskell.html
Rushi
CC BY-SA 4.0
2022-01-16T04:53:59.707Z
2022-01-18T06:21:54.270Z
2022-01-18T06:21:54.270Z
Rushi
<p>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:</p>
<pre class="lang-scheme prettyprint-override"><code>(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)
 ...)

</code></pre>
<p>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 <em>just learned</em> functional programming and I want to expand on that skill), but their primary experience for years has been in Python and Java.</p>
<p>In particular, the stack-as-cons-boxes combined with nondeterminism is <em>really</em> 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.</p>
<p>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 <em>know</em> what (for instance) Sigma is, and our subsequent lessons in class reflect that fluidity.</p>
<p>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.</p>
<p>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 <em>must halt on its own</em> before the deadline!</p>
<p>While they must stick to the API for the Turing Machine, they are encouraged to think <em>extremely</em> 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.</p>
<p>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:</p>
<ul>
<li>number of states</li>
<li>cardinality of their chosen alphabet, and</li>
<li>the number of cells already written to the tape as input.</li>
</ul>
<p>(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)</p>
<p>The contest isn't a major part of their grade, just a few points for an attempt, and a <a href="https://rads.stackoverflow.com/amzn/click/com/B00AQY18UG" rel="nofollow noreferrer" rel="nofollow noreferrer">Rubber Duck Trophy</a> for the winner.</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>

CC BY-SA 4.0
2022-01-15T14:24:01.197Z
2022-01-15T14:47:25.833Z
2022-01-15T14:47:25.833Z
Ben I.
<p>In an introductory course on complexity and computing, I am thinking about including some programming tasks.</p>
<p>I wonder what types of tasks I could give the students beyond &quot;construct&quot; a Turing Machine in Python that determines whether a number <code>p</code> is prime.</p>
<p>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.</p>
<p>I would appreciate suggestions of tasks students might benefit from when implementing by hand in a modern programming language.</p>

<lesson-ideas><resource-request><undergraduate><complexity-theory><turing-machines>
Do you include coding assignments in an intro to complexity and computation course?
# Do you include coding assignments in an intro to complexity and computation course?

(Asked by: username_0 on 2022-01-15)

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.

**Tags:** lesson-ideas, resource-request, undergraduate, complexity-theory, turing-machines


---

## 4 answers

### Answer by username_3 on 2022-01-16. Score: 8

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](https://matheducators.stackexchange.com/questions/24549/combative-students-in-proofs-classes) 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 anbn

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](https://stackoverflow.com/a/1732454/3700414)

## 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](https://en.wikipedia.org/wiki/Rice%27s_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](https://en.wikipedia.org/wiki/Bit).

Some of these profoundly wide-ranging ideas...

* Church Turing thesis
* The equivalence of [widely different formalisms](https://en.wikipedia.org/wiki/Turing_completeness#Examples)
* The relation of Turing-undecidability with Gödel-incompleteness with the lesser known [Tarski undefinability](http://qubd.github.io/files/TarskiUndefinability.pdf)
* 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](https://en.wikipedia.org/wiki/Use%E2%80%93mention_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](https://cis.temple.edu/%7Ebeigel/book/LOM.html) 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](https://en.wikipedia.org/wiki/Stepped_reckoner), [Pascal](https://en.wikipedia.org/wiki/Pascal%27s_calculator)… 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](https://www.cs.utexas.edu/users/EWD/transcriptions/EWD13xx/EWD1305.html):

> 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](http://hjemmesider.diku.dk/%7Eneil/comp2book2007/book-whole.pdf).  
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](http://blog.languager.org/2015/03/cs-history-0.html)
* [CS Early History](http://blog.languager.org/2015/07/cs-history-2.html)
* [Connections with Programming](http://blog.languager.org/2015/04/cs-history-1.html)
* [CS-ist = Math-ician List](https://en.wikipedia.org/wiki/List_of_pioneers_in_computer_science)

# 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.

> **Comments:**
> **username_0**: Amazing answer. Mind reformatting a bit your English so it’s easier to read. For example I’ve and not “ive” unless you have tried to imitate the style of a young student or something.  
> **username_3**: Just hurriedly typed on less than convenient kb... Sorry ! Need a few hours... Editing certainly needed. Also want to add one more section  
> **username_3**: Ive done a first quick bunch of cleanups @username_0.  I'll run through it more fine tomorrow. And also expand last <to-be-filled> section  
> **username_1**: What's the source of that Dijkstra quote? It doesn't really sound like him. You know that he was an excellent programmer?  
> **username_4**: *"Write a python regexp that matches brackets. And of course the answer is NO CAN DO."* Beware: what Python calls a regex is not really a regular expression in the theoretical sense, and [matching balanced parentheses is possible](https://stackoverflow.com/q/26385984/12299000) using Python's `regex` library, because it supports recursive patterns. Most programming languages have so-called regexes which support backreferences, if not recursion, so you can match e.g. `{a^nba^n | n in N}` with a so-called regex like `(a*)b\1`. So be *very* careful with setting regex homework involving real code.  
> **username_3**: Thanks for asking that  @VictorEijkhout — I had quoted that Dijkstra-aphorism slightly differently. I have amended it to match exactly the original and inserted the link to the source.  Which also contains the next line [*[Medical researchers are not required to suffer from the diseases they investigate.]* to amplify his point.  If you want to delve deeper into why he says this and from what angle see eg https://www.cs.utexas.edu/users/EWD/transcriptions/EWD10xx/EWD1012.html\  Dijkstra is of course always simultaneously bullseye and excessive   
> **username_3**: Oooops @username_4!! Good catch.  I guess one could replace that by some more classical re engine like egrep (But I wouldnt be surprised if even that has been enhanced beyond the regular domain...)  
> **username_1**: @Rusi I wonder what Dijkstra was referring to here. He has a famous statement that computer science is as much about computers as astronomy is about telescopes, but I don't think he is sneering here. Considering that these are answers to questions from the audience, and in view of the previous question, I wonder if he's only talking to the fact that he doesn't necessarily want to use a computer for doing presentations.  
> **username_3**: These are two independent axes @VictorEijkhout. Yeah he didn't think it hip to over use technology such as computers-ppt etc.  But here the point is different. And quite key to much of his work --- teach programming as mathematics. ie instead of "running around with the program counter" grok the program in terms of predicates -- invariants, pre/post conditions etc.  This is what he calls (in staid language) operational approach vs postulational approach [here](https://www.cs.utexas.edu/users/EWD/transcriptions/EWD10xx/EWD1012.html). His characteristic hyperbolic  "Being a CSist vs computer"  
> **username_3**: There is a conundrum in dealing with Dijkstra's ideas is that (a) he espouses **imperative programming** (2) **Approached declaratively**  He switched from this contradiction end of his life https://www.cs.utexas.edu/users/EWD/transcriptions/OtherDocs/Haskell.html  

---

### Answer by username_5 on 2022-01-15. Score: 4

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 by username_1 on 2022-01-15. Score: 2

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 by username_2 on 2022-01-16. Score: 1

**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](https://www.youtube.com/watch?v=kPRA0W1kECg&ab_channel=TimoBingmann)

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.


---

