Prove: Every decidable set is Turing reducible to the empty set

Question

Question- Prove: Every decidable set is Turing reducible to the empty set.

Can anyone help me with this please?

All reductions tutorials I've seen use practical examples of reduction such as sipser's introduction to computation theory:

"A reduction is a way of converting one problem to another problem in such a way that a solution to the second problem can be used to solve the first problem. ... For example, suppose that you want to find your way around a new city. You know that doing so would be easy if you had a map. Thus, you can reduce the problem of finding your way around the city to the problem of obtaining a map of the city"

I don't see how to use this kind of information as a general proof, or how the empty set is even usable to solve anything else in a practical example even.

Answer 1

You're trying to prove something, so you need to use something closer to an actual definition of Turing reducibility. The statement you quote from Sipser is an intuition about what reductions do, but it's not precise enough to let you solve problems.

Here's an informal definition of Turing reducibility that lets you start to reason about what it can do.

A set $A$ is Turing-reducible to a set $B$ if, assuming the existence of a subroutine that determines whether its input is in $B$, we can write a program that determines whether its input is in $A$.

We're considering $B=\emptyset$, so we need to assume the existence of a subroutine that determines whether its input is in $\emptyset$. Well, that's not much to assume. Here's the subroutine:

 return false

OK – we don't need to assume anything: we know this subroutine exists. So now, we just need to show that every decidable set is Turing reducible to $\emptyset$. That is, we need to show that

For every decidable set $A$, we can write a program that determines whether its input is in $A$.

So... what's the definition of decidable?

Answer 2

2 languages A and B. If B is <= t A, then A is <=t B. run A on B until {}, if A is {} (empty), then B is {}.