We all know what computers are, right? They sit on our desks and in our pockets, and put the smarts into everything from cars to washing machines.
Advertisement
That’s not wrong – and yet it’s not entirely right.
At its most basic, a computer takes information as an input, transforming it according to some predetermined rules into a different output. The digital electronic computers that rule our world do this using little pulses of electric current. But there’s no reason it has to be that way. “An abacus allows us to compute by moving stones around,” says at University College London. “If you can do that, I struggle to think of anything you cannot compute with.”
Sundials convert shadows to time, the liver regulates chemical outputs according to inputs, even rocks store mineral compositions for later breakdown and release: all of these things fit the broadest definition of a computer. “The notion of ‘computation’ currently appears to float dangerously free of its foundations,” says of Goldsmiths, University of London.
One way out is to suggest a hierarchy of computing machines. At the bottom are “finite state machines”: things like traffic lights and elevators that do little more than cycle through a limited series of input and output states.
Digital computers fall into the category of Turing machines. As conceived by Alan Turing in the 1930s, these read symbols from an infinitely long input tape and substitute them according to a set of rules, thereby simulating the behaviour of any conceivable algorithm. Basic though it seems, this still provides perhaps the best understanding of the limits of computation, says Bentley.
According to Turing’s model, though, there are well-defined problems that no computer can answer, such as the self-referential Halting problem, which asks “Will this program stop?”. No computer can say yay or nay without actually running the program (and possibly stopping). Other problems, though theoretically computable, take an almost endless time to solve. “Computer science was born very conscious of its limitations,” says at the University of California, Berkeley.
Models of computing more powerful than Turing machines do exist; Turing himself speculated about them (91av, 19 July, p 34). Some people think biological processes might be able to implement such “super-Turing” computation, accounting, perhaps, for some of our own excessive smarts. Others think that super-Turing models can only work by breaking the laws of physics as we know them. If so, that suggests an intriguing and deep-seated connection between notions of computability and the workings of the universe. If we can’t quite get our head around computers, perhaps it is because we are sitting in the biggest of them all.
Read more: “Get your head around the 13 boldest ideas in science”
This article appeared in print under the headline “How to think about computing”
