What is the Ignored Stop State?

If you had already read the FAQ How can I interpret instructions in the Penrose Turing Machine?, then you know that:

Every "instruction" (or Transition Function) in a Penrose Turing Machine is of the form mnD where m consists of one or more binary digits (0's and 1's); n is just a single binary digit (0 or 1); and D is one of the following: R, L, or STOP.

For example:

For 00R, m = 0, n = 0, D = R.

For 10001L, m = 1000, n = 1, D = L.

For 01STOP, m = 0, n = 1, and D = STOP.

For 10101R, m = 1010, n = 1, and D = R.

In each of the above examples, the m is always the State that the Turing Machine goes to after it finishes executing the instruction. The n is the digit (0 or 1) that the Turing Machine writes to the tape before it moves Right, Left, or moves one cell to the right and Stops.

However, in those cases when D = STOP, the m is always ignored. It is this m that I decided to call the Ignored Stop State.

For example:

For 10STOP, the Turing Machine writes a 0 to the tape, moves one cell to the right and the Turing Machine stops running. The 1 at the very beginning of the instruction is ignored.

For 10001STOP, the Turing Machine writes a 1 to the tape, moves one cell to the right and the Turing Machine stops running. The 1000 at the very beginning of the instruction is ignored.

---

I noticed that in all of the examples Sir Roger Penrose composed for his book, the STOP instruction was always either 00STOP or 01STOP. He never used a non-zero Ignored Stop State. When I noticed this, my initial reaction was "Well, sure. Why not. That zero at the beginning of the instruction will be ignored anyway, so why not zero. Besides, any other number there would just make a bigger Turing Machine Number, so I guess it makes sense to use zero."

Later, when I did lots of experimenting with various Turing Machines in an effort to find out how the Universal Turing Machine works, I thought of a much stronger reason to avoid using any non-zero Ignored Stop States. Perhaps the Universal Turing Machine was not designed to handle Turing Machines with non-zero Ignored Stop States?

---

Guess what! I have a fun homework assignment for you!
Let's figure out what the Turing Machine looks like whose Turing Machine Number is 1,418,730.
In case you've never done this sort of thing before, let me walk you through it step by step.

Homework #1

Step 1: Download the Notation Converter Excel file from the Home Page of this website. It's the second Excel file that you can download.

Step 2: With the Excel file open to the Welcome Sheet, click on the picture.

Step 3: When it asks From which numerical notation will you be converting your number? click Denary.

Step 4: When it asks What Denary number shall we use? click I will provide my own number.

Step 5: When it asks How will you provide your Denary number? click I'd just like to type it in.

Step 6: Here is where you type in the Turing Machine Number: 1,418,730. To do so, first click on the yellow cell in row 5 that's all the way on the left. Then, type in the digits 1 4 1 8 7 3 0, typing only one digit per cell, and hitting Enter after each digit. When you're done, click Done.

Step 7: When you see So Far So Good! click OK.

Step 8: When you see Well Done! click OK.

Well, there you have it! The instructions for your Turing Machine are in rows 16 and 17.

If you're really observant, then you'll notice that this Turing Machine is very similar to Sir Roger Penrose's UN+1 Turing Machine. The only difference is that instead of the instruction 01STOP that's in the UN+1 Turing Machine, this one has 101STOP instead.

So, what we have here is an example of a Turing Machine with a non-zero Ignored Stop State.

Notice also that in row 7 we have the number 1,418,730 in Binary Notation. We'll need this for the next two homework assignments.

Ok. When you're done looking at and admiring what you just did, make sure you close and save this Excel file somewhere on your computer. You'll need it for the next two homework assignments.

---

Wasn't that fun? Let's go ahead and do another homework assignment.

This time, let's simulate the Turing Machine you were just looking at with the Universal Turing Machine. When it comes to providing the data to be used by this Turing Machine, let's use the same data that Sir Roger Penrose used in his book when he explained his Turing Machine UN+1. It's the number 4 written in Unary Notation.

