### 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.