What happened after the invention of the Turing Machine?
At about the same time that Alonzo Church and Alan Turing were thinking about resolving the Entscheidungsproblem, there was another mathematician, Emil Post, who, independently of Church and Turing, was doing the same thing. He also came up with the idea of a machine, similar to that of Turing, except that instead of writing symbols on an infinitely long paper tape, Post envisioned an infinitely long line of boxes and his machine would either mark a box with a "1" or erase the mark. There were other similarities between his machine and Turing's, but there were also significant differences.
Emil Post described his machine in a paper with the title "Finite Combinatory Processes -- Formulation 1" and submitted it to the Journal of Symbolic Logic. When the paper was published, the editor of the journal, Alonzo Church, added a note that although this machine was similar in some ways to the Turing Machine, it was developed completely independently of Turing.
In time, the machine that Emil Post described became known as the Post Machine or the Post-Turing Machine.
Alan Turing's paper was received by the Proceedings of the London Mathematical Society on May 28, 1936. Emil Post's paper was received by the Journal of Symbolic Logic on October 7, 1936. Had Post published his paper before Turing did, then today everybody might be talking about the Post Machine rather than the Turing Machine.
Nevertheless, when John von Neumann came up with the "stored program concept" when building a real physical computer, he followed more closely the ideas presented in the Post Machine rather than the original Turing Machine. Up until that time, computers (such as the Bombe that Alan Turing built for cracking the German Enigma code) were programmed by turning dials or reconnecting wires in various ways, and even then they only served a unique purpose. This took a lot of human time and effort which was eliminated by designing a general purpose computer that could read in the instructions it was supposed to execute, and then execute them. In doing so, John von Neumann designed the first physical "Universal Turing Machine" and he himself became the world's first software designer.
As time went on, the term Turing Machine took on a much more general meaning. Rather than just pertain to the specific description given by Alan Turing in the paper he published in 1936, it now refers to a whole class of different kinds of Turing Machines. For example, the Post Machine is viewed today as just a special case of a Turing Machine. (In fact, furthermore, the Post-Turing Machine also became a generalized term, and today it refers to a whole class of variations of the Post Machine.)
Strictly speaking, in order for something to be a Turing Machine, it simply has to satisfy the Formal Definition of a Turing Machine.
It probably would be too much to list all Turing Machines on this website. I'm sure I wouldn't be able to do it even if I wanted to. However, it might be worthwhile to mention some of the more interesting ones.
There is a class of Turing Machines called the Busy Beaver Turing Machines. These are usually very small Turing Machines that have very few machine states. They are studied to answer questions like the following:
Of all the Turing Machines that have only 1 state, which one is it that will print the most 1's on the tape before it halts? How many 1's did it print? How many steps did it take before it stopped?
Of all the Turing Machines that have only 2 states, which one is it that will print the most 1's on the tape before it halts? How many 1's did it print? How many steps did it take before it stopped?
Of all the Turing Machines that have only 3 states, which one is it that will print the most 1's on the tape before it halts? How many 1's did it print? How many steps did it take before it stopped?
Etc.
If you're thinking that there can't be too many people in this world that are thinking about stuff like this, just Google "Busy Beaver Turing Machines" and you'll be surprised! There are even Busy Beaver Competitions, and there are web sites that keep track of who answered one of the above questions and in what year.
David Deutch proposed using Quantum Turing Machines to study the capabilities of Quantum Computers.
One special case of a class of Turing Machines that is definitely worth mentioning is the kind described by Roger Penrose in his book The Emperor's New Mind. These are exactly the Turing Machines that you can build and run when you download the Excel File from the Welcome page of this website. Penrose provides six specific examples of such Turing Machines, and he calls them UN+1, UNx2, XN+1, XNx2, EUC, and the Universal Turing Machine. These examples are also available as sample Turing Machines in the Excel file in this web site. (Actually, Penrose also describes thirteen other Turing Machines which he calls T0 through T12 on page 70 in his book; some of these are good Turing Machines and some are not. You can easily try to build these thirteen Turing Machines in the Excel file as well.)
What is really remarkable is that Roger Penrose provides the Turing Machine Number for the Universal Turing Machine, and he writes out that huge number in binary on pages 93 through 96 in his book. This binary number is 5,495 digits long! He also acknowledges his gratitude to David Deutch for converting this number to denary and lists it on page 74 of his book. This denary number is 1,654 digits long!
To the best of my knowledge, this is the only place where anyone actually wrote out the Universal Turing Machine Number! Others, including Alan Turing, have only described how a Universal Turing Machine could be designed. Undoubtedly, everyone expected that the Turing Machine Number of any Universal Turing Machine must be forbiddingly huge. But, as far as I know, this is the first and only time that anyone ever wrote it out!
The Excel file in this website has the Universal Turing Machine designed by Roger Penrose. It is not the first computer implementation of it, because in his book The Emperor's New Mind, Roger Penrose thanked David Deutch for using a computer to check that it actually worked. Also, in his book Shadows of the Mind, in a footnote on page 120, Roger Penrose thanked Steven Gunhouse for finding a much smaller Turing Machine Number for exactly the same Universal Turing Machine. I suspect that there may have been others who also implemented this Universal Turing Machine on their own personal computers. However, I do believe that this website has the first computer implementation of it available to the general public.
Version 1.0 -- June 15, 2022