I want to give a mapping reduction (many-to-one) using the Empty_TM which accepts nothing, so the accept state is a useless state. This is to show that useless_TM is undecidable.

A state q in a TM M is said to be useless if this state is never reached when M is executed on any string ω ∈ Σ*.

Note: I want the description of the reduction and not the computable function f: Σ* --> Σ*


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.