5.1.5. Ordering strings based on summation of indices

Try these first

1. 1.

   What is a countable set?

   Hint

   Think about how you can count elements in a set.

2. 2.

   Define an alphabet.

   Hint

   What symbols can you think of in a language or code?

3. 3.

   What characterizes a countable set?

   • It has no elements
   • It can be listed in a sequence
   • It only contains finite elements

   Hint

   Think about what it means to count an infinite set.

4. 4.

   True or False: The set of all valid programs in a programming language is uncountable.

   • True
   • False

   Hint

   Consider the finite nature of construction in programming.

5. 5.

   Given an alphabet {d, e, f, g}, generate the strings of length 3 and explain how many valid sequences can be constructed.

   Hint

   Think about the number of combinations of each letter.

6. 6.

   Explain why the action of inserting a valid instruction into existing valid programs keeps the set of valid programs countable.

   Hint

   Consider how each new insertion is still finite.