by Ian Stewart
The Tweedle twins and I were straphanging on the New York City subway. Delia Tweedle was universally known as Dee, so her brother had inevitably become Dum. Even though his real name was Seymour. As usual they were interrupting each other.
"Well, if the universe is algorithmic, then strong AI--"
"Don't be pedantic, Dee, what you mean is computers that think--"
"Must be possible in principle."
"Why?" I said.
"If our universe is algorithmic--"
"You could set up a computer to simulate it--"
"Which would therefore simulate everything in it, including us having this conversation," Dee concluded.
"You realize that if you're right, then a sufficiently complex subway system could become intelligent?" I said. "It would think rather s-l-o-w-l-y...but it would still be able to think."
"That's dumb," Dee exclaimed. "A subway can't think."
"Maybe not. But a subway can compute, according to a fascinating article I've just read in the latest issue of "Eureka." It was written by Adam Chalcraft and Michael Greene, and it's about the computational abilities of train sets."
"You mean TOY train sets? Rails and points and tunnels with sheep painted on their sides?"
"That's right, Dee. And whatever a train set can do, a subway surely can. It's not quite your hyperparallel superduperultracomputer, but in theoretical computing ability, equally as powerful. A computer is, after all, just a huge switching circuit with adaptable switches. And trains can switch tracks using points. What Chalcraft and Greene asked was: If you've got a big enough stock of straight and curved track, bridges and various kinds of points, but you've got only one engine and NO rolling stock, then what computations can you do if you set up the right track layout?"
"I don't see how a train can compute at all," Dee puzzled. "It's just a thing on wheels that moves along the rails."
"Electrons are just things that move along wires, but they are what computers compute with," I pointed out. "In both cases, the computational aspect is a matter of interpretation. For a train layout, the idea is to encode an input as 0's and 1's corresponding to the settings of various points. Then you run the train through the layout, and sometimes those settings change, which in turn alters the path of the train. Eventually the train is sidetracked onto a line leading to a terminal, the program 'stops,' and you read the output from the settings of the same collection of points."
"Okay, I see that it might work. But does it?"
"Let me start with the simplest switching unit, known as a lazy point . It's a Y-shaped piece of track. A train entering the Y from below runs up the upright and out of whichever arm of the Y the points are set for, leaving them unchanged. But a train that enters from one of the arms will--if necessary--reset the points so that they connect that arm to the upright and then exit via the upright. Lazy points have two states, depending on which arm is connected to the upright: call them left and right.
"The next type of point is a sprung one. It's like a lazy point except that any train entering along the upright of the Y always leaves by the same arm. The third kind of point is a flip-flop.
"With a flip-flop, trains always enter along the upright of the Y and exit through the left and right arms alternately," I went on. We lurched judderingly into the Liberty Avenue station. "The big question is: Given these components, can we build a computer?"
"What kind?" wondered Dee.
"A Turing machine," I said. "Alan M. Turing proved that his simple model of a computational system can do anything that a programmable digital computer can. Think of a Turing machine as a box that can travel along a very long tape of square cells, each containing either the symbol 0 or 1. You can either use an infinite tape or, if you don't like infinities, you just have to be prepared to add some more cells to the tape if you need them.
"The box can be in any of a finite set of internal states, depending on what hardware is inside it. For each combination of its own state and the digit written on the cell immediately below it, it must obey a small list of instructions, like this:
'Leave the current tape digit alone/change it.
'Then move one space left/right.
'Then go into some specified internal state ready for the next step.'
"Or the instruction can be just 'STOP,' and the computation then finishes."
"Give me an example."
"Okay. Here's a typical list of rules for a Turing machine with three states--1, 2 and 3:
'State 1, Digit 0: Change digit, move left, go to state 2.
'State 1, Digit 1: STOP.
'State 2, Digit 0: Leave digit, move right, go to state 3.
'State 2, Digit 1: Change digit, move right, go to state 2.
'State 3, Digit 0: Change digit, move right, go to state 1.
'State 3, Digit 1: Leave digit, move left, go to state 2.'"
"What does that compute?"
"I haven't the foggiest idea, Dum. Try it and see. Sensible programs generally need a lot more states than three, anyway. The digits on the tape provide the computer's input. The list of which instructions to perform for which internal state of the box forms the program, and the list of digits on the tape when the computation stops is the output. Amazingly, these simple devices can carry out any algorithm whatsoever. So all we need is to find a train layout that simulates any chosen Turing machine."
"Tricky."
"Yes. It helps to break down the problem into a series of stages. Now, the idea is to find a train layout that can play the role of the box. Instead of using a tape, you just plug an enormous number of these boxes into each other, side by side, to represent the whole tape. Each box will have several tracks coming in from the left and the same number going out the right--one track for each internal state."
"So instead of the box moving along the tape--" Dee began.
"The train moves along the row of boxes," Dum finished, enthusiastically.
"You can tell which 'cell' of the 'tape' is being worked on--"
"By which box the train is in. Neat."
"Yeah," Dee agreed. "But what do you put in the box? Schrodinger's cat?"
"I'll explain how the box is designed in stages. The train tracks are used as both input and output lines, so the box doesn't 'remember' which direction the trains came in from. Therefore, it can be set up as an outer shell that feeds trains from both input lines the same way into a core and conducts them out again according to the Turing program. Then we can ignore the outer shell and concentrate on the design of the core."
"You're going to need--" Dum started.
"Subroutines," Dee said. They'd been thinking ahead, as usual. A subroutine is a part of a program that can be used repeatedly by "calling" it from any other part. You can build complex programs by stringing together subroutines.
"Yes," I concurred. "You can set up a subroutine by hooking up a self-contained sublayout to a whole series of lazy points. Then the train comes in, setting the points as it does so, and wanders around the sublayout until it has carried out whatever subroutine that the sublayout computes. Finally, it exits by the same track that it came in on because of the way it set the points on entry. Using one lazy point for each input line, the trains can all be made to enter from the left, carry out the subroutine and exit to the right along the same track they entered on."
"Oh, right."
"Now, you need one more piece of gadgetry: a read/write head. If a train comes into a read/write head from the left, then it exits along line 0 or line 1 depending on the digit at the 'current' point of the tape. If a train comes in from above, then it swaps the 0 and the 1 and exits at the bottom. To achieve this, the lazy point P is set to redirect the train along output line 0 or 1 according to the digit on the 'tape' at that square. The flip-flop is set so that the first train entering from the top switches P to the other position.
"Having got all these bits and pieces, you build the inner core of the box. You may need some bridges to avoid the tracks crossing, but we can ignore that. The core consists of a parallel set of read/write heads, one for each internal state of the box. The output lines 0 and 1 lead to one of the output lines of the core, or to a lazy point that diverts the train into a subroutine that changes the state of that cell on the tape, or to a STOP subroutine that guides the train into a single terminal."
"Let me see," Dee interjected. "For your example, one of the rules is 'State 1, Digit 0: Change digit, move left, go to state 2.' How does that work?"
"Being in state 1 means that the train enters the cell along line 1, from the side. This state is actually set by the output of the PREVIOUS cell, which directs the train onto line 1 when it exits. In this case, the digit 'written' on the current cell is 0: that is, all the lazy points in the read/write heads are set to 0. So the train comes into the first read/write head, leaves along line 0 and runs into a set of sprung points. These direct it into the 'change digits' subroutine. It runs vertically downward, through all of the read/write heads, and flips their states from 0 to 1. So the digit written in the current cell now reads 1, not 0. The train continues back up the vertical track to the left of the heads, exits from the subroutine back onto its original track and then comes out of the core on the output line 2 LEFT, which effectively moves the train into the cell to the left, in state 2, as required."
"Cute. Suppose we look at the rule 'State 2, Digit 0: Leave digit, move right, go to state 3.' The train comes in along line 2 and exits the read/write head along line 0, which leads directly to exit 3 RIGHT. And it never goes anywhere near the subroutine loop, so the state of the cell remains unchanged."
"Right," Dum said. "And it's equally obvious that the rule 'State 1, Digit 1: STOP' works properly. Enter along line 1, exit the read/write head along line 1, and you get fed straight into the line that ends at the terminal."
"Exactly. You just set up the lines according to the rules that define the Turing machine."
"Do you realize," Dee asked, "that this shows that the future behavior of a train set can be undecidable?"
"Of course," Dum said. "Turing proved that the halting problem for Turing machines is formally undecidable. You can set up a Turing machine for which there is no way to decide, in advance, whether or not the computation stops."
"Which means that for the corresponding train layout, you can't predict in advance whether the train is ever going to reach the terminal."
"That's quite startling," I remarked. "I've never been terribly bothered by the formal undecidability of theoretical mathematical questions. I mean, who cares? But it's a bit worrying that you can set up a mechanical system--toy train tracks, for heaven's sake--whose workings are totally transparent, but not be able to answer such a simple question as whether the train will ever reach a chosen station."
"Speaking of which--" interrupted Dee.
"It's been an awfully long time since the last stop," Dum said.
I wiped away the moisture fogging up the window. "Hmm," I said. "We've slowed down to a crawl. All I can see is a big square with the digit '1' painted on it. And I swear there's a sign just along the tunnel that reads 'flip-flop 7743A/91.'"
"Dee gets claustrophobic if subway trains stop between stations," Dum whispered.
"They HAVE been adding some new connecting lines to the subway network," I offered. "Maybe its connectivity has passed the Turing threshold, and it has achieved artificial intelligence."
"O Mighty Subway," Dee declaimed, her voice rising rapidly in pitch, "we humble humans solicit your omniscient aid in GETTING US OUT OF--" At that moment a connecting door opened, and a uniformed guard stepped into the car.
"Small problem up the line, folks," he smiled. "Nothing to worry about, but we have to slow down for a while." Dee sighed with relief. "Hey, is the little lady all right?"
"Yeah," Dum answered. "She just thought she'd got stuck in an artificially intelligent Turing machine."
"This isn't any touring machine," the guard said indignantly. "This is a personnel commuter, buddy."
At least, I think that's what he said.
| Problem of Consciousness | Brain Tour | Machinery and Intelligence | Alan Turing | Amanda Sharkey | Bletchley Park (Ciphering)
Further Reading
THE TURING OMNIBUS. A. K. Dewdney. Computer Science Press,
1989. |
| Chaos | Quantum | Logic | Cosmos | Conscious | Belief | Elect. | Art | Chem. | Maths |
SCIENTIFIC AMERICAN Sep1994 File Info: Created Updated 17/10/2000 Page Address: http://members.nbci.com/Templarser/subway.html