The Turing Machine Program

The program that you will be working with today was demonstrated in class on Wednesday. It runs in your web browser and can be found here:

http://math.hws.edu/eck/js/turing-machine/TM.html

There is a link on the top of the page to brief Info and Instructions about the program. Mostly, it's reasonably intuitive. Hopefully, you learned enough from the demo on Wednesday to use the program.

It would be a good idea for you to spend some time familiarizing yourself with the program. Try some of the sample machines, and try giving them different inputs to run on. Use the step button to do a computation one step at a time. Click the "New Turing Machine" button, and try to add some rules. Note that if a TM gets into a situation for which it doesn't have a rule, it will stop. At that point, you can define the needed rule, and resume the execution. There is also a "Step Back" button that moves backward through the computation. This can be very useful when you are trying to debug a problem.

Some other remarks: As long as the machine is not running, you can drag the machine on its tape. You can also drag the tape back and forth, taking the machine with it. You can click on the machine and type in a new state number. You can click one of the cells of the tape and type legal symbols onto the tape. If you click inside the rule table, on the value of a "New Symbol", "New State", or "Move", you can type in a new value. But to make a new rule, with a new "Old State" and "Old Symbol", you have to use the Rule Editor. Just select the desired properties for the rule from the popup menus. Finally, note that there is an Undo button and a Redo button to the left of the rules table.

Saving and Turning in your Work

