Is there a one-to-one correspondence between the positive integers and all Turing Machines?

---

Yes, there is, but maybe not in the way you may think.

If you are thinking that the one-to-one correspondence can be achieved by associating each Turing Machine with its Turing Machine Number, then you are mistaken.

---

First of all, not every positive integer can be a Turing Machine Number. For example, any number that has five or more consecutive 1's when written in Binary Notation cannot be a Turing Machine Number. To see why, just take a look at the procedure to convert a Turing Machine into a Turing Machine Number. That procedure can be found on the web page that answered the question How do I figure out the Turing Machine Number? When following that procedure, you replace "STOP" with "11110" which gives you four consecutive 1's; you also replace "L" with "1110" which gives you three consecutive 1's; etc. But, there is no replacement of anything that can give you five or more consecutive 1's.

Also, any number whose three least sigificant digits (when written in Binary Notation) are "111" cannot be a Turing Machine Number. Why this is true becomes clear when you look at the procedure to convert a Turing Machine Number into a Turing Machine. That procedure can be found on the web page that answered the question How do I convert a Turing Machine Number into a Turing Machine? In Step 2 of that nine-step procedure, you append "110" at the end of your number, and then your binary number ends in "111110" so that it has five consecutive 1's, and you won't be able to convert the resulting number into a Turing Machine.

However, as long as the binary number does not have five consecutive 1's, and as long as it does not end in three consecutive 1's, then it can be a Turing Machine Number and can be converted into a Turing Machine. The Turing Machine may be a good Turing Machine, or it may be a bad Turing Machine, but it will be a Turing Machine. An example of a bad Turing Machine is one that does not have a STOP instruction and therefore just runs forever. Another example can be one that executes an instruction that tells it to move to a non-existent state, and then crashes.

---

Secondly, a Turing Machine can have more than one Turing Machine Number. To see why that can happen, take a look at the procedure to convert a Turing Machine into a Turing Machine Number. That procedure can be found on the web page that answered the question How do I figure out the Turing Machine Number? In Step 4 of that procedure, you are told to remove any leading zeros from the strings of 1's and 0's that you have thus far. However, if you skip this optional step, or better yet, if you insert one or more leading zeros to any of the strings, then you'll eventually end up with a bigger Turing Machine Number. And then, of course, if you convert this bigger number back into a Turing Machine, you'll end up with the same Turing Machine again!

In fact, when you think about it, every Turing Machine has infinitely many Turing Machine Numbers!

By the way, just in case you're wondering about this, the Notation Converter Excel file (that you can download from the Home page) will always convert a Turing Machine to its smallest possible Turing Machine Number.

---

Ok. It's clear that there are infintely many Turing Machine Numbers. But, are there infinitely many different Turing Machines?

---

On page 54 of his book The Emperor's New Mind (Oxford University Press, 1989), Sir Roger Penrose constructed a Turing Machine that he called UN+1. What it does is add 1 to a number on the tape (in Unary Notation) and display the answer on the tape (also in Unary Notation).

As an exercise, you can use the Turing Machine Excel file (that you can download from the Home page) to build a Turing Machine that you can call UN+2. What it should do is add 2 to a number on the tape (in Unary Notation) and display the answer on the tape (also in Unary Notation).

Then, as additional exercises, you can similarly build Turing Machines that you can call UN+3, UN+4, UN+5, etc. Certainly, there are infinitely many of these kinds of Turing Machines, and they're all different.

But, even beyond these examples, there are infinitely many different Turing Machines. In fact, as long as you can describe an algorithm for computing any particular number, you can build a Turing Machine to do it.

---

Ok. So, there are infinitely many different Turing Machines, and each Turing Machine has infinitely many Turing Machine Numbers, yet not every positive integer is a Turing Machine Number. So, how can we set up a one-to-one correspondence between the positive integers and all of the Turing Machines.

---

There are probably many different ways to do this. Here is one way:

On page 70 of his book, Sir Roger Penrose suggests naming all Turing Machines as T₀, T₁, T₂, T₃, etc., where the n is the Turing Machine Number of Turing Machine T_n. So, let's build a list of these Turing Machines while at the same time keeping track of each Turing Machine's position in the list.

And now we're stuck! The problem is that Turing Machine T₇ would have Turing Machine Number 7, but 7 written as a binary number is 111, and earlier (on this web page) we saw that any binary number that ends in 111 cannot be a Turing Machine Number. So, there is no Turing Machine such as T₇!

So, what do we do about this? We just skip it, and continue our list as follows:

And now we're stuck again! We would like to say that our 12th Turing Machine is T₁₂, but Turing Machine Number 12 converts to a Turing Machine with instructions 00R 00R 00R, and we already have that Turing Machine on our list! It's T₆ and it's the 7th one on our list.

If we are to have a one-to-one correspondence between the positive integers and Turing Machines, then we can't have any duplicate Turing Machines on the list. So, what do we do about this? We just skip it, and continue our list as follows:

And so, we can just continue this list, skipping over any T_n for which n is not a Turing Machine Number, or if that Turing Machine is already on the list, and we can see the one-to-one correspondence between the positive integers and all Turing Machines.

---

Ok. But how do we know that this list will have every single Turing Machine?

---

Every Turing Machine can be converted to a Turing Machine Number. If that number is n, then the name of that Turing Machine is T_n, so as we're building our list, sooner or later it will be placed on the list.

---

Ok. But, in listing just the first 15 Turing Machines on the list, we already skipped over T₇, T₁₂, and T₁₅. How do we know that after a certain time, we won't be skipping over every T_n for some reason or other, and thus end up with only a finite list?

---

Earlier (on this web page), we observed that there are infinitely many different Turing Machines. We also observed that every Turing Machine must, sooner or later, be placed on the list. So, this list must be infinitely long.