A question about many-one reducibility of two sets

70 Views Asked by At

We want to show that $ \big\{x:W_{x}$ is finite }$=Fin \leq _m Cof=\big\{x : W_{x}$ is cofinite}. But I really have not any idea.

Would be grateful for your help.

1

There are 1 best solutions below

2
On

Suppose $T$ is some Turing machine, and construct this $U$:

read (y,n);
simulate T on input y for n steps;
if T halts after exactly n steps
   then loop forever
   else halt