Decidable (or solvable) problems:
Definition:
If fe is a reasonable encoding of a decision problem P over Σ, we say P is decidable if the associated language {fe(X)| X is a yes-instance of P} is recursive.
A problem P is undecidable) if P is not decidable.
Self-Accepting
- SA (Self-accepting) = {wÎ{0,1,#, ,}*| w=e(T) for some TM T and wÎL(T)}
- NSA (Non-self-accepting) = {wÎ {0,1,#, ,}*| w=e(T) for some TM T and wÏL(T)}
- E (Encoded-TM) = {wÎ{0,1,#, ,}*| w=e(T) for some TM T}
NSA is not recursively enumerable
We prove by contradiction.
Assume NSA is recursively enumerable . Then, there is TM T0 such that L(T0)=NSA. Is e(T0) in NSA?
- If e(T0)∈NSA, then e(T0)∈L(T0) by definition of NSA But
L(T0)=NSA. Hence, contradiction.
- If e(T0)∈NSA, then e(T0) ∈SA and e(T0)∈L(T0) by definition of SA. But L(T0)=NSA. Hence, contradiction.
Then, the assumption is not true. Which means that, NSA is not recursively enumerable.
Email based Automata assignment help - homework help
The study of automata is an important area of theory of computation. Students feel trouble in solving automata questions. We at www.expertsmind.com offers Automata assignment help - Automata homework help and online tutoring with best qualified and experienced computer science tutor's help. We cover all topics including Decidable problems in assignment help - homework help service. Get solved problems in automata theory with step by step answers anytime from expert tutors at expertsmind.