I'm curious about how to build TM that decide and recognize languages defined by cardinality. For example, with the language $L_1$ = $\{w \in \{0,1\}^* | |w| = 1\}$ this is the language with a single string. It is finite so we know that is it decidable and we can build a decider $A$ that determines whether there is a DFA with at least 1 state for 1 string.

However, how to we build TMs to describe a language that isn't finite but countable infinite like $\{w \in \{0,1\}^* | |w| > 100\}$? Wouldn't this be like $\{0,1\}^*$? Even though we can represent this as a DFA with a single accept state and self loop the computation has no end in that it goes through strings forever, therefore, this would be undecidable, right? How then would we build a TM that ensures that we have at least 100 strings in this language?

  • 1
    $\begingroup$ Could you write a program to recognize it? Then it's decidable. $\endgroup$ – D.W. Jun 6 at 2:38

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.