I am preparing for an exam in computability and still learning about the idea of reductions. I found an interesting problem to start with and am curious if my approach is correct:

Let H0 be the halting problem starting on an empty tape, and let A be a decision problem defined as A ∶= {x ∈ N ∣ x < 10}. Show or disprove: A ⪯ H0.

We show that A ⪯ H0 via mapping reduction. Proof:

A is decidable since it is finite (A = {0,...,9}). Moreover, A must then be semi-decidable, where M specifies a Turing machine that simulates the following semi-decidable procedure for A:

M := IF x ∈ {0,...,9} THEN OUTPUT(1); ELSE LOOP infinity;

Let f be a computable function that maps each input x to a Turing machine M' defined as follows:

M' :=
INPUT(ε) (i.e., M' starts on an empty tape)
1.) Simulate M on x.
2.) Halt. (i.e., accept x)

It now holds that x ∈ A ⇔ M halts on x ⇔ M' halts on ε ⇔ M' (=f(x)) ∈ H0.


Any help or confirmation of correctness is appreciated as I am still trying to learn!



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.