Why are Turing Machines the Preferred Model of Computation?

There are several reasons of the popularity of Turing machines:

(1) Turing machines fit well in a course of automata theory: you can start by introducing simpler models, like finite automata or pushdown automata and then move to TMs.

(2) The statement of the most famous open problem in theoretical computer science, namely P = NP, and more generally Computational complexity theory heavily relies on TMs.

(3) The notion is quite flexible and admits several extensions like Alternating TMs, Probabilistic TMs, Quantum TMs, just to name a few.

Some people might also be perhaps fascinated by the Busy Beaver problem (see Busy Beaver Scores and Alphabet Size for recent results) and its applications to Goldbach's conjecture: there is a 47-state, 2-symbol, 1-tape Turing machine that halts iff Goldbach's conjecture is false.

If you read Turing's original 1936 paper, you will see how he tried to get at the fundamental ingredients of a human following some systematic process of symbol manipulation. The word 'effective' is sometimes used in this context: a computation or algorithm is 'effective' when a human can perform it. E.g Long division is an effective algorithm because we can do it. In fact, when we are performing long division, we are the 'computer'. Indeed, in Turing's time a 'computer' was often still understood as a human performing some calculation. The Manhattan project, for example, used many human computers, and the recent movie Hidden Figures showed the human computers employed at NASA at the time of the Apollo Project.

Turing's conceptual path that led him to his 'Turing Machines' is actually fairly straightforward. Any computer, Turing said, manipulates a bunch of symbols, which we can think of written down on a sheet of paper. Now, while computing, the computer takes discrete steps, where each step taken is dependent on what stage or state the process is at, and what symbols the computer sees in front of it.

Going back to the addition of numbers, for example, we may at some point find ourselves in the 'state' of having to add two specific digits, followed by the 'state' of having to write down the result, etc. Now, Turing said, while our natural language description of these states may use words like 'adding two digits' or 'writing down the result', all that is really important is that the computer is able to distinguish between the different states. That is, for all that the computer cares, the different states could simply be numbered $1$, $2$, $3$, etc. and all that the computer needs to know in order to make its next move, is to know whether we're in state $1$, $2$, or whichever other state there may be there.

A similar story goes for the symbols, Turing argued. That is, while we are used to the decimal representation of numbers, we could of course use any other kind of representational scheme. Again, Turing argued, all that matters is that we are able to distinguish one symbol from a different symbol. Or, a little more technical, if we use a set of symbols $s_1$, $s_2$, $s_3$, etc. then all that should matter to the computer is that the computer be able to recognize that some written symbol is, say, symbol $s_2$, rather than any of the other symbols. In short, the computer simply needs to have an alphabet of symbols that the computer is able to read and write.

How are the symbols organized? Turing writes:

Computing is normally done by writing certain symbols on paper. We may suppose this paper to be divided into squares like a child’s arithmetic book. In elementary arithmetic the 2-dimensional character of the paper is sometimes used. But such use is always avoidable, and I think it will be agreed that the two-dimensional character of paper is no essential of computation. I assume then that the computation is carried out on one-dimensional paper, on a tape divided into squares.

Turing here makes the point that whatever we can compute using a two-dimensional (or even higher-dimensional, as when we use multiple sheets of paper) layout for the symbols, we can always simulate using a one-dimensional layout, since we can always 'string' together all the lines and make it into one long string of symbols, possibly using special symbols to demarcate what would normally be line, page, or other breaks.

Also, since it is not predictable how much 'scratch' work one has to do while performing the computation, Turing decided that we can think of having a tape with an infinite number of squares on it, and that symbols can be placed in each of those squares. Or, maybe more realistically, that one always has the ability extend the tape by adding squares on either direction, so that one is guaranteed of any amount of 'working space' as needed.

How many states and symbols can there be? Turing said that there could be any number, as long as it is finite. Turing argued for both to be finite saying that the human mind and human memory was limited. Also, assuming a finite size of the squares on the tape in which to place our symbols , there can only be finitely many different symbols, or else the differences between the symbols would be come infinitely small, and we would not be able to recognize and discriminate the one symbol from the next:

I shall also suppose that the number of symbols which may be printed is finite. If we were to allow an infinity of symbols, then there would be symbols differing to an arbitrarily small extent.

Finally, as a computer we must be able to go to any arbitrary place in this one long string of symbols. But for that, Turing argued, all that is required is an ability to go either left or right one square relative from the square one is currently looking at: wherever one wants to go, eventually one should be able to get there. Thus, Turing imagined that one would have a 'read/write' head that at any particular point in time would be 'at' some particular square on the tape, and that this 'head' can move left or right, one square at a time.

And there you have it: all the components that we now call a Turing machine!

Moreover, this very argument makes the Turing-Church Thesis plausible that any computation can be performed using Turing-computation.... which is why it is important that instructors covering Turing-machines should relate Turing's analysis to the students, rather than immediately starting with a definition of Turing-machines as unfortunately so many instructors do.