2 ms·
Right, oracle machines are - or can be interpreted as - interactive. However, whatever it is that oracles do - it's often called "hypercomputation" - they're no
by dhs 17y ago
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".
- forinti 17y agoThe 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.