Introduction to clarithmetic III

Details Introduction to clarithmetic III Introduction to clarithmetic III

2010-08-04

arxiv.org/abs/1008.0770v1

Computer Science

Logic in Computer Science

Scientific paper

The present paper constructs three new systems of clarithmetic (arithmetic based on computability logic --- see http://www.cis.upenn.edu/~giorgi/cl.html): CLA8, CLA9 and CLA10. System CLA8 is shown to be sound and extensionally complete with respect to PA-provably recursive time computability. This is in the sense that an arithmetical problem A has a t-time solution for some PA-provably recursive function t iff A is represented by some theorem of CLA8. System CLA9 is shown to be sound and intensionally complete with respect to constructively PA-provable computability. This is in the sense that a sentence X is a theorem of CLA9 iff, for some particular machine M, PA proves that M computes (the problem represented by) X. And system CLA10 is shown to be sound and intensionally complete with respect to not-necessarily-constructively PA-provable computability. This means that a sentence X is a theorem of CLA10 iff PA proves that X is computable, even if PA does not "know" of any particular machine M that computes X.

Affiliated with

Also associated with

No associations

Rating

Introduction to clarithmetic III does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Introduction to clarithmetic III, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Introduction to clarithmetic III will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-82784