In a course about Turing machines, how many questions like "Construct a Turing Machine that does X" should I include?

Question

In a course about Fundamental Computer Science, which includes Turing Machines,
how many questions like "Construct a Turing Machine that does X" should I include?

There should be at least a few basic constructions, like doubling a string of ones or checking whether a number is even, checking whether one number is larger than another, to show how a Turing Machine works. However, I'm unsure whether to include more difficult problems, like:

• Given two positive integers, check whether one is divisble by the other.
• Given a positive integer $n$, check whether $n$ is prime.
• Given a positive integer $n$, compute the $n$th Fibonnaci number.
• Given two positive integers $m,n$, calculate $m^n$.

Also, should I just allow the blank symbol and one other symbol or should I allow any number of symbols? Or maybe a mix. The difficulty will largely depend on this.

Students learn thinking abstractly about these problems. However, this abstract thinking is different from the abstract thinking that is used in most programming activities, so I'm unsure.

Answer 1

I integrate many, many simple TMs into both my lecture and as homework. I also force them to use descriptors such as $\vdash$ and $\vdash^*$ on their machines. I've found that it takes a long time for students to get used to basic operations.

They have no problem converting a given TM to its tuple members ($\delta$, $\Gamma$, $\Sigma$, etc.), but have surprising trouble seeing the performance implications of transitions on machines that I provide to them. With practice, they get much better at this, but it takes (in my experience) a surprising amount of practice, both in encoding and decoding simple Turing Machines.

Some particular traps for my students have been:

• navigating halting states (since they cannot transition outwards)
• identifying ending conditions of loops
• making comparisons between two strings stored on different parts of the tape
• learning when it is appropriate to overwrite your data.

All of these take practice. I do this in-class so that I can assist and guide, but I also have many hours of facetime with my students. In a more constrained timeline, I would give out homework assignments instead.