Incompleteness in Linear Time
Salvatore Caporaso (Dipartimento di Informatica dell'Università di Bari, Italy)
Giovanni Pani (Dipartimento di Informatica dell'Università di Bari, Italy)
Emanuele Covino (Dipartimento di Informatica dell'Università di Bari, Italy)
Abstract: A class LT 0 of functions computable in a proper sub_class of Lintime is defined, and formalized in a system LT0 of monadic and atomic (quantifier-free) logic. In spite of its poor computational complexity power and logical apparatus, this system has enough power to describe its own proof-predicate. Therefore it might qualify as smallest known system in which Gödel-like diagonalization can be applied. A proof is given that the identically true functions of LT 0 are productive. Hence this incompleteness phenomenon doesn t depend on the technicalities adopted to show it.
Keywords: computational complexity, incompleteness, linear time
Categories: F.4.1
|