5.2.1. Set of Valid Programs in a Programming Language

Try these first

1. 1.

   What does it mean for a set to be countable?

   Hint

   Think about how you could list natural numbers.

2. 2.

   Define a valid program in programming languages.

   Hint

   Consider the beginning and end instructions of a program.

3. 3.

   A set is countable if:

   • It has a finite number of elements
   • It can be listed using natural numbers
   • It has no elements

   Hint

   Recall our definition of countability.

4. 4.

   True or False: All strings over a finite alphabet form a countable set.

   • True
   • False

   Hint

   Think about how we listed the strings.

5. 5.

   Design a valid program using a made-up programming language that includes at least three distinct commands.

   Hint

   Focus on ensuring your program has a start and a syntax that makes sense.

6. 6.

   Prove that there are infinitely many programs even within a constrained limited programming language.

   Hint

   Consider how you can add new steps between the start and end.