Evaluation of Mistakes in Computablity Written Tests

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.

1. 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.''
2. Stating that a set is recursive but not recursively enumerable.
3. Stating that the set of natural numbers, even naturals, odd naturals, or primes is a finite set. Similarly for other infinite ``well-known'' sets.
4. 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.

1. 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)
2. 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 ...''
3. 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.
4. Using Rice-Shapiro without being clear about which direction you are using.
5. 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.

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

Home - Teaching - Computability

Roberto Zunino, 2011