History and Philosophy of Computing
Exercise 1. Give an example of a set with zero elements. Give an example of a finite non-empty set.
Exercise 2. Define what the cardinality of a set is and compare the cardinalities of the two sets defined in the previous exercise.
Exercise 3. Consider the following sentence: "This sentence is false". Do you think this is a paradox? Why?
Exercise 4. The logical notion of type for an expression was used to resolve Frege's contradiction. Typing is widely used in Computer Science. Can you explain what a type is for a programming language? Can you explain how a type expression in a given programming language helps avoiding some errors in the process of running a program?
Exercise 5. Think about the idea of a procedure that is well-defined for each of its steps: which notion in Computer Science reflects the same idea?
Exercise 6. Formulate a small algorithm in some programming language or in pseudo-code to add a natural number to its successor; then add the result to its successor; and so on. Can you ever make it list in full an infinite set of elements? What does that mean for the process of computation?
Exercise 7. Consider a computer program whose signature is of type INT → BOOL stating for any n ∈ INT, whether n is odd or even. Write a program in a programming langauge or pseudo-code to this aim. Does this program answers a decision problem? Is the problem of checking if a number is odd or even decidable (i.e. can you always have an answer to that question)?