Common Mistakes in Answers in Computablity Written Tests

This page lists some specific significant mistakes which I found to be common in answers to the written tests. Since some of them are way too common, I am putting some penalties on them. I'd rather prefer a missing answer than one carrying one of these mistakes.

Critical Mistakes: these are likely to cause the rejection of your whole answer sheet, no matter how good the other answers may be.

1. Stating that, since the hypothesis of a known theorem does not hold, the thesis does not hold as well. Notable examples of this mistake:
   • Using Rice's theorem to prove that a set is recursive.
   • Using the Rice-Shapiro theorem to prove that a set is recursively enumerable.
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.

Major Mistakes: these are likely to award a negative score. Unless the other answers are good to compensate, your overall score might fall under the threshold to pass the written test.

1. Using Rice-Shapiro without being clear about which direction you are using.
2. 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 ``x + y'' when x and y are not numbers.
   • Stating that a function is (not) recursively enumerable. (whatever that would mean)
   • (not exhaustive list)
3. Arbitrarily choosing the value of a variable (e.g. ``I pick x=5, hence p(5) holds'') when you can not (e.g. you applied a theorem stating that ``for some x, p(x) holds'')

Wishful Reading Mistakes: misreading a question so that it becomes trivial will award zero points. Do not waste your time: if you do not know the answer, skip the question instead.

Standard Mistakes: these will not award negative points, but award no positive points, either.

1. Rewriting a logical formula, arithmetic formula, set formula in a non-equivalent way. E.g. x*y+4 = x*(y+4)
2. Simple mistakes e.g. ``4+3=8'' which do not make the exercise trivial.

Infelicities: these, technically speaking, are not mistakes, but can be described as ``taking the stairs instead of the lift at the Empire State Building''. There is no penalty for these, but for the fact that you wasted your time during the test.

1. Proving a set to be non recursively enumerable, and then proving (from scratch) that it is non recursive.

Home

Roberto Zunino, 2010