Hacker News Reader

Comment by forinti | Hacker News Reader

Please look up http://en.wikipedia.org/wiki/Oracle_machine.

The purpose of a machine with interactions is not to be more intelligent, it is just to be able to execute a larger body of computations than a machine without interactions would. You can't model operating systems on Turing machines, for example, precisely because they need to interact.

This is from the Wikipedia entry on Alan Turing:

"In June 1938 he obtained his Ph.D. from Princeton; his dissertation introduced the notion of relative computing, where Turing machines are augmented with so-called oracles, allowing a study of problems that cannot be solved by a Turing machine."

View on HN

Right, oracle machines are - or can be interpreted as - interactive. However, whatever it is that oracles do - it's often called "hypercomputation" - they're not doing computation, in the sense that Turing used the term in "On computable numbers...", which is why Turing couldn't prove that they are more powerful. The apparent - to me - problem here is that people use a definition of "computation" which is different from Turing's (which is alright), and then say that Turing was "wrong" in what he said about "computation" (which is not alright).

I actually think that operating systems are a good example of how interaction can be less powerful than algorithm - the "oracle" in this case might be a user, and the user might be new to computers, so that in this case the result of the interaction might be worse than if the "oracle" were another (non-human) computer, the interaction with which might in turn give a worse result than if you were the "oracle".

The object of this study is not to prove that all forms of interaction are better than algorithmic computing, it is to prove that machines that interact during computation can execute a larger set of computations.

You also insist in factoring in intelligence, which is not at all revelant to this discussion. This is about which sets of functions can be executed with which machines.

Oracle machines are capacle of executing all functions that a Turing machine can (if you simply shut off interaction) and also all those that involve interaction. Having been proved that the latter set of functions is larger than the first, we can conclude that oracle machines are more powerful.

Reply on news.ycombinator.com