Question: I've heard the motto [**interaction is more powerful than algorithms**](http://www.cs.brown.edu/people/pw/papers/ficacm.ps) from [Peter Wegner](http://www.cs.brown.edu/~pw/). The basis of the idea is that a (classical) Turing Machine cannot handle interaction, that is, communication (input/output) with the outside world/environment.

> 
> How can this be so? How can something be more powerful than a Turing Machine? What is the essence of this story? Why is it not more well known?
> 
> 
>

Answer: 
Turing machines can handle interaction just fine, using oracle tapes. It works are follows: from the point of view of a computer that handles interaction, the input of the operator is simply another sequence of bits that it sent into the computer from time to time. We all know that a lazy sysadmin could write a script to send the input to the program when it is requested, so that the sysadmin could go on break earlier. The interaction machine has no way to know if there is really a live operator at the console, or if the input is being piped from another program. 

Having all the interaction input prepared ahead of time is the same, in theoretical terms, as having all the input on a separate tape that is used by an oracle Turing machine. Whenever the computer would normally request interaction from the operator, the machine instead reads from the input tape. If the thing read from the tape seems invalid in some way, the Turing machine does exactly what the interaction machine would do on receiving that input.

I would guess that Wagner is aware of the ability to use oracle tapes to code input, so you have to take his comments with a grain of salt, or you have to ask what he actually means. I believe that people who think about interaction are generally worried about two things:

* "Real" computers do have interaction, but algorithms as defined by Turing don't. We can get around this by coding the input on oracle tapes, but this still does not match the way that real computers operate. It might be nice to study models of computation that are more closely aligned with real computers.
* Oracle-based algorithms are not often considered in day-to-day computing because normal computers don't come with a magic "oracle" to supply data. But we might be able to actually just use a person as the oracle. If the person understands the data that is being requested, they may even be able to help the algorithm along, thus improving its performance. In other words a human may be able to provide a useful oracle tape rather than simply a random one, and in principle this might lead to faster or more powerful computing methods compared to non-oracle-based ones. A similar thing happens with randomized computing, after all, where the machine is given a sequence of random bits as an extra input.
Recently ACM held Ubiquity symposium '[What is Computation?](http://ubiquity.acm.org/article.cfm?id=1883611)' in which Peter Wegner published an article which reflects his views on Interactive computing.

Here are two excerpts from the article by Peter Wegner:

> 
> One new concept, missing from early Turing machines, is "Interactive Computing," which accommodates interaction with the environment during the computation. 
> 
> 
> Interaction machines can perform more powerful forms of computing than Turing machines, and can perform the kind of thinking proposed by Turing because interaction improves their performance over that of Turing machines.
> 
> 
> 

However, Fortnow, who has an article in the same symposium, appears to disagree with the Wegner views and believes that interactive computing does not offer any additional power over Turing Machines. 

To add to the mix, it appears that we are still debating and defining computation. Moshe Vardi has an article, What is an Algorithm?, Communications of the ACM, Vol. 55, No. 3, March 2012.

Vardi reports on two new definitions of algorithms. The first is proposed by Gurevich and the second by Moschovakis.

> 
> Gurevich argued that every algorithm can be defined in terms of an abstract state machine.
> 
> 
> Moschovakis, in contrast, argued that an algorithm is defined in terms of a recursor, which is a recursive description built on top of arbitrary operations taken as primitives.
> 
> 
>