Eberhard, Sebastian (2014). A feasible theory of truth over combinatory algebra. Annals of pure and applied logic, 165(5), pp. 10091033. Elsevier 10.1016/j.apal.2013.12.002
Text
1s2.0S0168007213001772main.pdf  Published Version Restricted to registered users only Available under License Publisher holds Copyright. Download (386kB)  Request a copy 


Text
ebe14.pdf  Accepted Version Available under License Publisher holds Copyright. Download (450kB)  Preview 
We define an applicative theory of truth TPT which proves totality exactly for the polynomial time computable functions. TPT has natural and simple axioms since nearly all its truth axioms are standard for truth theories over an applicative framework. The only exception is the axiom dealing with the word predicate. The truth predicate can only reflect elementhood in the words for terms that have smaller length than a given word. This makes it possible to achieve the very low prooftheoretic strength. Truth induction can be allowed without any constraints. For these reasons the system TPT has the high expressive power one expects from truth theories. It allows embeddings of feasible systems of explicit mathematics and bounded arithmetic. The proof that the theory TPT is feasible is not easy. It is not possible to apply a standard realisation approach. For this reason we develop a new realisation approach whose realisation functions work on directed acyclic graphs. In this way, we can express and manipulate realisation information more efficiently.
Item Type: 
Journal Article (Original Article) 

Division/Institute: 
08 Faculty of Science > Institute of Computer Science (INF) > Logic and Theory Group (LTG) 08 Faculty of Science > Institute of Computer Science (INF) 
UniBE Contributor: 
Eberhard, Sebastian 
Subjects: 
000 Computer science, knowledge & systems 500 Science > 510 Mathematics 
ISSN: 
01680072 
Publisher: 
Elsevier 
Language: 
English 
Submitter: 
Florian Ranzi 
Date Deposited: 
26 Jan 2015 08:49 
Last Modified: 
21 Sep 2015 09:49 
Publisher DOI: 
10.1016/j.apal.2013.12.002 
BORIS DOI: 
10.7892/boris.61791 
URI: 
https://boris.unibe.ch/id/eprint/61791 