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?
Doubts about infinite language decided by a turing machine
turing machines
Some infinite languages are decidable, some are not. The algorithm that you give, however, doesn't work, for two reasons:When the input is not in a language, you never find out.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.