Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Archive for Mathemat...arrow_drop_down
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
Archive for Mathematical Logic
Article . 1995 . Peer-reviewed
License: Springer TDM
Data sources: Crossref
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article . 1995
Data sources: zbMATH Open
Archive for Mathematical Logic
Article . 1995 . Peer-reviewed
Data sources: Crossref
versions View all 3 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

A theory of rules for enumerated classes of functions

Authors: Schlüter, Andreas;

A theory of rules for enumerated classes of functions

Abstract

In classical logic, the fact that we have proved the existence of a solution does not necessarily mean that we have thus got an algorithm for producing this solution: For example, our proof can be based on considering two cases: when the Riemann hypothesis is true, and when it is not, and lead to different constructions in both cases; unless we know whether the Riemann hypothesis is true, we cannot produce an algorithm. In many cases, we need an algorithm, so it would be nice to have a logic in which proofs will automatically lead to algorithms. Such logics are called constructive. In constructive logics, a proof of a statement \(A\) carries with it an object (if any) whose existence is declared in \(A\). Correspondingly, a proof of an implication \(A\to B\) carries with it an algorithm that transforms an object whose existence is declared in \(A\) into an object whose existence is declared in \(B\). For formulas with iterated implications, like \((A\to B)\to C\), we will need mappings of higher type: from functions to objects, from functions to functions, etc. The resulting system becomes very complicated. In traditional constructive logic, this complicated structure is simplified by the existence of a universal (enumerating) algorithm. In programming terms, a universal algorithm is simply a compiler. In mathematical terms, it is a function \(f(m, n)\) of two variables (\(m\) is the code of a program, and \(n\) is the program's input) such that every computable function \(g(n)\) can be represented as \(f(m, n)\) for an appropriate code \(m\). The existence of such a function enables us to use codes to describe functions; hence, mapping from functions to objects can be coded as mappings from codes to objects, and thus, again simply by codes. One of the convenient forms of constructive logic in which this idea is implemented is combinatory logic (a basis for \(\lambda\)-calculus). For traditional combinatory logic, it is important that the universal function is also an algorithm (i.e. that it also belongs to the class of functions that we call constructive). It is true if we consider all algorithms, no matter how long they run, as constructive. In reality, an algorithm whose running time on small inputs exceeds the lifetime of the Universe can hardly be called constructive. If we restrict ourselves to a class of truly constructive algorithms (be it polynomial time, or primitive recursive), the enumerating function still exists (the compiler is still there), but it no longer belongs to the chosen function class (because a small program can run forever). For these situations, traditional combinatory logic is not applicable. Since the codes still exist (i.e., a class of functions is still enumerated), it is desirable to design a modification of combinatory logic in which these codes are used to simplify the hierarchy; care must be taken because the universal function is no longer constructive. Such a modification is proposed in the reviewed paper. This modification distinguishes between variables that occur in argument position in expressions (so that the dependency of the expression on these variables is computable), and other variables (related to codes) with respect to which computations are not necessarily possible. In particular, a \(\lambda\)-construction that uses a given term \(t\) to generate a constructive function \(\lambda x.t\) (meaning computing \(t\) from \(x\)) is only possible for variables \(x\) in argument position. An abstract Recursion Theorem is proven that generalizes recursion theorems for recursive and primitive recursive functions. The existence of the enumeration enables us to describe explicitly objects constructed by iterative constructions. Thus, the above theory is applied to explicit mathematics, first described by \textit{S. Feferman} [Lect. Notes Math. 450, 87-139 (1975; Zbl 0357.02029)].

Keywords

universal algorithm, enumerating function, abstract Recursion Theorem, Applications of computability and recursion theory, modification of combinatory logic, constructive logic, Combinatory logic and lambda calculus, Metamathematics of constructive systems, Other constructive mathematics, computable function, explicit mathematics

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    5
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
5
Average
Average
Average
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!