Editing Turing reduction (section)

== Example ==

Let <math>W_e</math> denote the set of input values for which the Turing machine with index ''e'' halts.  Then the sets <math>A = \{e \mid e \in W_e\}</math> and <math>B = \{(e,n) \mid n \in W_e \}</math> are Turing equivalent (here <math>(-,-)</math> denotes an effective [[pairing function]]).  A reduction showing <math>A \leq_T B</math> can be constructed using the fact that <math>e \in A \Leftrightarrow (e,e) \in B</math>.  Given a pair <math>(e,n)</math>, a new index <math>i(e,n)</math> can be constructed using the [[Smn theorem|s<sub>mn</sub> theorem]] such that the program coded by <math>i(e,n)</math> ignores its input and merely simulates the computation of the machine with index ''e'' on input ''n''.  In particular, the machine with index <math>i(e,n)</math> either halts on every input or halts on no input.  Thus <math>i(e,n) \in A \Leftrightarrow (e,n) \in B</math> holds for all ''e'' and ''n''.  Because the function ''i'' is computable, this shows <math>B \leq_T A</math>.  The reductions presented here are not only Turing reductions but ''many-one reductions'', discussed below.