1
$\begingroup$

I am having difficulty understanding the difference between PAC and Oracle Machines. I cannot compare these two in terms of uncertainty and physical effort.

The degree of uncertainty we can tolerate in a system has been discussed ever since Turing. His oracle machines answer questions with maximal uncertainty, and zero physical work, because they are oracles. They don't have to justify their answers.

His automatic machines, or a-machines, are what we now call standard TM. In the probabilistic version, there is no new class of functions that we can compute which we cannot compute with deterministic TM. The Probabilistic TM can decide which route to take depending on probabilities assigned to its transitions. In the simplest case of binary branching at every state and total random choice, it flips a coin about which route to take. We know that in doing so we don't get anymore computable function than what we get with nondeterministic TM, but we might get to some answers more quickly.

PAC idea, however, changes things. 1-epsilon is the amount of uncertainty a PAC problem solver can tolerate in calling a solution 'approximately' correct. If epsilon=0, then you get maximal tolerance.

How this idea can be related to Turing's oracle, and to relation between certainty and amount of physical effort.

$\endgroup$
3
  • $\begingroup$ Can you elaborate on what PAC is? $\endgroup$
    – nir shahar
    Apr 25 at 13:51
  • $\begingroup$ His automatic machines, or a-machines, are what we now call standard TM. In the probabilistic version, there is no new class of functions that we can compute which we cannot compute with deterministic TM. The Probabilistic TM can decide which route to take depending on probabilities assigned to its transitions. In the simplest case PAC idea, changes things. 1-epsilon is the amount of uncertainty a PAC problem solver can tolerate in calling a solution 'approximately' correct. If epsilon=0, then you get maximal tolerance. $\endgroup$
    – Athena
    Apr 25 at 14:06
  • $\begingroup$ Instead of asking about differences, I suggest you first make sure understand each concept on its own. Once you understand both concepts, you should be able to work out the differences on your own. I encourage you to edit your question to include a definition of what you mean by the acronym "PAC". Also it would help to give a more specific question. "How this idea can be related to Turing's oracle" is pretty vague; it's hard to tell what kind of relationship you are looking for. They are two different concepts. $\endgroup$
    – D.W.
    Apr 25 at 22:05
0
$\begingroup$

An oracle access to a random oracle can simulate the effect probabilistic TM's have. However, oracle machines aren't limited to using a random oracle, you can specify whatever oracle you would like, to any problem - no matter how hard the problem is, and a TM with an oracle access to it would solve it in constant time.

So, in this line of thinking - an oracle machine can be thought of as a really general extension of the probabilistic case.

I don't know if this answered your question, but I hope I managed to help a little!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.