# Search results

- ...ly 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 can23 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 of10 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
- ...://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r0802608.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/l ...th.org/legacyimages/r/r080/r080260/r08026019.png" /> by means of primitive recursion if for any values of <img align="absmiddle" border="0" src="https://www.enc9 KB (1,216 words) - 19:03, 7 February 2011
- .../www.encyclopediaofmath.org/legacyimages/h/h047/h047210/h04721034.png" />, 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
- ...in 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-t3 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. Finally27 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 .../www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034018.png" />, and the ordinary recursive sets are "recursive" relative to any set. In its w29 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 ...th.org/legacyimages/l/l057/l057000/l05700038.png" /> occurs free and bound and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/l33 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 and2 KB (371 words) - 23:13, 2 November 2014
- ...re 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 i1 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 perm10 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