Are all infinite languages undecidable?

turing-machines computation-theory language-theory
user1974753 picture user1974753 · Feb 13, 2013 · Viewed 7.2k times · Source

I am wondering are all infinite languages undecidable?

They must be right, as the TM trying to decide an infinite language would just loop forever, which makes it a recgonizer, not a decider.

Thanks guys.

Answer

sepp2k picture sepp2k · Feb 13, 2013

No, there are many infinite languages that are decidable. One trivial example is the language {n € N | a^n}, i.e. the language of words that only contain the letter "a". This language can be matched by the regular expression a*. so it is a regular language and thus decidable.

Related questions

What is the difference between recursive and recursively enumerable languages

I was wondering what the difference between recursive and recursively enumerable languages is in terms of halting and Turing Machines. I know that recursively enumerable languages are a subset of recursive languages but I'm not sure about the difference beyond …

Read More
Difference between Turing-Decidable and Co-Turing-Decidable

I am really struggling with understanding the difference between these two. From my textbook, it essentially describes the difference by saying a language is co-turing recognizable if it is complement of a turing-recognizable language. I guess the part of this …

Read More
Real world uses of DFA,NFA,PDA and Turing machines

I am now taking a course on Theory of Computation. I can understand the concepts well. I can able to solve the problems. And, when I asked my instructor about the real world application, he told me these concepts will …

Read More