# What are the differences between Oracle Turing Machine and PAC?

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.

• Can you elaborate on what PAC is? Apr 25 at 13:51
• 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. Apr 25 at 14:06
• 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.
– D.W.
Apr 25 at 22:05