Computer Abilities

Is that really all that a computer can do: name things, repeat steps, make decisions, and manipulate data?

Yes, really – that’s it. Everything else that a computer can do is just combinations of the those abilities:

This is enough to build a Turing Machine. In fact, everything that possibly can be computed, can be computed with just these four abilities, combined in different and sometimes surprising ways. Probably the most powerful way is called abstraction. An example of abstraction is when you create a function or procedure. Others can then use that function or procedure without knowing or caring out the details of how it works.

Now if you think about what you know that people do with a computer, the claim that these four abilities is all that you need to do everything may seem far-fetched. How does a computer interface with a human or another computer? All connections to the world outside of the computer appear as memory (special variable values) to a computer.

Now, think about all the wonderful things that computers can do, from web searches over billions of sites, to massive data analysis to track far away stars, to sharing messages among billions of on-line friends. All of those can be understood in terms of these four abilities.

Computers today are fast. A typical computer today might execute a single assignment statement in one billionth of a second. It is very difficult to write a program that will even take a full second to execute. Mostly what a computer does today is wait – wait on data coming in from the network (which the computer sees as, you guessed it, another memory location), or waiting on the user to type a key or move a mouse.

We know that there are some limits to what we can compute. For example, we know that we can’t write a computer program that can test all other computer programs. The problem is called The Halting Problem. Imagine a program as one big long string. We know that we can look at parts of that string using indexing. We know that we can make decisions using if statements. Can we write a program that can read other programs as strings, and tell us whether or not they will work? Alan Turing, the same brilliant mathematician who defined computers for us, also wrote the mathematical proof that such a program is impossible. We can’t write a general “program checker.”

But we don’t know the limits of computing with respect to ourselves. Are we computable? Is our intelligence just a really big and complicated program, with millions of conditions and hundreds of loops and billions of variables? Is it possible to write a program that is intelligent? We don’t know the answers to those questions yet, but it’s a fascinating problem to see how far we can push Alan Turing’s machine.

You have attempted of activities on this page