17
$\begingroup$

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?

|cite|improve this question|||||
$\endgroup$
  • 1
    $\begingroup$ Do you have a reference to include in your question? I know the formal definition of a Turing Machine, but I don't know exactly what you mean by "interaction". $\endgroup$ – Janoma Mar 16 '12 at 21:16
  • $\begingroup$ Also, it seems like "cannot handle interaction with the environment" is similar to "cannot handle true randomness", which might be true, but both of them can be approximated quite well with sensors and pseudo-randomness. But that is an uninformed comment, not knowing a definition of interaction. $\endgroup$ – Janoma Mar 16 '12 at 21:18
  • 2
    $\begingroup$ Turing Machines don't have sensors. $\endgroup$ – Dave Clarke Mar 17 '12 at 0:05
  • 1
    $\begingroup$ I am aware of that. And yet, computers do use sensors, which are a particular way of passing an input to a Turing Machine. So TMs do interact with external signals/environment somehow. $\endgroup$ – Janoma Mar 17 '12 at 2:39
  • 2
    $\begingroup$ The question isn't about computers. The only interaction with a TM is that the environment provides one input to it at the start, and receive at most one output at the end. This is hardly general interaction. $\endgroup$ – Dave Clarke Mar 17 '12 at 7:50
11
$\begingroup$

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.

|cite|improve this answer|||||
$\endgroup$
  • $\begingroup$ Oracle tapes do not correctly model interaction. Consider trying to prove that a computer system doesn't leak private information. This can't be formalized in terms of a TM with a fixed oracle tape, because the property depends on characterizing the computation that the environment can do -- exactly what we abstract away with an oracle tape. $\endgroup$ – Neel Krishnaswami Mar 22 '12 at 14:24
  • $\begingroup$ It depends on what you mean by "correctly model". Some papers (e.g. from the hypercomputation community) appear to suggest that interaction somehow enlarges the set of computable functions. Which it does, in exactly the same way that oracle computation does. Of course you can't use TMs to study properties of the actual computation environment; if you want to know if the processor in your computer is buggy, it won't help to ignore it completely and just look at Turing machines. But for questions that are only about the function that is being computed, interaction and oracles are equivalent. $\endgroup$ – Carl Mummert Mar 22 '12 at 14:32
  • $\begingroup$ No, this is not the case: there are continuity restrictions on feasible interactions which oracle tapes don't model. If the environment cannot see inside the program, then the input it supplies at time $n$ may only depend on the output at earlier times $n$. (That is, viewing the input as a function of the output, the input function has to be nonexpansive with respect to the Cantor metric.) Just as computability "feels like" topology to a classical mathematician, interactivity "feels like" topology to constructive mathematicians. $\endgroup$ – Neel Krishnaswami Mar 22 '12 at 15:26
  • $\begingroup$ For a really thorough working out of this analogy, see Peter Hancock, Pierre Hyvernat: Programming interfaces and basic topology. citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.107.919 $\endgroup$ – Neel Krishnaswami Mar 22 '12 at 15:27
  • 1
    $\begingroup$ The input the operator enters at time $n$ can be any possible input, and so the collection of all possible input runs contains all infinite sequences of input elements. There's no continuity there, because the operator can enter anything. Feasibility (which I take to mean computational complexity) is not relevant to the question I am answering - any function can be computed by an oracle machine, if the function is given on the oracle tape, and similarly any function can be computed by an interaction machine, if the operator is prepared to enter arbitrary values of the function on demand. $\endgroup$ – Carl Mummert Mar 22 '12 at 18:00
8
$\begingroup$

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.

|cite|improve this answer|||||
$\endgroup$
8
$\begingroup$

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.

|cite|improve this answer|||||
$\endgroup$
6
$\begingroup$

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.

|cite|improve this answer|||||
$\endgroup$
  • $\begingroup$ So Turing Machines with Oracles are more powerful that Turing Machines without them and Turing Machines with Oracles can model interaction. So the answer seems to be yes. $\endgroup$ – Dave Clarke Mar 17 '12 at 10:56
  • 1
    $\begingroup$ @DaveClarke If you consider perfect oracles, yes. $\endgroup$ – Raphael♦ Mar 17 '12 at 11:01
  • 2
    $\begingroup$ I think an unaided (by any form of oracle or input) machine (or program) could in principle find every proof. There are two problems: (1, theoretical): it will never be able to ascertain that a statement has no proof, and (2, practical): blindly generating proofs in the hope of stumbling upon a given statement is so awfully inefficient that nobody wants to try, and so proof assistants prefer a guided search, abandoning "assured" succes in case a proof does exist. $\endgroup$ – Marc van Leeuwen Mar 18 '12 at 8:51
  • 2
    $\begingroup$ As Ben points out in his answer, the right way to look at it is not "Turing machines with oracles are more powerful"; the machines themselves are just doing computable things. The right way to look at it is "some oracles are not computable, and so from those oracles we can compute things that we cannot compute without an oracle". The computational strength comes from the oracle, rather than from the machine. $\endgroup$ – Carl Mummert Mar 22 '12 at 14:37
  • $\begingroup$ Seems that Turing Machines with Oracles are the most powerful thing. Why even bother with new definitions? $\endgroup$ – saadtaame Mar 20 '13 at 19:57
0
$\begingroup$

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

|cite|improve this answer|||||
$\endgroup$
  • 2
    $\begingroup$ Perhaps you could summarize some of the points made in your link? Also, it is better if you provide a citation as well as a link, since links could move or disappear. $\endgroup$ – Yuval Filmus Aug 24 '17 at 8:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.