How many Paper Towns have you found so far?

So far, I found eight Paper Towns. Here are their Turing Machine Numbers:

155; 315; 347; 619; 699; 1,259; 1,387; and 2,795.

I leave it as a homework assignmnent for you to convert these eight Turing Machine Numbers into Turing Machines, so that you can see what they really look like. All you have to do is run the Notation Converter (which you can download from this website) and convert these eight Denary Numbers into Machine State Notation.

---

The first Paper Town that I found is the one with Turing Machine Number 699. I stumbled upon it by accident when I was preparing a Help Video for the Notation Converter.

As soon as found this one, I easily guessed at three additional Paper Towns. Their Turing Machine Numbers are:

315; 1,259; and 2,795.

For a long time, as I was developing this website, these were the only four Turing Machines that I knew. I even composed a separate FAQ in which I went into more details about these four Turing Machines.

---

Then, about a year later, an idea popped into my head, and I decided to try it. Lo and behold, I found four more Paper Towns! Here are their Turing Machine Numbers:

155; 347; 619; and 1,387.

When I discovered these four new Paper Towns, I wondered why I didn't think of them sooner. After all, they are very similar to the first four Paper Towns that I found.

However, there is a difference here that may have prevented me from originally considering them.

The first four Turing Machine that I found can be shown to be Paper Towns regardless of what data they work on. In other words, regardless of what data you provide, the Turing Machine will work correctly as expected, but the Universal Turing Machine simulation of it will fail.

However, with these four new Paper Towns, there is a condition on what kind of data they can work with. The condition on the data may be stated as follows:

The first 1 that appears in the data must be immediately followed by a 0.

For example, if the data that you provide to any of these four new Paper Towns is 1 0 then the Turing Machine will run just fine, but the Universal Turing Machine simulation of it will fail. That's what makes it a Paper Town.

However, if the data you provide is 1 1 then the Turing Machine will fail. In that case, who cares if the Universal Turing Machine simulation of it fails or not?

So, these happen to be Turing Machines that come with conditions on the data that they can work with. Is that ok?

Well, after thinking about if for a while, I had to answer "Yes! Of course it's ok." After all, the Turing Machines composed by Sir Roger Penrose also come with conditions on the data. For example, Penrose's EUC Turing Machine expects the data to be two Unary Numbers separated by one or more zeros. If you provide it with only one Unary Number, then it will fail because it'll run forever.

The only way that anyone can show that EUC is a Paper Town is to come up with two Unary Numbers separated by one or more zeros for which the EUC Turing Machine works correctly, but the Universal Turing Machine simulation of it, with the same data, fails.

---

Those of you who completed the Homework Assignment at the beginning of this FAQ may have noticed that each one of those eight Turing Machines include the instruction 00STOP or 01STOP.

That is an excellent observation! I'm glad you noticed it!

Furthermore, some of you that made that observation may now be asking:

How about if, in those eight Turing Machines, you replaced each 00STOP with 10STOP, and replaced each 01STOP with 11STOP. Wouldn't that give you another eight Paper Towns, for a total of sixteen Paper Towns?

That is a very good question. It is a question that I myself thought about for a while, and then decided not to include them in the list of Paper Towns.

The reason is, that instructions such as 10STOP and 11STOP are examples of instructions that have something that I decided to call the Non-Zero Ignored Stop State.

After thinking some more about it, I felt that perhaps the Universal Turing Machine was never designed to simulate Turing Machines that had Non-Zero Ignored Stop States.

In fact, I was able to find a Turing Machine with a Non-Zero Ignored Stop State that the Universal Turing Machine is not able to simulate. It is the Turing Machine whose Turing Machine Number is 1,418,730. If you use the Notation Converter to see what this Turing Machine looks like, you'll see that it is identical to Sir Roger Penrose's UN+1 Turing Machine, except that the instruction 01STOP was replaced by 101STOP.

(As a homework assignment, you can check to make sure that everything I wrote in the previous paragraph is true.)

I don't think there is any good reason for ever using a STOP instruction with a Non-Zero Ignored Stop State, in place of 00STOP or 01STOP. For that reason, I suspect that the Universal Turing Machine was just not designed to handle Turing Machines with Non-Zero Ignored Stop States.

---

---

---

Most Turing Machines have infinitely many Turing Machine Numbers.

(In fact, there are only two good Turing Machines that don't have infinitely many Turing Machine Numbers.)

The way that you can generate infinitely many Turing Machine Numbers for the same Turing Machine is by inserting Optional Leading Zeros into the Turing Machine Number. In case you're not sure what we're talking about, there is an FAQ which explains what an Optional Leading Zero is and another FAQ that shows you how you can generate another Turing Machine Number for the same Turing Machine by inserting Optional Leading Zeros.

When you generate another Turing Machine Number by inserting an Optional Leading Zero, the Universal Turing Machine may or may not be able to simulate the Turing Machine correctly.

---

For example, the UN+1 Turing Machine composed by Sir Roger Penrose has Turing Machine Number 177,642. If you provide this number (in binary) to the Universal Turing Machine, then it will work just fine.

The number 353,770 is also a Turing Machine Number for UN+1. It was derived from the number 177,642 by inserting an Optional Leading Zero. If you provide this number (in binary) to the Universal Turing Machine, then it will also work just fine.

The number 355,274 is also a Turing Machine Number for UN+1. It was also derived from the number 177,642 by inserting an Optional Leading Zero, but in a different place. However, the Universal Turing Machine will fail if you provide it with this number. (As a homework assignment try this yourself. When asked what data it will work on, give it the same data that Sir Roger Penrose used in his book: 0 0 0 0 0 1 1 1 1 0 0 0 0 0. You'll see that it eventually goes into an infinite loop of 11 steps, each time moving further to the left, until the Excel file runs out of columns).

---

---

---

To summarize, if we do not consider any Turing Machine Numbers that contain Optional Leading Zeros, nor if we allow any Turing Machines that have Non-Zero Ignored Stop States, then I am aware of only eight Paper Towns, and their Turing Machine Numbers are at the beginning of this web page.

If you like, you are welcome to search for other good Turing Machines that are also Paper Towns. If you find another one, I think it would be a great idea for you to present it in your own website or YouTube video. I think there would be those who would be interested in that.

Better yet, if you could figure out how the Universal Turing Machine works, then that would be the best way to discover all of the Paper Towns. That would certainly give you the right to brag about it in a website or YouTube video of your own.