JUCS - Journal of Universal Computer Science 6(12): 1185-1196, doi: 10.3217/jucs-006-12-1185
Incompleteness in Linear Time
expand article infoSalvatore Caporaso, Giovanni Pani§, Emanuele Covino§
‡ Dipartimento di Informatica dell'Università di Bari, Italy§ Università di Bari, Bari, Italy
Open Access
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.
incompleteness, linear time, computational complexity