Field Reports tell how instructors have used AVs in their teaching.

Teaching the universal Turing machine

1 reply [Last post]
pilucrescenzi
pilucrescenzi's picture
Offline
White BeltYellow BeltGreen BeltRed BeltBlack Belt
Joined: 2009-06-08
Posts:
Points: 161
Instructor(s): 
Pilu Crescenzi
Location: 
University of Florence
Course: 
Theoretical Computer Science: Languages, Computability, Complexity
Term / Date: 
First semester 2006 and 2007
AVs used: 

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 first 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.

shaffer
shaffer's picture
Offline
White BeltYellow BeltGreen BeltRed BeltBlack Belt
Joined: 2009-05-28
Posts:
Points: 2019
Re: Teaching the universal Turing machine
That is very interesting! So, given appropriate support, students seem to buy into learning about Turing machines by writing something for them. While doing that makes sense to me, I wasn’t sure how well the students would like it.