# Is a computational oracle physically possible?

1. Sep 14, 2011

### AlpT

def: oracle: see http://en.wikipedia.org/wiki/Oracle_machine

Question: wouldn't an oracle violate the law of conservation of energy or second law of thermodynamics, by creating a device similar to the Maxwell Demon? In other words, would being able to get information without actually computing it or acquiring it experimentally violate the second law (or first)?
Note that "computing it" or "acquiring it" are correlated but different, in the first case you could use the oracle, for example, in this way: you measure position and velocity of all the molecules, then you use the oracle to "cheat compute" their new positions and velocities without actually spending a bit of energy. In the second case, you don't even care of measuring the initial conditions of the experiment, you just ask the oracle what you need (this would be a "physical oracle").

As far as I know, it seems to me that the answer is positive: oracles cannot exist in this universe, as we know it, (i.e. with the current laws that we know).

From Wikipedia Maxwell demon: """Szilárd pointed out that a real-life Maxwell's demon would need to have some means of measuring molecular speed, and that the act of acquiring information would require an expenditure of energy. Since the demon and the gas are interacting, we must consider the total entropy of the gas and the demon combined. The expenditure of energy by the demon will cause an increase in the entropy of the demon, which will be larger than the lowering of the entropy of the gas. [...] In 1982, Bennett showed that, however well prepared, eventually the demon will run out of information storage space and must begin to erase the information it has previously gathered. Erasing information is a thermodynamically irreversible process that increases the entropy of a system. Although Bennett had reached the same conclusion as Szilard’s 1929 paper, that a Maxwellian demon could not violate the second law because entropy would be created, he had reached it for different reasons."""

2. Sep 14, 2011

### dhillonv10

Oracles are abstract constructs generally computational devices that we use to prove conjectures and so on, for instance you can give infinite computational resources to one oracle and then limited to another one and simulate the Merlin-Arthur games. They are not physical devices, the reason being that one can't give infinite power to anything. Now for proven results, such as BQP-Completness, one can say that there exist an oracle that shows that relationship and then you can construct a theoretical device to show that result (theoretical because quantum computation models are still in infancy regarding architecture).

3. Sep 14, 2011

### chronon

I don't think that an oracle would help in creating a Maxwell's demon. The work of Bennett and others suggests that computations can be done with arbitrarily small amounts of energy, and that it's the erasing of data which requires energy and defeats a Maxwell's demon.

4. Sep 14, 2011

### AlpT

dhillonv10: my question was exactly: "can we have physical oracles, i.e. can we construct one? maybe not because nothing in the universe can have infinite power and infinite computation requires infinite power. Can we prove this for example by appealing to a violation of the first/second law?".

chronon: """In 1982, Bennett showed that, however well prepared, eventually the demon will run out of information storage space and must begin to erase the information it has previously gathered.""" So, at some point you HAVE TO erase information. Erasing information is not a disposable matter. At least, this is what I understood.

5. Sep 15, 2011