Turing Decidable

Question

 

Comments

srestha

The link has totally different question right?

---

Can we generate an uncountable language with finite symbols?

---

We start with a finite, nonempty set ∑ of symbols, called the alphabet. From the individual symbols we construct strings, which are finite sequences of symbols from the alphabet.

Source: PeterLinz Chapter/ Topic 1.2

With these conditions can we have an uncountable language?

Answer 1

The property of both  L1 & L2 are Trivial as

for L1 :

there exists a TM for which languages accepted by it are countable, so Tyes exists. (as we know, languages accepted by TM are countable)

There is no TM whose languages accepted by it are not countable, so Tno doesnt exist.

therefore it is not undecidable.

---

for L2,

Tyes doesnt exist => so it is straightly not undecidable.

There is no TM, whose languages accepted by it are not countable. Tyes doesnt exist

---

 

if both Tyes as well as Tno exists for a property => non trivial property => undecidable (Rice's Theorem)

 

Comments

both a, b are trivial property so it is recursive , as we know , the property is trivial if it is contains by every turing machine (1)and if it is empty (2)

for given problem ,L1, language of all turing machine is countable .so there is no uncountable language (1).

L2 is empty set (2) case so its also trivial . this is also recursive language

---

the property is trivial if it is contains by every turing machine (1)and if it is empty (2)
 

can you elaborate it ?