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

Corresponding author: Salvatore Caporaso ( caporaso@di.uniba.it )

© Salvatore Caporaso, Giovanni Pani, Emanuele Covino.
This article is freely available under the J.UCS Open Content License.
Citation: Caporaso S, Pani G, Covino E (2000) Incompleteness in Linear Time. JUCS - Journal of Universal Computer Science 6(12): 1185-1196. https://doi.org/10.3217/jucs-006-12-1185
Open Access
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
incompleteness, linear time, computational complexity