Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 6 / Issue 12

available in:   PDF (237 kB) PS (80 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-006-12-1185


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