Computational Flows in Arithmetic

Publication date 6 November 2017

Abstract: A computational flow is a pair consisting of a sequence of computational problems of a certain sort and a sequence of computational reductions among them. In this paper we will develop a theory for these computational flows and we will use it to make a sound and complete interpretation for bounded theories of arithmetic. This property helps us to decompose a first order arithmetical proof to a sequence of computational reductions by which we can extract the computational content of low complexity statements in some bounded theories of arithmetic such as

I D e l t a_{0}

,

T_{n}^{k}

,

I D e l t a_{0} + E X P

and

P R A

. In the last section, by generalizing term-length flows to ordinal-length flows, we will extend our investigation from bounded theories to strong unbounded ones such as

I S i g m a_{n}

and

P A + T I (a l p h a)

and we will capture their total

N P

search problems as a consequence.

This page was built for publication: Computational Flows in Arithmetic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6293525)