5.2.3. Comparison of set P with Π*

Try these first

1. 1.

   What is a finite alphabet?

   Hint

   Think of letters of the English alphabet.

2. 2.

   What is Π*?

   Hint

   Consider how many ways you can combine letters.

3. 3.

   What does it mean for a set to be countable?

   • It can be finite
   • It can be listed with natural numbers
   • It contains infinite elements

   Hint

   Think about how you would list items.

4. 4.

   Is the set P (valid programs) countable?

   • True
   • False

   Hint

   Remember the definition of valid programs.

5. 5.

   Prove that the set of all possible strings from an alphabet {x, y, z} is countable.

   Hint

   Start with the shortest strings and build up.

6. 6.

   If you had an infinite number of valid programs, how would you ensure that each one can be included in your enumeration?

   Hint

   Analyze the structure of valid programs.