2.2. Turing Machines¶
The idea for a computer was first described in 1936, over a dozen years before the first electronic computer was ever built. Alan Turing, a brilliant mathematician, was trying to answer a question that mathematicians were struggling with at the beginning of the 20th century, “What are the limits of mathematics? What can be computed using mathematics, and what truths can’t be computed?” Turing defined a device (a Turing Machine) that answered that question: Anything that is possible to mathematically compute could be programmed on a Turing Machine.
Today’s computers work differently than Turing’s machine, but are mathematically equivalent. Anything that is possible to compute can be programmed on any modern electronic computer. ALL computers, from the ones in your microwave to the super-duper computers that predict the weather all have the same basic abilities. Click on the following link to learn more about how Turing Machines work.
The meaning of that statement is huge. For example, it means that it’s possible to run any program on any computer, but it might mean that you have to do a lot of programming to make it work. But it doesn’t mean that we can solve all problems on any computer. One of the important things that Turing proved is that some problems can’t be solved by computers at all, ever.
Turing’s machine didn’t actually know anything about numbers, which might be surprising for a device that could do any mathematical computation. Instead, it could simply make marks on a piece of paper tape, and then count those marks to be able to do mathematics. In reality, electronic computers are just as dumb. They count using patterns of voltages on wires (e.g., “off,on,off,off” is a representation of the number 4 in binary). But we don’t really want to deal with patterns like this, so people have already programmed basic mathematical operations into the computer.
When you work with a computer, you have all kinds of abilities already built-in by others. Your computer already knows how to deal with numbers and mathematical operations, and lots of other things as well. At the basic level, though, even the biggest, most powerful, most expensive supercomputer cannot solve problems better than a Turing Machine. All computers are exactly the same in terms of what they can do.
A programming language (like Java or Python) which is a language that allows you to tell a computer what to do, can do anything that a Turing Machine can do (no more or less). A programming tool like Alice or Scratch can do most of what a Turing Machine can do, but typically, not everything. You can program anything that a Turing Machine can do in Python .
Discuss topics in this section with classmates.