Turing machines

Next post in topic
Previous post in topic
First post in topic

There was the butcher, the baker, and the candlestick maker. Good for them, all fine an honorable professions, but there was another job you could have back in the day. You could be the computer.

Just like butcher or baker or candlestick maker, a computer was a job title, the person who did whatever calculation you needed to have calculated. This might be to survey property, work out your taxes, figure out how much flower the baker should order, how much extra business the candlestick maker could expect in an average winter, or how much money the butcher could expect to lose when some religious observance kept customers from eating or ordering any meats.

Computers often used things to help them calculate. This could be as simple as marks on a stick, or small stones moved from one bowl to another, or it could be some sort of calculating device. In many cases, such as with the abacus, the arrangement was simple, but there were special rules and procedures to follow, such as one row of beads representing ones, and another being fives, and another being tens. It was part of the computer’s training—learn the device, and the way to use it, and then figure out how to use what you’d learned to give the butcher, the baker, and the candlestick maker the numbers they needed.

As with any other profession, some computers were better and more reliable than others. They could, and did, make mistakes in their calculating, and the skills to catch the mistakes or correct them before they could cause problems weren’t widespread. If, instead of working for one of the honorable townsfolk, your customer was, oh say, the king, this could become especially ticklish.

Running a kingdom takes lots of number crunching. You have to gather taxes, assess land, build castles, lay roads, store food, maintain the army, and that was all in peace time. If you went to war, things got much more complicated.

Good numbers, and your weapons hit, your troops had accurate maps, your forces could arrive when and where they were needed with enough supplies to let them win the day. Bad numbers and you couldn’t hit anything, the troops stumbled randomly across the countryside, you could miss the battle, lose the war, and your soldiers might find they’d been sent too many candlesticks and not enough meat.

Over the years, a number of mechanical calculating machines were designed and built. These machines often took quite a bit of calculating to figure out how they could calculate, and a good deal of time and money to build them. They were often built to solve a particular problem quickly, but even when everything worked, you still needed the computer to use them. If you’ve ever used a calculator, you know how easy it is to hit the wrong buttons, or even the right buttons in the wrong order. So, errors persisted in causing problems. To make matters worse, sometimes the calculator would depend on large tables of numbers, worked out by computers and then built into the machine. If there was a mistake in those tables, it got built right in. Then, after all that time and effort building the calculator for, say, aiming your guns, when you needed to do something different, like keep track of supplies, you’d be forced to design and build an entirely different calculator.

What if, instead of building some calculator for a computer to use, you could build a computer? Could some machine be designed and built that could do any calculation, and which could, if given very specific instructions, push its own buttons in the right order. You’d only need one kind of machine, and the number of errors could, at least in principle, be lowered to nearly zero.

Enter the Turing machine.

The Turing machine is an abstract model of a computing machine, described by Alan Turing in 1936. It has a tape, divided into cells or slots. In each slot there can be a symbol, or the slot can be blank. The symbols are part of a predefined alphabet that can be used to write commands or instructions. The machine has a head that can read a symbol, or write one. Lastly, the tape can be moved in either direction. The machine will read a symbol and then, depending upon what’s been read, it will write a different symbol, or move in one direction or another, according to a table of rules. The machine can store some of the symbols internally, and it changes from one state to another according to what symbols are encountered and the rule table.

When I first read about Turing machines, I was less than satisfied. The explanations I was reading seemed like they did a lot of hand waving. Somehow, this set of internal states and this alphabet and either move read or write was supposedly enough to make this thing do everything a computer can do. But how? How does reading writing and moving turn into Mine Sweeper, or the table of rules and internal states become email, text messaging, YouTube and Twitter?

Let’s find out!

A computer used to be a job, and before we try and make a machine do the computing, it will be our job. We’ll use an alphabet you’re already familiar with, and one simple procedure that can be repeated over and over again, to obtain any result we need.

Our alphabet has only eleven symbols—the numerals, 0 through 9, and a minus sign.

Next post in topic
Previous post in topic
First post in topic