If a set S is infinite and recognizable, how can I prove that, if any, some subsets K is infinite and decidable? how about infinite and recognizable?
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ I can answer the second question: $S$ is a subset of $S$ which is infinite and recognizable. $\endgroup$– Yuval FilmusCommented Feb 26, 2014 at 3:13
-
$\begingroup$ 1. "if any"? "some subsets"? I can't understand what you are asking. Would you like to try rephrasing? 2. We expect people to make a serious effort on their own before asking here, and to show us what they have tried. So, what have you tried? How have you tried to prove it? $\endgroup$– D.W. ♦Commented Feb 26, 2014 at 6:06
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
The second question is the easier one, we can just pick any string $\varsigma$ in the infinite Turing recognizable language $S$, and let $S' = S\setminus\{\varsigma\}$. Then you should be able to construct a TM that recognizes $S'$ from the recognizer $R$ for $S$.
The normal proof for the first question is trickier, relying on two facts:
- Every Turing recognizable language has an enumerator (a TM that prints out the strings in the language one by one).
- If a language has a lexicographic enumerator (a TM that enumerates the strings in the language in lexicographic order), then it is decidable.
So you start with $S$, which must have an enumerator $E$ that prints out, one by one, the strings in $S$ in some order, which may include repeats. What you have to do is construct a lexicographic enumerator using $E$ as a subroutine. It doesn't have to print out everything in $S$, just a subset of course, the trick is to ensure that the ones it prints are in lexicographic order. As noted Jeremy West in the comments, we must also ensure that the subset is infinite, this is easy enough, just not to be forgotten.
answered Feb 26, 2014 at 3:13
-
1$\begingroup$ And then, of course, you must prove that the lexicographic subset is infinite. $\endgroup$ Commented Feb 26, 2014 at 5:47
-
1$\begingroup$ @JeremyWest yes, a point worth ... pointing out. $\endgroup$ Commented Feb 26, 2014 at 6:15
-
1$\begingroup$ @JeremyWest, if $S$ is infinite and has an enumerator that lists all its strings, once it has output $\alpha$, it can't go on indefinitely generating strings less than $\alpha$ (if it did, its output would be finite). $\endgroup$– vonbrandCommented Feb 26, 2014 at 12:53
-
$\begingroup$ Yeah, the proof isn't hard, but worth mentioning. $\endgroup$ Commented Feb 27, 2014 at 12:58
-
2$\begingroup$ @Raphael, it's not for the whole set, it's "just" for an infinite subset - you just let $E$ run, if it spits out a string that is after (lexicographically) the last one you output, then you output it, otherwise you ignore it. You get the infinite part essentially for free as for any given string, there is only a finite number of strings before it lexicographically, so eventually $E$ produces something after it. $\endgroup$ Commented Apr 9, 2016 at 13:55