CSci 301 Lecture Notes

Week Ten, Tuesday: Turing Reducibility

Oracle

An oracle in the theory of computation sense has a "magical ability" to decide whether a string is a member of a language. Do not confuse this with an oracle in the software engineering sense that is a problem for which one knows the answer for software testing purposes.

Example 6.17: We want to decide if M accepts no strings. We construct N that runs M in parallel on all strings. M may loop on all inputs, in which case it will not halt (it's not by itself a decider of the empty TM). If M accepts any string, N accepts. Now query the oracle to see if N is an accepter of anything. If it is, then M's language is not empty. If the oracle says that N is not an acceptor of any string then we "accept" M as member of the class of machines that accepts no strings.

This is an example of using an imaginary oracle to establish relative decidability.

Email: Richard dot J dot Wagner at gmail dot com