CampusProgram.com: University, College and Employment Resources that Guide you from High School to your Dream Job.

MENUHomeUniversitiesCollegesProgramsJobsLibraryArticlesStore
Google
 
Web www.campusprogram.com

Oracle Machine

Wikipedia Reference Information

An oracle machine is a Turing machine connected to an oracle. The Turing machine can write on its own tape an input for the oracle, then tell the oracle to execute. In a single step, the oracle computes its function, erases its input, and writes its output to the tape. Sometimes the Turing machine is described as having two tapes, one of which is reserved for oracle inputs and one for outputs.

In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single step. The problem can be of any complexity class. Even undecidable problems, like the halting problem, can be used.

The complete, up-to-date and editable article about Oracle Machine can be found at Wikipedia: Oracle Machine
http://en.wikipedia.org/wiki/Oracle_machine




MENUHomeUniversitiesCollegesProgramsJobsLibraryArticlesStore
Google
 
Web www.campusprogram.com

Copyright 1996-2007 - CampusProgram.com