# Teaching the universal Turing machine

The goal of these lectures (6 hours in 2006 and 3 hours in 2007) was to teach the students how to fully construct a universal Turing machine `U`

and to show them that this machine does not exist only *in theory*. In 2006, I used a Turing machine simulator, called **Enjgma**, that I developed during the summer 2006, while in 2007 I used **JFLAP** (the reason why I used Enjgma in 2006 is that, if I am not wrong, the JFLAP block feature was not available at that time). In 2006 I decided to be very *tough*: indeed, `U`

was a one-tape machine with a binary working alphabet (plus the blank symbol). At the end of the course, I asked the students whether they agreed with the following two statements.

- It is didactically useful to build the universal Turing machine from the beginning to the end.
- It is didactically useful to work with one-tape Turing machines.

Of 25 students, 2 completely disagreed with the ﬁrst statement, 15 disagreed, 7 agreed, and 1 completely agreed, while 1 student disagreed with the second statement, 13 agreed, and 11 fully agreed. I then decided in 2007 to make the construction of `U`

much easier: indeed, `U`

was a 3-tape machine with a working alphabet containing 9 symbols (plus the blank symbol). The description of this machine is contained in the Italian lecture notes, which are downloadable from the website: the JFLAP implementation is attached to this report. At the end of the course, I asked again the students whether they agreed with the following statement.

- It is didactically useful to build the universal Turing machine from the beginning to the end.

Of 20 students, 1 completely disagreed with the above statement, 7 disagreed, and 12 agreed. It then seems that making the universal machine easier increased its didactic usefulness, at least in the students' opinion. Personally, I am still convinced that teaching the universal Turing machine in this *constructivist* way is a very interesting exercise, since it really shows the power of this simple computation model. This year I have been on sabbatical and, hence, I did not teach the computability course: I will teach it again next semester and I think I will still show the students how to build the universal Turing machine (by using JFLAP). P.S. At the end of the two courses I also asked the students whether they agreed with the following statement.

- A computability theory course has to use a Turing machine simulator.

In 2006, of 25 students, 2 students disagreed with the above statement, 13 agreed, and 10 fully agreed, while in 2007, of 20 students, 9 agreed and 11 fully agreed.