1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ all regular languages are recursive. The opposite is incorrect. Make sure you don't confuse the (overloaded) term "finite". see: cs.stackexchange.com/questions/6609/… $\endgroup$ – Ran G. May 6 '15 at 22:15
  • $\begingroup$ I also don't understand what additional misunderstanding you have on top of your previous related(dup) question: cs.stackexchange.com/questions/41963/… $\endgroup$ – Ran G. May 6 '15 at 22:19
  • $\begingroup$ for finite I mean that the number of words in L is finite $\endgroup$ – revisingcomplexity May 6 '15 at 22:26
  • 1
    $\begingroup$ Then you probably know that every finite language is regular -> recursive = decidable. It has a trivial DFA that accepts it and a very simple TM that accepts it. $\endgroup$ – Ran G. May 6 '15 at 22:30
  • $\begingroup$ I don't see how this is a duplicate of the question about the possibility of uncoubtable languages. Asking if all recursive langauges are finite is almost the opposite of asking if they can be uncountable and the answer to the other question doesn't seem to answer this one. $\endgroup$ – David Richerby May 7 '15 at 6:56
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ this means that the language I described is r.e.? $\endgroup$ – revisingcomplexity May 6 '15 at 22:25
  • $\begingroup$ Your particular example is decidable. $\endgroup$ – Yuval Filmus May 6 '15 at 22:27
3
$\begingroup$

Yes, a Turing machine can decide that langauge: it just looks at the first character and accepts or rejects without even needing to look at the rest of the string.

The question "Are all recursive languages finite?" is not a generalization of "Is this particular infinite language recursive?" The fact that $\{ax\mid x\in\Sigma^*\}$ is recursive (decided by a Turing machine) and infinite (contains infinitely many strings) already shows that the answer to "Are all recursive languages finite?" is no.

To enumerate the strings in a language informally means to write them all down in a list but, as you've observed, this informal definition doesn't make a whole lot of sense if the language is infinite: you'd never finish. What we require is that, although the process of listing the strings in the langauge takes infinitely long, any single string in the language must be guaranteed to appear after a finite amount of time.

So, for example, 1, 2, 3, ... is an enumeration of the natural numbers. You'll never finish writing down the list but, if I pick a natural number (say, 2,938,427,365), I'll only have to wait a finite amount of time until you write that number. Conversely, if I pick something that isn't a natural number (e.g., a frog), I'm guaranteed that you'll never write that down. By way of a non-example, listing all the even numbers, then all the odd numbers isn't an enumeration of the naturals: you'll never finish writing the evens, so you'll never start writing the odds, so 1 will not appear in any finite amount of time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.