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: 
Turning Machines model computation, and don't have a concept of interaction. In that sense a machine that supported interaction with an outside system can do things a Turning Machine can't. But the computation done *between* bit of input from an outside source can obviously always be modelled by a Turing Machine, so even an "IO Machine" can't do anything *with* outside input that a Turing Machine couldn't do.

In some sense such a machine may be able to "decide" problems that are undecidable by Turing Machines, but only if you imagine that the system it is interacting with has super-Turing-Machine powers *and is reliable* (in some way; probabilistic reliability would be enough).

Imagine a program for an IO Machine like: "for any initial tape input, print the tape contents, then read a symbol from outside input; accept if the symbol is 1 and reject otherwise". This program can decide **any** problem. But *only* if the outside system it can interact with is capable of deciding the problem; to me that's not a very interesting way of saying that the IO Machine of is able to decide problems that are undecidable by Turing Machines.

I think it would always be possible to represent an interactive computation by imagining a machine that takes as input on its tape an encoding of some prior configuration together with an outside input, and have the machine halt with its tape containing an encoding of a configuration together with output. Then the process of "running a program" is repeatedly running this Turing Machine in a mechanical fashion, with the only "non-mechanical" part being however the outside input is sourced. I'm certain that you could prove that if such a system got its input by giving its output to *another Turing Machine* set up to operate in a similar manner, then the combined system has identical computational powers to a single Turing Machine. I find that a convincing argument that interactive computation is no more powerful than non-interactive computation, *unless the system the computation interacts with is more powerful than a Turing Machine*.

---

There is a non-theoretical sense in which interactivity can add to a computer's ability to solve problems, however. There are many things which humans do very accurately that we don't know how to get computers to do very well. But there are also many many things that humans are rubbish at that we can get computers to do. Combining these two can lead to projects such as [reCaptcha](http://www.google.com/recaptcha/learnmore), which is effectively automatically digitising books by farming out the problems of recognising words to humans in difficult cases. The resulting system of computer + human labour achieves a result that is currently impractical to achieve with either the computation alone or the human labour alone.
Check this out :)
"***Turing's Ideas and Models of Computations***"
<https://www.cs.montana.edu/~elser/turing%20papers/Turing%27s%20Ideas%20and%20Models%20of%20Computation.pdf>