I would like to be able to run your machines. (Except for very trivial machines, it's difficult to tell what the machine will do by looking at the rule table). You might also want to be able to save partially completed work so that you can return to it later. The Turing Machine program runs in a web browser and can't save your work to a file. However, it does have a way of exporting your work.

Click the botton labeled "Show Import/Export," on the bottom left. You will see a popup that can be used to save and reload TM specifications (or even to hand-edit them). One of the buttons in that popup is named "Grab Current Example." It shows the specification for the current machine and tape. Here is what it looks like for the "Binary Increment" example machine:

To save your work, use "Show Input/Export" and "Grab Current Example". Select all of the text in the text box, and you paste it into a plain text file, which you can save as usual. It is essential to copy the entire text, including the braces at the beginning and the end.

When you want to reload your work into the program, go to the program on the web, click "Show Import/Export." Open the text file and select the TM specification. Copy it, and paste it into the text area in the "Show Import/Export" popup. Click "Apply." Your machine will be loaded into the program, just as it was when you saved it.

To submit your work for this lab, create a plain text file named "TM.txt". For each of the exercises that ask you to create a Turing machine, copy and paste the specification for your machine from the "Show Import/Export" popup into the text file. Label it clearlyk. For the exercises that have written responses, type your answers into the same file.

Submit your file by copying it into your folder inside /homework/cs229/homework on the file server. Please use the correct name for the file, TM.txt! (If you can't figure out how to do that, you could also email your file to me.) I will need the file, not a print out, so that I can copy-and-paste your machines into the program for testing.

Exercise 1: Looking for $'s

This is a small exercise to help you get used to working with the Turing machine simulator.

In class, we looked at a simple example of a Turing machine that moves to the right searching for two $'s in a row. When (and if) it encounters them, it halts, and the machine is left on the second $

Create such a Turing machine in the simulator. You can assume that the tape contains only a's, b's, blanks, and $'s.

This can be done using two states (in addition to the halt state), if you use the "stay" option (S) as a direction of motion at the end. Without that option, it requires 3 states to put the machine in the proper position at the end. If you use the "other" and "same" options for "Old Symbol" and "New Symbol" in some of your rules, you can do this with just four or five lines in the rule table.

Exercise 2: A Regular Problem

Create a Turing machine that checks whether the number of a's in a string of a's and b's is a multiple of 3. The input is a string of a's and b's, with the machine positioned on one end of the string. The output of the computation should be 1 if the number of a's is a multiple of 3, and should be 0 if the number is not a multiple of 3. (That is, the only thing left on the tape should be a 0 or 1, and the machine should be positioned on that 0 or 1.)

Exercise 3: Regular Languages

This is a written exercise. The Turing machine in the previous problem "decides" the regular language { w ∈ {a,b}^* | the number of a's in w is a multiple of 3 }. Given any regular language L, explain how to make a Turing machine that decides the language L. That is, explain why every regular language is Turing-decidable.

Exercise 4: Binary To Unary

The representation of a natural number n as the string aⁿ is called the "unary" representation, since an a in the string counts as 1, no matter where it it is in the string. In class, I claimed that it is possible for a Turing machine to convert a number n represented in binary into its unary equivalent. You should make a Turing machine to do that. That is, if the machine is run with the binary representation of n as its input, it should halt with a string of n a's on the tape. To conform with our defintion of computing a function, the machine should end up on the right end of the string of a's, and the a's should be the only thing on the tape.

As a starting point, you can use the following machine, which decrements a binary number. That is, if it is started on the rightmost digit of a binary number, it will subtract one from that number. As a special case, if it is asked to subtract 1 from 0, it will erase the input and halt. You can import the machine into the Turing machine simulator using the "Show Import/Export" button as described above. Copy and paste this specification from this web page into the "Show Import/Export" popup, and click "Apply":

{
   "name": "Decrement",
   "max_state": 25,
   "symbols": "xyzabc01$@",
   "tape": "1011",
   "position": 3,
   "rules": [
      [ 0, "#", "#", 2, "R" ],
      [ 0, "0", "1", 0, "L" ],
      [ 0, "1", "0", 1, "R" ],
      [ 1, "#", "#", "h", "L" ],
      [ 1, "0", "0", 1, "R" ],
      [ 1, "1", "1", 1, "R" ],
      [ 2, "#", "#", "h", "L" ],
      [ 2, "1", "#", 2, "R" ]
   ]
}

The idea for the machine is that it should make a string of a's to the right of the binary number. Every time it subtracts 1 from the number, it should add an a to the string (instead of halting). When the number reaches 0, the string of a's is complete.

Exercise 5: Divisibility

Create a Turing machine that does the following: The input will be two strings of a's, separated by a space, such as

aaaa aaaaaaaaaaaaaaaaaaaaaaa

The strings represent two numbers, D and N, in "unary" notations. That is, the first string contains D a's and the second string contains N a's. Your goal is to test whether N is evenly divisible by D, or, equivalently, whether N is a multiple of D. If N is divisible by D, halt with output 1. If N is not divisible by D, halt with output 0. You can start the machine anywhere you find most convenient. (The left end of D is a reasonable choice.)

As a hint, you can basically subtract D from N by erasing one a from N for each a in D. If you repeat that process over and over, you will eventually run out of a's in the string on the right. If that happens at the end of erasing a group of a's, then N was divisible by D. If it happens in the middle of erasing a group of a's, then N was not divisible by D.

This is a challenging problem! Do some planning before you start. Ask for help and advice. I was able to do it with a Turing Machine that has 12 states (plus the halt state).

Exercise 6: Prime Numbers

This is a written exercise. You are not going to create an actual machine for this one!

Discuss how a Turing machine could be constructed that can test a number to determine whether that number is prime. A number N is prime is N is not evenly divisible for any integer D in the range from 2 to N-1. The number N can be provided as a string of N a's on the tape. The machine from the previous exercise could be part of the solution. You will probably also need a machine that can make a copy of a string of a's, as well as a machine for comparing the length of two strings of a's.

Exercise 7: Computability

"Anything that can be computed can be computed by a Turing Machine." This is one way of phrasing the Church-Turing Thesis. This is not something that can be proved or disproved mathematically. Given your experience with the Turing machine simulator and the material covered in class and in the textbook, what do think about this thesis? Do you believe it? Why or why not? Do you think it is useful or interesting? (Write a couple of paragraphs in response.)