<p>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.  </p>

<p>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 <em>encoding</em> and <em>decoding</em> simple Turing Machines.</p>

<p>Some particular traps for my students have been: </p>

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

<p>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.</p>

CC BY-SA 3.0
2017-05-23T19:49:48.797Z
2017-10-08T17:20:00.970Z
2017-10-08T17:20:00.970Z
Ben I.
<p>In a course about Fundamental Computer Science, which includes Turing Machines,<br>
how many questions like "Construct a Turing Machine that does X" should I include?</p>

<p>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:</p>

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

<p>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.</p>

<p>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. </p>

CC BY-SA 3.0
2017-07-01T16:17:17.807Z
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
<turing-machines>
In a course about Turing machines, how many questions like "Construct a Turing Machine that does X" should I include?
# In a course about Turing machines, how many questions like "Construct a Turing Machine that does X" should I include?

(Asked by: username_0 on 2017-05-23)

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.

**Tags:** turing-machines

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2017-05-23. Score: 5

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.


---

