oracle machine noun1 •In computability theory, a form of theoretical Turing machine, able to solve even undecidable decision problems in a single operation. formsoracle machines