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.

  • $\begingroup$ 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. $\endgroup$ – 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.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.