 Suggested languages for you:

Europe

Problem 19

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

Expert verified
We are given an infinite Turing-recognizable language L with Turing machine M that accepts L. To show that L has an infinite decidable subset S, we enumerate the strings in L and construct S by including each string in the sequence if M halts and accepts it. Then we construct a Turing machine M' that decides S by checking the existence of any input string w in S. M' halts and accepts on every string in S and halts and rejects on every string not in S, proving that S is an infinite decidable subset of L.
See the step by step solution

## Step 1: Define the given language

Let L be an infinite Turing-recognizable language. This means that there is a Turing machine M that accepts L. Since L is infinite, there are infinitely many strings in L.

## Step 2: Construct the infinite decidable subset

We will construct an infinite decidable subset S of L. To do this, we will enumerate all possible strings in L and consider different lexicographic orders. Let's call the sequence of these strings as $$w_1, w_2, w_3, ...$$. We can start by constructing S with the first string $$w_1$$ in the sequence. Next, we can simulate M on the input $$w_2$$. If M halts and accepts, we can include $$w_2$$ in S. We proceed to the next string, $$w_3$$, and so on. If this process is repeated for all strings, since L is infinite, we would have an infinite sequence of strings in S. Now, we should show that S is decidable.

## Step 3: Construct a Turing machine for S

To show that S is decidable, we need to construct a Turing machine M' that decides S, meaning that it halts and accepts for every string in S and halts and rejects for every string not in S. M' can be constructed as follows: 1. Given an input string w, check if w exists in the sequence of strings included in S. 2. If w is found, halt and accept. 3. If w is not found, halt and reject.

## Step 4: Show that M' decides S

M' halts and accepts for every string in S since we know that these strings are in L and M accepts them. M' also halts and rejects for every string not in S because it checks for the existence of w in the sequence of strings included in S. M' halts on every input, and therefore, S is decidable.

## Step 5: Conclusion

We have shown that for any infinite Turing-recognizable language L, there is an infinite decidable subset S. We constructed S by considering the lexicographic order of strings in L and including them in S if M halts and accepts the input within the sequence. Then, we demonstrated that M' decides S, proving that S is decidable.

We value your feedback to improve our textbook solutions.

## Access millions of textbook solutions in one place

• Access over 3 million high quality textbook solutions
• Access our popular flashcard, quiz, mock-exam and notes features ## Join over 22 million students in learning with our Vaia App

The first learning app that truly has everything you need to ace your exams in one place.

• Flashcards & Quizzes
• AI Study Assistant
• Smart Note-Taking
• Mock-Exams
• Study Planner 