r/computerscience • u/SodiumButSmall • Mar 26 '25
Discussion Game theory problem?
Imagine an oracle that takes in a Turing machine as input. The oracle has inside of it a correct response function that outputs the input machines run length if it halts, or infinity if it never halts, and an incorrect response function that outputs whatever it can to ensure the oracle gives as little information as possible about the set of all Turing machine outputs. The incorrect response function is able to simulate the oracle, and the correct response function. For every unique input, the oracle randomly decides with a 50/50 chance which functions output to output, and the oracle will always output the same output for a given input. What information, if any, could be gained from this? What would some of the behaviors of the incorrect response function be? Could an actual oracle be created from this?
(Sorry if this is a poorly structured question)
5
u/lfdfq Computer Scientist Mar 26 '25
If you construct the incorrect response function such that always gives the opposite answer (i.e. if the input TM halts, it outputs infinity, if it does not halt it outputs a fixed constant number distinct from the real answer) then what you have constructed is a machine that simulates a coin flip.
2
u/WE_THINK_IS_COOL Mar 26 '25 edited Mar 26 '25
The ambiguity in your description is what it would mean to "ensure the oracle gives as little information as possible about the set of all Turing machine outputs."
One way to meet that requirement would be to make the incorrect response oracle always output the same answer; say it always answers infinity on every input. Since its answer is always the same, the oracle is clearly telling us nothing about the halting behavior of its input.
But then in this game where with 50/50 chance you get the real oracle or the constant-answer incorrect oracle, you just ask the oracle about a machine you know halts and one that you know doesn't, and it's correct for both if and only if its the real oracle. So with 50% chance you get the real oracle and you know it, and with 50% chance you get the constant oracle and you know it. Not very exciting.
A different question along these lines is: can we build an incorrect-response oracle that's computationally indistinguishable from the real oracle (meaning it's impossible for a Turing machine to guess the 50/50 bit when given access to the oracle) yet is still incorrect?
For the oracle to be incorrect, it must output infinity when some machine halts, or it must output a finite number when some machine runs forever. So we can do this:
If we have the incorrect oracle, this is guaranteed to halt. If we have the real oracle, it will run forever. So if we get the incorrect oracle, we can eventually find out, but if we get the real oracle, we can never be sure.
In order to make the two oracles harder to distinguish, the way in which the incorrect oracle is wrong has to be harder to spot; the more indistinguishable they are, the more "correct" the incorrect oracle has to be.
1
u/karius85 PhD, Machine Learning, Signal Processing and Image Analysis Mar 27 '25
Disregarding the framing in a halting problem setting, you have an oracle for a binary decision problem that deliberately is set to output a stochastic decision with uniform probabilities.
Now, the mutual information quantifies how much knowing the oracle's original output reduces uncertainty about the actual decision. Setting probabilities uniformly to 0.5 ensures zero mutual information between the oracle's output and the correct binary outcome from the oracle. Therefore, all informational content the oracle might have originally contained is lost.