Question

Show that every infinite Turing-recognizable language has an infinite decidable subset.

Short answer

Answer

It can be shown that every infinite Turing-recognizable language has an infinite decidable subset.

Step-by-step solution

Explain Turing Machine

Turing machine is the computational model that has an unlimited memory. It has a tape that can read and write symbols as input.

Show that every infinite Turing-recognizable language has an infinite decidable subset

Consider the language A , an in Turing recognizable language. Consider that the enumerator M enumerates the language A.

Consider the language,$A_1=\{s_1,s_2,s_3,k\}$, in which $s_1$is the first string.

For very i that is greater than one, $s_1$is the first string that is lexicographically larger than $s_{i-1}$.

Assume that $A_1$is finite, then $s_i$is the last string of the language. It is also the lexicographically larger element in the language and the all other strings enumerated are less than $s_i$. Thus , it is in contradiction to the fact that the language A is infinite. So, $A_1$ is infinite and it is the subset of A

Construct the enumerator in lexicographic order L . Consider that the last string from the enumerator L be the s , initialize to a value that is placed before all the strings in a lexicographical order. Run the emulator until it emits a string n , if n > s lexicographically, then set s=n and let the lexicographic emulator L emit n .

Thus, knowing that the language is decidable if and only if enumerator enumerates the language in lexicographic order.

Therefore, that every infinite Turing-recognizable language has an infinite decidable subset has been proved. .