4
$\begingroup$

I am reading Exploring Robotic Minds by Prof. Jun Tani, and came across the term subrecursive. Original context:

Another possibility might be to assume subrecursive functions embedded in analogical processes rather than logical operations in FLB that can mimic recurssive operations for finite levels.

FLB is Noam Chomsky's faculty of language in a broad sense

I am have found the following definition from Campagnolo et al., but am having a hard time understanding it. Any help unpacking the following or an example would be greatly appreciated :)

All functions in the Grzegorczyk hierarchy are subrecursive, meaning that they are computable in a number of steps which is a less computationally complex function of the input than the function itself

Bonus question

Are subrecursive algorithms the opposite of superrecursive algorithms? In either case can you help me understand the relationship between them?

$\endgroup$
  • $\begingroup$ Link to Wikipedia article about superrecursive algorithms (I don't have 10 reputation here) $\endgroup$ – Toke Faurby Dec 30 '16 at 8:54
3
$\begingroup$

There exist many interesting languages that do not have the full expressiveness of Turing Machines: these languages are traditionally called subrecursive.

The typical example is the language of primitive recursive algorithms, provably equivalent to the language of algorithms that can be written with "for-like" statements (fixed step, fixed bounds). Primitive recursive algorithms are total, hence they are not complete (that means that there are total functions not expressible in the formalism). A famous example of a total function not expressible in the primitive recursive setting is Ackermann function.

Other examples of subrecursive languages come from logic. It is well know that no logical system (rich enough to allow to reason about natural numbers) is complete. Hence you cannot expect to prove the totality of all algorithms in them. That is to say that any logical system characterizes a set of computable functions that are provably total in the given system. For instance, the set of computable functions provably total in Peano arithmetics is the so called Goedel's System T (a higher order generalization of primitive recursion); similarly, the set of computable functions provably total in second order arithmetics is Girard's System F, also know as polymorphic lambda calculus.

The interest of considering subrecursive languages consists in the fact of capturing statically , i.e. by the way the program is written, relevant dynamic aspects of the algorithm, such as totality, or complexity properties.

The problem of providing syntactical characterizations of subrecursive complexity classes such as P, Pspace, etc. has received much attention in the literature. The recent field of Implicit Complexity aims at studying the computational complexity of programs with no reference to a particular machine model and explicit bounds on time or memory, but instead relying on logical or computational principles that entail complexity properties, typically via a controlled use of the available resources. For an introduction to this topic, you may consult the special issue on Implicit Computational Complexity, ACM Trans. Comput. Log., Vol 10, n.4 2009.

Other interesting characterizations have been obtained restricting the interpretation of programming languages to finite domains. The seminal result in this area is an old work of Gurevich ("Algebras of feasible functions", FOCS 1983) where he proved that interpreting primitive recursive functions (resp. recursive functions) over finite structures one precisely get the log-space (resp. polynomial time) computable functions.

Please have a look at my article "Computational Complexity via Finite Types", ACM Trans. Comput. Log., Vol 16, n.15 2015, for more references in this area.

$\endgroup$
2
$\begingroup$

From http://www.cs.toronto.edu/~bor/Papers/subrecursive.pdf

PR is called universal or general recursive. A language characterized by a subset of R is called subrecursive.

where

Pn is all n argument partial functions

PRn is all n argument partial recursive functions

$\endgroup$
  • 1
    $\begingroup$ Also from the referenced paper: 'The structural complexity of programming languages, and therefore of programs as well, can be measured by the subrecursive class of functions which characterize the language. Using such a measure of structural complexity, we examine the tradeoff relationship between structural and computational complexity' $\endgroup$ – Toke Faurby Jan 3 '17 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.