and let’s consider an oracle to be a function O:N×P→[0,1], such that O(┌M┐,p) specifies the probability that the oracle will return “true” when invoked on the pair (┌M┐,p)
Confusing notation. In the paragraph above, O had the type N×P→{true,false}.
We want to find an oracle machine that will output A if E[M]>E[M'], output A' if E[M]<E[M'], and output either A or B if the expectations are equal.
Should be “And output either A or A′ if the expectations are equal”, presumably.
I considered describing the probabilities of the oracle returning “true” by a different function τ(┌M┐,p), but it seemed too pedantic to have a different letter. Maybe that’s wrong, but it still feels too pedantic. If I do things that way I probably shouldn’t be writing ”O(┌M┐,p) returns ‘true’ if...”, though...
Typos & syntax complaints:
Confusing notation. In the paragraph above, O had the type N×P→{true,false}.
Should be “And output either A or A′ if the expectations are equal”, presumably.
[Will edit this post as I find more complaints.]
Fixed the typo, thanks!
I considered describing the probabilities of the oracle returning “true” by a different function τ(┌M┐,p), but it seemed too pedantic to have a different letter. Maybe that’s wrong, but it still feels too pedantic. If I do things that way I probably shouldn’t be writing ”O(┌M┐,p) returns ‘true’ if...”, though...