2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Smartphones may not have "infinite tape," to begin with. They're quite finite. But more generally, it sounds like your question is more akin to "do we really need set theory, to begin with? Are there reasons for the formalism still being "worth it?" Or can we just say a number is a number, without thinking of $0$ as $\emptyset$ or having to build the reals?" than to the quaternions anecdote. It's not necessary on a daily basis, and you can forget about them most of the time; but there needs to be a common, agreed-upon, sound foundation... $\endgroup$ – Clement C. Apr 5 at 16:42
  • $\begingroup$ This question is probably a good candidate for migration to CS.SE $\endgroup$ – jmite Apr 5 at 17:04
  • 1
    $\begingroup$ @ClementC. Brilliant! Of course the formalism of set theory is worth it! Of course formalizing computation is worth it. The ZFC axioms are path-dependent, and there are other choices, but it's what people use. Turing machines are path-dependent- and there are clearly other choices, but it's what people use. I shouldn't be dismissive of Turing machines if I'm unwilling to be dismissive of ZFC. $\endgroup$ – Mark S Apr 5 at 18:08
11
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thanks for helping me clarify my source of frustration! I've found the physical embodiment of a Turing machine to be off-putting to my 21st century mind's eye, like there's a Platonic ticker-tape machine that must be instantiated as some early 20th century machine to have any chance to talk about computation. Contrast this with set theory - I'm OK with the level of formalism of ZFC, but it never has to be instantiated as something "physical." I'd be OK with alphabet symbols etc. if I didn't immediately have to think of a ticker-tape. But that's not the Turing machine's fault. $\endgroup$ – Mark S Apr 5 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.