Thread: Oracles in computer science

Hello.

I'm not sure this is the right section but here it goes. I'm having a lot of trouble understanding the notion of an oracle in computer science. In his lecture notes, the teacher defines an oracle for a function f (in Mathematica language) as

Function[n,
Function[x,
Print[ToString[Oracle],n,ToString[on],x];
a=Input[];
If[IntegerQ[a]&&a>=0,
y=a,
While[True,Null[]]];
y
]
]

Now, my guess is that the input we provide is the image of the function which has the oracle. Is this right? Could you please give me an intuition of what's going on here?

Thanks in advance.

I am not familiar with Mathematica language. Could you explain what this code is doing?

This description of a Turing machine with an oracle seems pretty clear.

Also, you can use [code]...[/code] tags to preserve formatting and indentation.

Ok. I've reread that article on wikipedia and I'm still confused as to how it applies to my particular book.

I'll try to explain the code to you:

It starts as a function on n. Inside it, it's defined a second function, on x, that does the following: it prints "Oracle n on x"; it asks for an imput (a); if the input is a natural number the output is y=a or else the function enters in an infinite loop.
So it's a function on n that, once evaluated on n, is a function on x that basicaly asks for an imput and if it's a natural number the input becomes the output.

I hope that was clear.