Turing-recognizable infinite language, decidable subset

[phoenix-anna]

Summary:: Show that every infinite Turning-recognizable language has an infinite decidable subset

Sipser's Theory of Computation, third edition, chapter three contains and exercise that asks us to demonstrate this. I don't know how to do this; I have certain ideas. We could modify the recognizer to reject strings whose prefix matches the shortest strings on which the recognizer doesn't halt. This machine would, I believe, decide a subset of the original recognized language. However, it is not clear that the resulting subset is non-empty, let alone infinite.

 

[pbuk]

1. Although this is not homework it belongs in a homework section, I'll get it moved.
2. This is not an easy question if you have not seen it before.
3. I don't think you will get there with your recogniser.

Spoiler: Hint

Try an enumerator.

 

[phoenix-anna]

Well the hint says to consider enumerators. It is clear that the recognized language is enumerable. However, it seems we need a subset that can be enumerated in a finite number of trials. If we run the enumerator 1000 times, for example, we will see 1000 or fewer strings in the language. That is a subset but it is not infinite. It seems that to get an infinite subset we would have to run the enumerator 1000 times. So I am still not seeing the answer.

 

[pbuk]

However, it seems we need a subset that can be enumerated in a finite number of trials.

Aren't we looking for an infinite subset? Anyway, let's not consider an enumerator over a subset when we haven't worked out yet how to construct any subset.

Instead, consider a lexicographic enumerator $E$ over the language $L$. Write down an arbitrary string $w$ and set $E$ running. After finite time then one of two things must happen.