table of contents

turing reducibility

2024-05-05

one problem is reducible to another if a method for solving the second problem yields a method for solving the first.

let be sets. is many-one reducible to , written , if there is a computable function such that that is, iff . (the word many-one simply refers to the fact that we do not require to be one-one.)

a reduction function has to be a total computable function.

if and is computable then is computable.

suppose .

let . if is noncomputable, then is also noncomputable. if isnt computably enumerable then is also not computably enumerable.

we can use the reducibility arguments to show that certain sets are not r.e. let

is not r.e.

consider the function this function acts as a reduction from to . for every program number (i.e. is the encoding of a program ), the function returns the code of the following program : ignores its inputs and runs the given program on .

the given reduction function is computable: we can write an algorithm that receives and returns the encoding of the program (the encoding function should be computable).

we have :

if and , then .

if is -complete, is r.e. and , then is -complete.

if then .

the proof is trivial, assuming there is a reduction function for , the same reduction function can be used for the reduction .