The data that Penrose used is 0 0 0 0 0 1 1 1 1 0 0 0 0 0.

In case you've never done this sort of thing before, let me walk you through it step by step.

Homework #2

Step 1: Download the Turing Machine Excel file from the Home Page of this website. It's the first Excel file that you can download.

Step 2: With the Excel file open to the Welcome Sheet, click on the picture.

Step 3: When it asks Which Turing Machine shall we use? click Example from the book "The Emperor's New Mind".

Step 4: When it asks Which Turing Machine Example from the "The Emperor's New Mind" would you like to use? click The Universal Turing Machine.

Step 5: When it asks ARE YOU SURE?? click YES !

Step 6: When it asks What Turing Machine shall the Universal Turing Machine imitate? click I will provide my own Turing Machine.

Step 7: When it asks How will you provide the Binary Number of the Turing Machine that the Universal Turing Machine will emulate? click From another Excel workbook.

Step 8: Here is where you select the Excel workbook that you used when you did Homework #1.
After you select your Excel workbook, open it to the sheet where you did your work. Then click on row 7 (because that's the row that has the Turing Machine Number in Binary) and then click OK.
Just follow the directions on the screen and you'll do fine.

Step 9: When it asks How will you provide the data for your Turing Machine? click I'd just like to type it in.

Step 10: Here is where you type in the data. To do so, first click on the yellow cell in row 12 that's all the way on the left.
Then, type in the digits 0 0 0 0 0 1 1 1 1 0 0 0 0 0, typing only one digit per cell, and hitting Enter after each digit. When you're done, click Done.

Step 11: You have just finished building your Turing Machine and now ready to run it. In the blank rectangle that you see, type 20,000 steps at a time.
Then, click Click to Run.

When it finishes, click Change Settings.
Then, click 1 step at a time, then click Show recorded history?, and then click Go.

Step 12: Click Go several times, and observe what is happening.

Notice that the Universal Turing Machine got itself into an infinite loop and it's executing the same instruction over and over again, and each time it does so, it moves one cell further to the left. Since the theoretical Turing Machine has a paper tape that's infinitely long, it'll keep doing this forever and ever and will never finish.

Of course, an Excel file only has a finite number of columns, so eventually it'll run out of columns and you'll see a message telling you that this Excel file cannot handle your Turing Machine.

You can go ahead and click Go several more times if you like, and when you get bored, you can just click Stop.

---

Wasn't that exciting? Let's go ahead and do another homework assignment.

This time, let's do Homework #2 all over again, except this time, instead of using the data that Sir Roger Penrose used, let's just use the number 1. Also, let's not put in any leading or trailing zeros.

So, the data that we'll use this time is just 1.

In case you've never done this sort of thing before, let me walk you through it step by step.

Homework #3

Steps 1 through 9 are exactly the same as in Homework #2.

Step 10: Here is where you type in the data. To do so, first click on the yellow cell in row 12 that's all the way on the left. Then, just type in the digit 1, hit Enter, and then click Done.

Steps 11 and 12 are exactly the same as in Homework #2.

Now, if you are as observant as I hope you are, then you noticed that the Universal Turing Machine got itself into an infinite loop consisting of eleven steps, and it's executing them over and over again, and each time it goes through this loop, it's further to the left by one more cell than it was before.

So, this time it'll also run forever and ever and never finish. Actually, you'll just get a message that this Excel file cannot handle your Turing Machine, just like in Homework #2, but this time it may take longer to get there.
You can go ahead and click Go several more times if you like, and when you get bored, you can just click Stop.

---

Well, what do you think? Isn't that interesting?

It makes you wish you understood how the Universal Turing Machine really works, doesn't it? Well, at least that's the wish that I have right now.

You know what! If you happen to be smart enough to figure out how the Universal Turing Machine works, how about if you explain it in a YouTube video or your own website.

I think that would be just great! Don't you?