PA is instantiationally complete, but algorithmically incomplete: An alternative interpretation of Goedelian incompleteness under Church's Thesis that links formal logic and computability
Bhupinder Singh Anand · arXiv (Cornell University) · 2005
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.