HW2

Homework 2: A Paradox, Induction, and Research Basics

Due Monday Sep 27 at 17:00

Deadline: Monday Sep 27, 17:00. Please remember that you must submit the assignment separately
in Canvas (for grading) and Peergrade (for peer review)! The Peergrade submission can be found as a 
separate Canvas assignment called Homework 2 HT2021- peer review submission.

Please submit your work as a pdf-file. We recommend using LaTeX for the submission since this is
a standard tool for scientific writing which should be practiced ahead of your master's thesis.

In the peer review submission, you may if you wish submit it anonymously, but the Canvas submission
must contain your name.

It is important to give full answers with careful motivation. When you make use of a result or idea
that is due to someone else, you should make use of references as in a scientific text. References should
primarily be to original publications, not to textbooks or similar. Please collect your references in a reference
list at the end of the text. Referencing will be reviewed more later in the course - in the meantime you 
could take a look, e.g., at a guide for the IEEE format such as this.

Also note that standard rules against plagiarism apply - you cannot copy text from other sources
(published material, the work of other students, etc) except in the form of explicit quotes with sources
given.

And a general comment after reviewing submissions to HW1: The length of the submissions varied a lot between
students. Some wrote quite long, and very interesting and detailed essay answers. This is very nice and appreciated,
but often one can give more concise but still well-motivated answers and pass the assignment anyway -
we understand that you have other obligations as well. On the other hand, a few students gave too brief and insufficiently
motivated answers. So, I suggest trying to find a middle ground - a couple of pages will suffice for most assignments.

Suggested reading:

• See the reading list (textbooks Ladyman and Walliman), for lecture 2.
• Lecture notes from lecture 2.
• Zeno's paradoxes (Links to an external site.) (Wikipedia)
• Raven paradox (Links to an external site.) (Wikipedia)

Optional reading:

Jorge Luis Borges, The Perpetual Race of Achilles and the Tortoise, see  AchillesTortoise.pdf Download AchillesTortoise.pdf

1. Achilles and the Tortoise

"The implications of the word jewel—precious little thing, delicate though not necessarily fragile, easy to transport, translucency that can also be impenetrable, ageless flower—make it pertinent here. I know of no better qualification for Achilles's paradox, so indifferent to the definitive refutations which have been nullifying it for over twenty-three centuries that we can already declare it immortal. The repeated tours of the mystery proposed by such endurance, the fine ignorance it has visited upon humanity, are gifts we have no choice but to accept gratefully. Let us revive it once more, if only to convince ourselves of perplexity and arcane intimations. I intend to devote a few pages—a few moments—to its presentation and most noteworthy revisions. Its inventor, as is well known, was Zeno of Elea, a disciple of Parmenides, who denied that anything could happen in the universe."

(from Jorge Luis Borges, The Perpetual Race of Achilles and the Tortoise, essay from 1929).

Read the Wikipedia page on Zeno’s paradoxes, in particular that of Achilles and the Tortoise.

The paradox of Achilles and the Tortoise is said to have been invented by Zeno of Elea, a disciple of Parmenides, almost 2500 years ago. Zeno's paradoxes have been the food of discussion for millennia.

A paradox can be viewed as consisting of three parts: A premise consisting of facts and established truths, an argument that is a logical derivation from the premise, and a conclusion that seems to be false.

In other words, a paradox can be defined as an unacceptable conclusion derived by apparently acceptable reasoning from apparently acceptable premises.

Describe briefly your own resolution of the paradox of Achilles and the Tortoise!  For example by stating the three parts above clearly, and identifying problems with one or more of them.

2. When does induction work?

The Raven Paradox was introduced in the 1940s by Carl Gustav Hempel (1905-1997), a German writer and philosopher. It questions the notion that a hypothesis H is supported by an observation that concurs with H, i.e., the basis for scientific induction.

Hempel's hypothesis was: All ravens are black.  An observation of a non-black raven would falsify the hypothesis. But does each observation of a black raven strengthen it? And how do observations of non-ravens affect the hypothesis?

The hypothesis can be expressed in predicate logic as :

H1: ∀x R(x) ⇒ B(x)

Another, logically equivalent, way of writing this is:

H2: ∀x ¬B(x) ⇒ ¬R(x)

i.e., All non-black objects are non-ravens. 

If we considered observations relating to this statement, an observation of a non-black raven would still falsify the hypothesis, but now any observation of a non-black non-raven, such as a yellow banana or pink elephant, would strengthen it! And sightings of black objects do not seem to matter at all.

a) A number of attempts at explaining the raven paradox may be found in the Wikipedia article Raven paradox. Which explanation do you find the most convincing? Motivate your answer briefly!

b) Goodman's paradox is one example that illustrates the problems of inductive inference. Give another example of when induction does not work, i.e., when induction could lead you (or someone else, or an algorithm) to incorrect or inappropriate answers. 

3. Research basics

a) In chapter 1 of the textbook by Walliman, eight different ways of using research to obtain new knowledge are listed: categorize, describe, explain, evaluate, compare, correlate, predict, control. Find examples of at least two of these in computer science research. Examples should be specific with references. Some research projects may illustrate more than one of these concepts.

b) Also, read pages 21-25 of chapter 2 of the book by Walliman, and discuss very briefly which of the approaches and philosophical viewpoints mentioned are used in computer science research? Give two examples.

Handing in your solution

Please save your solution as a pdf file and hand it both in Canvas (for grading) and Peergrade (for peer review). 

Peer grading

You will be asked to review the homework of two other students in Peergrade. Your solution will also be
reviewed in this way. The peer review is a mandatory part of the course. 

Feedback from your TA

Your seminar leader will grade your submission and report the result in Canvas. This may happen before
the associated seminar, but if your seminar leader is busy it will 

Complete means you have passed the assignment.

Incomplete means you have to hand in a revised version.

Fail means that you will have to submit a new version and attend the make-up seminar.
The Fail grade will only be applied in exceptional circumstances such as plagiarized work.