Example
Let denote the set of input values for which the Turing machine with index e halts. Then the sets and are Turing equivalent (here denotes an effective pairing function). A reduction showing can be constructed using the fact that . Given a pair, a new index can be constructed using the smn theorem such that the program coded by ignores its input and merely simulates the computation of the machine with index e on input n. In particular, the machine with index either halts on every input or halts on no input. Thus holds for all e and n. Because the function i is computable, this shows . The reductions presented here are not only Turing reductions but many-one reductions, discussed below.
Read more about this topic: Turing Reduction
Famous quotes containing the word example:
“Our intellect is not the most subtle, the most powerful, the most appropriate, instrument for revealing the truth. It is life that, little by little, example by example, permits us to see that what is most important to our heart, or to our mind, is learned not by reasoning but through other agencies. Then it is that the intellect, observing their superiority, abdicates its control to them upon reasoned grounds and agrees to become their collaborator and lackey.”
—Marcel Proust (1871–1922)