Do you know anything about the complexity of peano arithmetic? is it stronger or weaker than Turing machine model? what is the relation between turing machine computability and PA-represantability?

 
plz reply to my email if you know the answer of that question, it will be a great kindness from you :)

 
I just sent you an e-mail. I don't know much about what you are asking, but I am willing to speculate a little (or a lot). Here's a version of what I said in the e-mail:

1. I don't understand the question about complexity. If you mean computational complexity, that seems mostly based on Turing machine and related computational models in the first place. Peano Arithmetic isn't really a computational model (though it is easy to relate a computational model to it), it is a logic-based theoretical formalism [a number theory]. If one were to suppose a computer that carried out elementary Peano arithmetic computationally (say, with 0, =, successor and predecessor as [necessary for computational-completeness] primitives) I would think the usual speed-ups apply. I don't know how one would characterize stronger and weaker in a complexity context here.

2. I can't answer your second question, though I can see how one might frame an argument about it in informal terms. That is, there might be a construction to show that every function that is PA-representable (that is, can be expressed in a particular way using first-order-logic with equality and the simple finesse beyond first-order to achieve PA) is TM-computable. Then there is the thought experiment of working through a demonstration that any TM (represented by its state-table rules, say) corresponds to a PA-representable function. I don't know enough about it to know that is an established case, or if that is responsive in being the relation you have in mind. For all I know, it's all in Turing and Gödel and is a routine student exercise in computation theory. [Proving that they're *not* equivalent might be a lot harder.][I bet it is all in Martin Davis's "Computability and Unsolvability" if you're willing to tease it out.]

3. My interest, in Numbering Peano, is more mundane with regard to manifestation of Peano numerals in a real computational system and seeing what that shows us about the manifestation of abstractions via computational means. I think I can steer clear of the heavier aspects of computation theory while providing a practical demonstration of some insights to be gained about how computers work (and don't work) for us.

Your question teaches me how superficial my understanding of these deeper areas is, and will remain so for a while longer. I'm operating at a more-vulgar level and that's sufficient so far.

Good luck with whatever has your question be so urgent.