[Solved]: Doubts about infinite language decided by a turing machine

Problem Detail: 

Assume you have an infinite language $L$ over alphabet $\Sigma=\{a,b\}$ For example, $L=\{ax \mid x \in \Sigma^*\}$

Can a Turing Machine, $M$ decide this language?

(Generalizing, are all the recursive languages finite?)

In my opinion, it can, since I can enumerate all the strings and say if they are in the language or not. However, enumerating all the strings will take infinite amount of time, so I will never end up enumerating them.

Can someone clarify this doubt?

Asked By : revisingcomplexity

Answered By : Yuval Filmus

Some infinite languages are decidable, some are not. The algorithm that you give, however, doesn't work, for two reasons:

1. When the input is not in a language, you never find out.

2. It is not always possible to enumerate all the words in $L$. A language $L$ for which this is possible is known as recursively enumerable (r.e.), and by many other terms. An example of a language which is not r.e. is the language of encodings of Turing machines which don't halt on the empty input. That is, $\langle M \rangle$ is in the language if $M$ never halts when running on the empty input.

In your specific example, there is a very simple Turing machine accepting $L$. The Turing machine examines the first symbol, accepts if it is $a$, and rejects otherwise.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42235

3.2K people like this

 Download Related Notes/Documents