arnold beckmann's pages

Subset-Bounded Recursion and a Circuit Model for Cobham Recursive Set Functions

File: PDF-File

Author: Arnold Beckmann, Samuel R. Buss, Sy-David Friedman, Moritz Müller and Neil Thapen
Title: Subset-Bounded Recursion and a Circuit Model for Cobham Recursive Set Functions
Year: 2016
Status: submitted
Pages: 47

Abstract: The Cobham Recursive Set Functions (CRSF) provide an analogue of polynomial time computation which applies to arbitrary sets. We give three new equivalent characterizations of CRSF. The first is algebraic, using subset-bounded recursion and a form of Mostowski collapse. The second uses a circuit model of computation; the CRSF functions are shown to be precisely the functions computed by a class of uniform, infinitary, Boolean circuits. The third is in terms of a simple extension of the rudimentary functions by transitive closure and subset-bounded recursion.

websites: Arnold Beckmann 2017-08-28 Valid HTML 4.01! Valid CSS!