Please use this identifier to cite or link to this item:
Type: Artigo de periódico
Title: The Ricean Objection: An Analogue of Rice's Theorem for First-order Theories
Author: Oliveira, IC
Carnielli, W
Abstract: We propose here an extension of Rice's theorem to first-order logic, proven by totally elementary means. If P is any property defined over the collection of all first-order theories and P is non-tricial over the set of finitely axiomatizable theories (i.e., P holds for some, but not all theories), then P is undecidable. This not only means that the problem of deciding properties of first-order theories is as hard as the problem of deciding properties about languages accepted by Turing machines, but also offers a general setting for proving several undecidability results in first-order theories.
Country: Inglaterra
Editor: Oxford Univ Press
Rights: fechado
Identifier DOI: 10.1093/jigpal/jzn023
Date Issue: 2008
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
WOS000262853100004.pdf78.6 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.