Question

INFINITETM = {〈M〉| M is a TM and L(M) is an infinite language}. Is it co-Turing-recognizable?...

INFINITETM = {〈M〉| M is a TM and L(M) is an infinite language}. Is it co-Turing-recognizable? prove your answer.

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

Answer:

Let's prove this by Rice's theorem.

INFINITETM is the language of TM descriptions.

Given language satisfies the two conditions of Rice's theorem.

a) It is non-trivial because some TMs have infinite language and others dont have.

b) It depends only on the language.

As we know that of two TMs reconise the same language, either both have descriptions in INFINITETM or neither do.

Consequenty, Rice's theorem implies that INFINITETM does not satisfy co-Turing-recognizable

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Prove that the following language is undecidable: L = { 〈M〉 | M is a Turing...
Prove that the following language is undecidable: L = { 〈M〉 | M is a Turing machine that accepts all strings of length at most 5}
Consider the language defined by L = {aibmcn | i > 0, n > m >...
Consider the language defined by L = {aibmcn | i > 0, n > m > 0 } Is L regular or not? Prove it
Prove that if a language L is regular, the suffix language of L is also regular.
Prove that if a language L is regular, the suffix language of L is also regular.
5 A Non-Regular language Prove that the language}L={www∣w∈{0,1}​∗​​} is not regular.
5 A Non-Regular language Prove that the language}L={www∣w∈{0,1}​∗​​} is not regular.
For Automata class: Let L be a regular language over the binary alphabet. Consider the following...
For Automata class: Let L be a regular language over the binary alphabet. Consider the following language over the same alphabet: L' = {w | |w| = |u| for some u ∈ L}. Prove that L' is regular.
The chopleft operation of a regular language L is removing the leftmost symbol of every string...
The chopleft operation of a regular language L is removing the leftmost symbol of every string in L: chopleft(L) = { w | vw ∈ L, with |v| = 1}. Prove or disprove that the family of regular languages is closed under the chopleft operation.    Hint: If it’s regular, give an idea of constructing an FA that accepts chopleft(L) using an FA M that accepts L. Otherwise, give a counterexample.
Do a Push Down Automata for the following language: L = { 0n1m2m3n | n>=1, m>=1}...
Do a Push Down Automata for the following language: L = { 0n1m2m3n | n>=1, m>=1} Show your work please.
Prove by induction on n that if L is a language and R is a regular...
Prove by induction on n that if L is a language and R is a regular expression such that L = L(R) then there exists a regular expression Rn such that L(Rn) = L n. Be sure to use the fact that if R1 and R2 are regular expressions then L(R1R2) = L(R1) · L(R2).
Turing and Wittgenstein seem to agree that if you run into a contradiction, then anything might...
Turing and Wittgenstein seem to agree that if you run into a contradiction, then anything might happen. In other words, any logic that is inconsistent is also trivial in the sense that every sentence may be proved. Could there be a logic in which it is not possible to prove every sentence from a contradiction? What might such a logic look like? Explain your answer.
Prove the language of strings over {a, b} of the form (b^m)(a^n) , 0 ≤ m...
Prove the language of strings over {a, b} of the form (b^m)(a^n) , 0 ≤ m < n-2 isn’t regular. (I'm using the ^ notation but your free to make yours bman instead of (b^m)(a^n) ) Use the pumping lemma for regular languages.
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT