0
$\begingroup$

We were taught to use reductions in order to show that a given L is undecidable. My question is, given some definition of a new L, is there a way to find a reduction $$ L\leq_mHALT $$ So that I can determine $L \in RE$? More specifically, given the quite common problem of the decidability of $$ L=\{\langle M\rangle | |L(M)| ≥ 5\} $$ (Or any other natural number instead of 5)

All proofs I've seen online construct a TM that uses dovetailing so I was wondering if there is a different way to solve this problem, specifically using a reduction.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

You can get a reduction from the proofs you've seen. Construct a TM $M_L$ which uses dovetailing to count how many inputs a given TM $M$ accepts and let $M_L$ halt once that counter reaches a value $\geq 5$. Thus, $M_L$ halts on input $\langle M \rangle$ if and only if $\langle M \rangle \in L$, yielding the desired reduction.

I don't see an easier reduction for this problem.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.