People in theoretical computer science and especially people in quantum computing keep talking about oracle machines to describe theoretical solutions to diffrent types of problems.
Basically an oracle machine for a given problem is an (Turing machine) algorithm that take in an input and tell if the input is a solution to a given problem, but without actually giving a general solution to the problem in general (Because if we have the general solution, just calculate it instead of consulting the oracle). The classic layman's example given is: suppose we have a phone book, and we want to search for a person given his phone number (instead of searching for a phone number given a person). We can check for a given name wether it corresponds to the desired phone number or not, but we can't "calculate" the name form the number.

More specifically, in the case of digital computer the oracle would be a black-box function that takes a binary string :

x=(x1,x2,....xn) as an input
and returns f(x)=1 if x is a solution and f(x)=0 if not,
and we can access this orcale without knowing how to calculate the solution ourselves.

This type of hypothetical function is used in a lot of papers, especially Grover's famous quantum search algorithm for quantum computers.
But none of the papers I've read actually mention how to find a concrete useful oracle machine or construct one for a given problem. It seems to me that if we can construct such a machine, then we already know the solution in the first place.
Can anyone think of an actual, non-trivial, useful oracle machine that can be expressed in mathematical terms (No phone books)?