PA is instantiationally complete, but algorithmically incomplete: An alternative interpretation of Goedelian incompleteness under Church's Thesis that links formal logic and computability

Simple item page
dc.creatorAnand, Bhupinder Singh
dc.date2005-07-03
dc.date.accessioned2026-07-07T05:21:21Z
dc.date.available2026-07-07T05:21:21Z
dc.descriptionWe define instantiational and algorithmic completeness for a formal language. We show that, in the presence of Church's Thesis, an alternative interpretation of Goedelian incompleteness is that Peano Arithmetic is instantiationally complete, but algorithmically incomplete. We then postulate a Provability Thesis that links Peano Arithmetic and effective algorithmic computability, just as Church's Thesis links Recursive Arithmetic and effective instantiational computability.
dc.description18 pages; an HTML version is available at http://alixcomsi.com/PA_is_instantiationally_complete.htm
dc.identifierhttps://arxiv.org/abs/math/0507044
dc.identifierhttp://arxiv.org/abs/math/0507044
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/75657
dc.subjectGeneral Mathematics
dc.subject03B10
dc.titlePA is instantiationally complete, but algorithmically incomplete: An alternative interpretation of Goedelian incompleteness under Church's Thesis that links formal logic and computability
dc.typetext

Files

Collections

arXiv