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 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
• ...://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.enc
9 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-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 .../www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034018.png" />, 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 ...th.org/legacyimages/l/l057/l057000/l05700038.png" /> occurs free and bound and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/l
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
• ...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 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