Search results

Jump to: navigation, search
  • enumerable. Many sets playing an important role in recursive set theory and its applications are productive (e.g. the set of all Gödel numbers of gene ...lign="top"> H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165</TD></TR></table>
    2 KB (288 words) - 19:33, 15 November 2014
  • ...rsive methods). Finally, in set theory [[Transfinite recursion|transfinite recursion]] is often used. ...rable from a more accurate description of the concept of recursion itself, and for this it is essential to establish which type of formal expressions can
    23 KB (3,188 words) - 18:56, 7 February 2011
  • ...umber of the operations of composition and [[Primitive recursion|primitive recursion]]. ...utable and the operators of superposition and primitive recursion preserve computability, the set of all primitive recursive functions is a subclass of the class of
    10 KB (1,339 words) - 18:56, 7 February 2011
  • ...t]]; in other words, a set $A$ is creative if it is recursively enumerable and if there exists a [[partial recursive function]] $\phi(x)$ such that, for a ...numerable sets. The concept of creativity generalizes to sequences of sets and other objects.
    2 KB (295 words) - 08:52, 28 September 2016
  • ...://" /> and <img align="absmiddle" border="0" src="" /> by means of primitive recursion if for any values of <img align="absmiddle" border="0" src="https://www.enc
    9 KB (1,216 words) - 19:03, 7 February 2011
  • .../" />, and their complements (the <img align="absmiddle" border="0" src="https://www.e In mathematical logic, hierarchies of sets and relations given by the formulas of logical languages are considered (see [[
    16 KB (2,267 words) - 19:09, 7 February 2011
  • where the $R_i$ and $R$ are atomic formulas (and $R$ could also be $x_p = x_q$ or $\texttt{false}$. (Strict) propositional H ...exttt{false}$. In the strict case $q = \texttt{false}$ is excluded. A Horn theory is a set of Horn clauses.
    7 KB (1,111 words) - 08:59, 21 October 2016
  • ...lign="top"> H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165</TD></TR> ...tin, "Bounded Queries in Recursion Theory", Progress in Computer Science and Applied Logic '''16'''. Springer (1999) ISBN 0817639667</TD></TR>
    2 KB (297 words) - 00:37, 11 January 2016
  • ...[[Universal function|Universal function]]. All possible forms of multiple recursion can be reduced to the following normal form: It is more common to speak of simultaneous recursion, rather than multiple recursion; cf., e.g., [[#References|[a1]]].
    3 KB (389 words) - 19:14, 7 February 2011
  • such a way that each mark can change position only finitely many times, and in its final position the mark must necessarily be the mark of an element t ...times allowed that the marks change position an infinite number of times), and therefore it is often better to speak of priority methods.
    3 KB (523 words) - 19:16, 7 February 2011
  • ..., by its table; the number of arguments of the function may depend on $a$) and numbers $b_1,\ldots,b_n$ such that $a\in A$ is equivalent to the truth of $ ...quivalence relation $\equiv_{tt}$, namely $A\equiv_{tt}B$ if $A\leq_{tt}B$ and $B\leq_{tt}A$. The equivalence classes for this relation are called truth-t
    3 KB (414 words) - 23:57, 16 January 2016
  • ...m for the solution of a given infinite series of problems of a given type, and of finding such an algorithm if it exists. ...the history of mathematics: all algorithms known in mathematics satisfy it and all attempts to construct algorithms not satisfying it have failed. Finally
    27 KB (4,050 words) - 19:18, 7 February 2011
  • ...lassifies subsets of natural numbers from the point of view of algorithms, and also studies the structures arising as a result of such a classification. F .../" />, and the ordinary recursive sets are "recursive" relative to any set. In its w
    29 KB (4,021 words) - 07:55, 9 November 2018
  • ...ed his machines (cf. [[Turing machine]]) and showed that Turing computable and lambda definable are equivalent notions. These are arguments for the Church" /> occurs free and bound and <img align="absmiddle" border="0" src="
    33 KB (4,575 words) - 20:23, 19 December 2014
  • ...ained by primitive recursion from an $n$-place function $g(x_1,\dots,x_n)$ and an $(n+2)$-place function $h(x_1,\dots,x_n,y,z)$ if for all natural number and
    2 KB (371 words) - 23:13, 2 November 2014
  • of interest from the point of the view of the recursive analogue of the theory of [[cardinal number]]s. In [[recursive set theory]] and its applications one also uses certain special subclasses of the class of i
    1 KB (194 words) - 13:14, 3 September 2017
  • <TR><TD valign="top">[2]</TD> <TD valign="top"> A.I. Mal'tsev, "Algorithms and recursive functions" , Wolters-Noordhoff (1970) (Translated from Russian)
    2 KB (253 words) - 14:32, 17 January 2016
  • ...duction (see below). It subsumes addition, multiplication, exponentiation, and all higher-order analogues of these operations. Because of this it grows to ...ermitted in primitive recursion fail to capture completely the notion of "computability" (cf. also [[Computable function|Computable function]]); one needs to perm
    10 KB (1,437 words) - 19:27, 7 February 2011
  • ...the basis of which lies a certain synthesis of ideas in the theory of sets and algorithms (see [[#References|[2]]]). ...TD valign="top">[2]</TD> <TD valign="top"> J. Barwise, "Admissible sets and structures" , Springer (1975)</TD></TR></table>
    1 KB (150 words) - 19:27, 7 February 2011