Register

MP481 Review Problems Turing Machines and (Un)Decidability Luay K. Nakhleh

• reshown by
268 views
0 votes
0 votes
L1={<M>|M is a TM and |L(M)|<=3}

L2={<M>|M is a TM and |L(M)|>=3}

L3={<M>|M is a TM and L(M) is finite}

How can we  judge  which language is rec, R. E or not R. E?
• reshown by
User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
1
daksirp asked Jul 31, 2018
892 views
TOC : Turing Machines, Decidability
Consider <M> be the encoding of a Turing Machine as a string over alphabet Σ = {0, 1}. Consider L = {<M>⏐M is TM that halt on all input and L(M) = L′ for some undecidable language L′}. Then L is .... can anyone explain the sentence in Bold and bold & italics ?? i didnt get L(M).
Consider <M be the encoding of a Turing Machine as a string over alphabet Σ = {0, 1}. Consider L = {<M>⏐M is TM that halt on all input and L(M) = L′ for some undecid...
User Avatar
2 votes
2 votes
2 answers
3
rahul sharma 5 asked Aug 7, 2017
667 views
Turing machines decidability
Check whether the language below is recursive, recursively enumerable but not recursive, or not recursively enumerable? {⟨M1,M2⟩∣ M1 and M2 are two TMs, and ϵ∈L(M1)∖L(M2)}.
Check whether the language below is recursive, recursively enumerable but not recursive, or not recursively enumerable?{⟨M1,M2⟩∣ M1 and M2 are two TMs, and ϵ∈L(M...
User Avatar
Link Copied!