PA is instantiationally complete, but algorithmically incomplete: An alternative interpretation of Goedelian incompleteness under Church's Thesis that links formal logic and computability
Abstract
Description
We 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.
18 pages; an HTML version is available at http://alixcomsi.com/PA_is_instantiationally_complete.htm
18 pages; an HTML version is available at http://alixcomsi.com/PA_is_instantiationally_complete.htm