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