Are Turing machines still useful as model of computation?

Question

Often when I hear "Turing machine," my mind's eye pictures a quaint infinite ticker-tape with a small little machine writing and erasing $0$'s and $1$'s.

But when I'm forced to think about a Turing machine as a tuple of states, blank symbols, alphabet symbols, transition functions, etc., my mind often glosses over.

I live in the 21st century; thinking about computation is so second-nature to me now that I struggle with keeping my mind on such a pleasantly old-fashioned infinite ticker tape. I know pretty well how the computer on which I'm writing this operates, clearly not at the details of the machine code but at a level of abstraction that I feel comfortable with. I also never liked how the alphabet has, basically, three symbols $(0,1,blank)$. Why do we even need the $blank$?

Turing's work in the 30's was baller of course, and there are some well-deserved accolades when the new "smallest universal Turing machine" or "largest Busy-Beaver" are announced. People also have a game of writing esoteric programming languages based on small Turing machines.

But is there a good reason to use the ticker-tape Turing machine for a model of computation, now, in the 21st century? Are there reasons for the formalism still being "worth it?" Or can we just say a Universal Turing Machine as in a smart-phone?

Of course Hamilton's etchings on Broom Bridge marked a turning point in the history of mathematics, but I've read that quaternions per se were oversold by the end of the 19th century.

Answer 1

I think the issue is that, you're misunderstanding the purpose of the Turing Machine model.

Turing Machines are not meant to be programmed in. If you're writing code, you absolutely should not be thinking of how it would run on a Turing Machine.

However, Turing Machines are excellent for reasoning about. In Theoretical Computer Science, we're interested in proofs. We want to be able to say "there exists an algorithm with this property" or "for all algorithms, this statement holds". And we need an operational definition of what an algorithm is.

This is exactly where Turing Machines come in handy. First, the definition of a Turing Machine is precise: it's an exact mathematical object, whose behaviour is fully specified. Secondly, it's small: it contains finite states, and transitions between states that affect the tape.

If you wanted to rigorously prove something about a smartphone model, you would have to reason about all the different bits in memory, possibly even about hardware and transistor states. But to prove something about a Turing Machine, there's one simple state-space, and a simple memory model. This is how we've been able to build up theories of decidability, computational complexity, etc. They work because they're based on a model that's simple enough to write proofs about, but powerful enough that it reflects the capabilities of actual computers.

For example, say you create a new programming language. You want to show that every problem that can be solved, can be solved in your language. Now, you could show that you can simulate an entire smartphone's circuitry in your language, each gate and transistor and byte. But that's huge. Instead, you can achieve the same thing by showing that you can simulate an arbitrary Turing Machine in your language, which is much simpler to write.

Now, it's worth mentioning that Turing Machine's are not the only model of computation. There are two main competitors. First, any time we're discussing fine-grained complexity, you will likely use a RAM model instead of a Turing Machine, so that you can model the speed of algorithms without having to traverse the entire tape to access a particular part of memory. Secondly, the Lambda Calculus and its various derivatives are equivalent in power to a Turing Machine. While they don't model hardware, their semantics closely match how we think of programming language as behaving, and there's an entire field (Programming Languages Theory) build around such models. They're not as minimal as Turing Machines, but they're more compositional i.e. it's easier to build programs by combining small building blocks. and their behavior is predicable based on those combinations.