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

available in:   PDF (237 kB) PS (80 kB)
 
get:  
Similar Docs BibTeX   Write a comment
  
get:  
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