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

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.

• These sort of constrained problems can be great seminar and assignment submission, but I'd caution you against assigning too many of these sort of problems in the context of a time-pressured exam. You'll filter not for those who are able to do this sort of abstract thinking, but for those who happen to see the solution more quickly and those who are less 'anxious' about solving problems under pressure. – Adam Williams Jul 1 '17 at 16:17

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.