Predicatively computable functions on sets

Archive for Mathematical Logic 54 (3-4):471-485 (2015)
  Copy   BIBTEX

Abstract

Inspired from a joint work by A. Beckmann, S. Buss and S. Friedman, we propose a class of set-theoretic functions, predicatively computable set functions. Each function in this class is polynomial time computable when we restrict to finite binary strings.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,593

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Computability of measurable sets via effective topologies.Yongcheng Wu & Decheng Ding - 2006 - Archive for Mathematical Logic 45 (3):365-379.
Order-Computable Sets.Denis Hirschfeldt, Russell Miller & Sergei Podzorov - 2007 - Notre Dame Journal of Formal Logic 48 (3):317-347.
Computable shuffle sums of ordinals.Asher M. Kach - 2008 - Archive for Mathematical Logic 47 (3):211-219.
Derivatives of Computable Functions.Ning Zhong - 1998 - Mathematical Logic Quarterly 44 (3):304-316.
Index sets and parametric reductions.Rod G. Downey & Michael R. Fellows - 2001 - Archive for Mathematical Logic 40 (5):329-348.
Infinite Time Turing Machines With Only One Tape.D. E. Seabold & J. D. Hamkins - 2001 - Mathematical Logic Quarterly 47 (2):271-287.
H‐monotonically computable real numbers.Xizhong Zheng, Robert Rettinger & George Barmpalias - 2005 - Mathematical Logic Quarterly 51 (2):157-170.
Computability of Minimizers and Separating Hyperplanes.Kam-Chau Wong - 1996 - Mathematical Logic Quarterly 42 (1):564-568.
Lp -Computability.Ning Zhong & Bing-Yu Zhang - 1999 - Mathematical Logic Quarterly 45 (4):449-456.
Computability & unsolvability.Martin Davis - 1958 - New York: Dover Publications.

Analytics

Added to PP
2015-03-22

Downloads
24 (#563,024)

6 months
2 (#668,348)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Safe recursive set functions.Arnold Beckmann, Samuel R. Buss & Sy-David Friedman - 2015 - Journal of Symbolic Logic 80 (3):730-762.
Cobham recursive set functions.Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller & Neil Thapen - 2016 - Annals of Pure and Applied Logic 167 (3):335-369.

Add more citations

References found in this work

The fine structure of the constructible hierarchy.R. Björn Jensen - 1972 - Annals of Mathematical Logic 4 (3):229.
Safe recursive set functions.Arnold Beckmann, Samuel R. Buss & Sy-David Friedman - 2015 - Journal of Symbolic Logic 80 (3):730-762.

Add more references