This page describes the penalties applied to specific mistakes in written tests. For serious errors, these can bring the score of a whole exercise below zero: in that case, not doing the exercise would have awarded a better score.

**Instant failure**: a single occurence of these mistakes causes the
failure of the whole test -- even if the rest is perfect.

- Stating that, since the hypothesis of a known theorem does not hold,
the thesis does not hold as well. Notable examples:
- Using Rice's theorem to prove that a set is recursive.
- Using the Rice-Shapiro theorem to prove that a set is recursively enumerable.
- ``Let f(n)=( g(n) if property(n) ; h(n) otherwise ). Since property is not recursive, f is not recursive.''
- ``Since A and B are not recursive, A union B is not recursive.''

- Stating that a set is recursive but not recursively enumerable.
- Stating that the set of natural numbers, even naturals, odd naturals, or primes is a finite set. Similarly for other infinite ``well-known'' sets.
- Stating that the Kleene's set K is recursive; or that K is not recursively enumerable; or that the complement of K is recursively enumerable.

**Negative points**: these mistakes award negative points, typically
making the whole exercise detrimental to the overall score.

- Writing a formula which does not respect ``types'', i.e. it mixes
functions/sets/programs/natural numbers in a meaningless way. Examples:
- Writing ``x belongs to y'' when y is not a set (but e.g. is a function, a program, or a natural number)
- Writing ``x belongs to A'' when A is a set of functions/natural numbers/programs, while x is not a function/natural number/program (respectively).
- Writing ``f(x)'' when f is not a function.
- Writing ``f(x)=A'' when A is a set and f is supposed to return a natural.
- Writing ``x + y'' when x and y are not numbers.
- Stating that a function is (not) recursively enumerable. (whatever that would mean)

- Arbitrarily choosing the value of a universally/existentially quantified variable. Examples:
- Justifying the claim ''for all x, p(x) holds'' by picking a specific value of x.
- Justifying the claim ''there is no x such that p(x) holds'' by picking a specific value of x.
- Justifying ''there is no function g such that ..." when applying Rice-Shapiro (=>) by providing an example for g.
- ``I take x=5, hence p(5) holds'' justified by a theorem stating
that ``
*for some*x, p(x) holds'' - ``I will prove that each x in A is even. Take e.g. x=4 ...''

- Defining functions/sets through formulae involving undefined variables.
- ``Let f(x)=x+y'' with no definition of y.
- ``Let A={i | exists j. property(i,j) } and g(i)=j'' claiming that the last j was defined in A.

- Using Rice-Shapiro without being clear about which direction you are using.
- Using logic in a remarkably creative way.
- ``A is not a subset of B since A is the empty set''
- ``I tried to implement a verifier V for A, but I failed. Hence A admits no verifier.''
- ``I am unable to prove p, hence p is false. QED''
- Reversing the order of an implication: ``A is not RE, hence the complement of K is m-reducible to A''

**Answer invalidation**: forcefully misreading a question so that it
becomes trivial will award zero points for that question.

**No penalty**: small mistakes which do not invalidate the overall
reasoning do not award negative points.

- Misreading a constant in the question which do not affect the essence of the exercise.
- Miscalculating an arithmetic expression without affecting the overall reasoning.
- Avoiding the simple solution and providing a much longer, but correct, alternative answer.

Home - Teaching - Computability

Roberto Zunino, 2011