FOM: Provably non-constructive priority argument

John Case case at
Sun Jul 30 18:29:36 EDT 2000

Harvey Friedman and later Steve Simpson asked in fom about priority arguments
for results provably non-constructive.

Some years back I posed a specific conjecture along these lines to Mark Fulk,
one of my then Ph.D. students.  My conjecture posited particular inherently 
non-constructive elements re the existence of almost everywhere h-complex
0-1 valued computable functions.  The standard construction of these is by a 
zero-injury priority construction.  Mark's proof of my conjecture appears
in [M. Fulk, ``A note on almost everywhere h-complex functions,'' Journal of 
Computer and System Sciences, 40 (1990), 444-449].  The statement and proof are
entirely recursion-theoretic.  Odifreddi's Classical Recursion Theory, Vol. II,
also has a discussion, pp. 27-30.


  * John Case                                      Email: case at  *
  * Professor                                      Phone: +1-302-831-2714 or *
  * Computer and Information Sciences Department          +1-302-831-4175    *
  * 101A Smith Hall                                  FAX: +1-302-831-8458    *
  * University of Delaware                                                   *
  * Newark, DE 19716-2586 (USA)                     Home: +1-302-832-5557    *
  *                 URL:                      *

More information about the FOM mailing list