FOM: priority and CS

[Piergiorgio Odifreddi]

a quick note on the applications of priority in computer science. there 
is (or was) a widespread use of a special kind of the priority method,
the socalled "no injury priority", which is not as trivial as a grocery
shop list, although not as sophisticated as other kinds of priority with
injuries, in the subject of abstract complexity. 

this kind of priority was first used by post in 1944, in his construction
of a hypersimple set, and it basically consists of making a list of
requirements, and then satisfy at a given stage the requirement with
smaller index that can be satisfied and has not yet been satisfied.

a sample of results proved by this method in abstract complexity is:
rabin's theorem on functions having an arbitrarily large complexity;
the compression theorem showing that each complexity is the best
complexity of some recursive function; the celebrated blum's speed-up
theorem on functions without best complexity modulo a given recursive
factor; and the naming theorem showing that every complexity class has
a measured name.

the proof of the last result is particularly interesting since requirements
CAN be injured, and the solution is to have a dynamic priority list. 

thus the whole subject of abstract complexity seems to depend of a form
of the priority method (admittedly, with only one exception, without
injuries).

a treatment of this subject from a recursion-theoretical point of view
is in volume II of my book (classical recursion theory, 1999), which has
just appeared. in the same volume there is also a treatment of forcing
in arithmetic and its applications to recursion-theory, which is
relevant to the questions that some subscribers to fom have raised 
about the connections between diagonalization and forcing.

best wishes to all

george odifreddi