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:. 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. 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.
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? Vardi reports on two new definitions of algorithms.
The first is proposed by Gurevich and the second by Moschovakis. 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. Computer-human collaboration in the design of graphics. Contextual Interaction Support in 3D Worlds. Interactive Algorithms with Added Appendix.
Interaction as a Framework for Modeling. A Framework for Heterotic Computing. Interactive Foundations of Computing. Elements of interaction: Turing award lecture. The Sciences of the Artificial. The mythical man-month: Essays on software engineering. Like Bahbage, he lobbied for mathematical reform, stumped for the centrality of science in cultural advancement, argued that government support was crucial, and proved a stubborn and crotchety … Expand.
The mythical man-month anniversary ed. Few books on software project management have been as influential and timeless as The Mythical Man-Month. With a blend of software engineering facts and thought-provoking opinions, Fred Brooks offers … Expand. Computing Machinery and Intelligence. The Emperor's New Mind. The growing pains of software technology are due to the fact that programming in the large is inherently interactive and cannot be expressed by or reduced to programming in the small.
The behavior of airline reservation systems and other embedded systems cannot be expressed by algorithms. Fred Brooks's persuasive argument [1] that there is no silver bullet for specifying complex systems is a consequence of the irreducibility of interactive systems to algorithms. If silver bullets are interpreted as formal or algorithmic system specifications, the nonexistence of silver bullets can actually be proved.
0コメント