Hacker News new | past | comments | ask | show | jobs | submit login

I've read a little bit about turing machines and there is also a variation that includes what is called an "oracle" machine. Do you know anything about that?



An oracle machine is usually a turing machine that can tell you things about other turing machines.

An example would be the Halting-Oracle, which can tell you if a program will halt or not without running it. (Of course, this oracle doesn't actually work since your program can have the oracle's output as input and simply do the opposite)

A NP/P Oracle might be an oracle that can tell you if a more efficient algorithm for your problem exists.

Such oracles can be setup to prove certain assumptions (or disprove) based on simply logical statements (see halting problem oracle above).

Oracle machines are also not really turing machines, it's usually assumed they can do the oracling in a single operation and they're usually a black magic box (there is no need to explain how they work, they're an abstract concept).




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: