Is interaction more powerful than algorithms?

cs.stackexchange https://cs.stackexchange.com/questions/438

  •  16-10-2019
  •  | 
  •  

Pergunta

I've heard the motto interaction is more powerful than algorithms from Peter Wegner. 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?

Foi útil?

Solução

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.

Outras dicas

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, 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.

Recently ACM held Ubiquity symposium 'What is Computation?' 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.

I do not think models with IO are "more powerful" than Turing machines, they just model different things.

In theory, you could view IO as (noisy?) oracle. With a perfect oracle you can computer Turing-uncomputable functions; but where to get the oracle from? Humans are the only "super-Turing" choice (if there is any) and we are known to be very unreliable.

A class of programs that fit this model are interactive proof assisstants (e.g. Isabelle/HOL, Coq). They deal with undecidable proof spaces but (arguably) every proof can be found (and checked) with suitable user input.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top