Kleene's recursion theorem

Kleene's recursion theorem Not to be confused with Kleene's theorem for regular languages.

In computability theory, Kleene's recursion theorems are a pair of fundamental results about the application of computable functions to their own descriptions. The theorems were first proved by Stephen Kleene in 1938[1] and appear in his 1952 book Introduction to Metamathematics.[2] A related theorem, which constructs fixed points of a computable function, is known as Rogers's theorem and is due to Hartley Rogers, Jr.[3] The recursion theorems can be applied to construct fixed points of certain operations on computable functions, to generate quines, and to construct functions defined via recursive definitions.

Conteúdo 1 Notação 2 Rogers's fixed-point theorem 2.1 Proof of the fixed-point theorem 2.2 Fixed-point-free functions 3 Kleene's second recursion theorem 3.1 Comparison to Rogers's theorem 3.2 Application to quines 3.3 Application to elimination of recursion 3.4 Reflexive programming 4 The first recursion theorem 4.1 Exemplo 4.2 Proof sketch for the first recursion theorem 4.3 Comparison to the second recursion theorem 5 Generalized theorem 6 Veja também 7 Referências 8 Leitura adicional 9 External links Notation The statement of the theorems refers to an admissible numbering {estilo de exibição varphi } of the partial recursive functions, such that the function corresponding to index {estilo de exibição e} é {estilo de exibição varphi _{e}} .

Se {estilo de exibição F} e {estilo de exibição G} are partial functions on the natural numbers, the notation {displaystyle Fsimeq G} indicates that, for each n, qualquer {estilo de exibição F(n)} e {estilo de exibição G(n)} are both defined and are equal, or else {estilo de exibição F(n)} e {estilo de exibição G(n)} are both undefined.

Rogers's fixed-point theorem Given a function {estilo de exibição F} , a fixed point of {estilo de exibição F} is an index {estilo de exibição e} de tal modo que {estilo de exibição varphi _{e}simeq varphi _{F(e)}} . Rogers describes the following result as "a simpler version" of Kleene's (segundo) recursion theorem.[4] Rogers's fixed-point theorem. Se {estilo de exibição F} is a total computable function, it has a fixed point. Proof of the fixed-point theorem The proof uses a particular total computable function {estilo de exibição h} , defined as follows. Given a natural number {estilo de exibição x} , a função {estilo de exibição h} outputs the index of the partial computable function that performs the following computation: Given an input {estilo de exibição y} , first attempt to compute {estilo de exibição varphi _{x}(x)} . If that computation returns an output {estilo de exibição e} , then compute {estilo de exibição varphi _{e}(y)} and return its value, caso existam.

Desta forma, for all indices {estilo de exibição x} of partial computable functions, E se {estilo de exibição varphi _{x}(x)} é definido, então {estilo de exibição varphi _{h(x)}simeq varphi _{varphi_{x}(x)}} . Se {estilo de exibição varphi _{x}(x)} is not defined, então {estilo de exibição varphi _{h(x)}} is a function that is nowhere defined. A função {estilo de exibição h} can be constructed from the partial computable function {estilo de exibição g(x,y)} described above and the s-m-n theorem: para cada {estilo de exibição x} , {estilo de exibição h(x)} is the index of a program which computes the function {displaystyle ymapsto g(x,y)} .

To complete the proof, deixar {estilo de exibição F} be any total computable function, and construct {estilo de exibição h} como acima. Deixar {estilo de exibição e} be an index of the composition {displaystyle Fcirc h} , which is a total computable function. Então {estilo de exibição varphi _{h(e)}simeq varphi _{varphi_{e}(e)}} by the definition of {estilo de exibição h} . Mas, Porque {estilo de exibição e} is an index of {displaystyle Fcirc h} , {estilo de exibição varphi _{e}(e)=(Fcirc h)(e)} , e assim {estilo de exibição varphi _{varphi_{e}(e)}simeq varphi _{F(h(e))}} . By the transitivity of {simeq de estilo de exibição } , isso significa {estilo de exibição varphi _{h(e)}simeq varphi _{F(h(e))}} . Por isso {estilo de exibição varphi _{n}simeq varphi _{F(n)}} por {displaystyle n=h(e)} .

This proof is a construction of a partial recursive function which implements the Y combinator.

Fixed-point-free functions A function {estilo de exibição F} de tal modo que {estilo de exibição varphi _{e}not simeq varphi _{F(e)}} para todos {estilo de exibição e} is called fixed-point free. The fixed-point theorem shows that no total computable function is fixed-point free, but there are many non-computable fixed-point-free functions. Arslanov's completeness criterion states that the only recursively enumerable Turing degree that computes a fixed-point-free function is 0′, the degree of the halting problem.[5] Kleene's second recursion theorem The second recursion theorem is a generalization of Rogers's theorem with a second input in the function. One informal interpretation of the second recursion theorem is that it is possible to construct self-referential programs; Vejo "Application to quines" abaixo de.

The second recursion theorem. For any partial recursive function {estilo de exibição Q(x,y)} there is an index {estilo de exibição p} de tal modo que {estilo de exibição varphi _{p}simeq lambda y.Q(p,y)} .

The theorem can be proved from Rogers's theorem by letting {estilo de exibição F(p)} be a function such that {estilo de exibição varphi _{F(p)}(y)=Q(p,y)} (a construction described by the S-m-n theorem). One can then verify that a fixed-point of this {estilo de exibição F} is an index {estilo de exibição p} como requerido. The theorem is constructive in the sense that a fixed computable function maps an index for Q into the index p.

Comparison to Rogers's theorem Kleene's second recursion theorem and Rogers's theorem can both be proved, rather simply, from each other.[6] No entanto, a direct proof of Kleene's theorem[7] does not make use of a universal program, which means that the theorem holds for certain subrecursive programming systems that do not have a universal program.

Application to quines A classic example using the second recursion theorem is the function {estilo de exibição Q(x,y)=x} . The corresponding index {estilo de exibição p} in this case yields a computable function that outputs its own index when applied to any value.[8] When expressed as computer programs, such indices are known as quines.

The following example in Lisp illustrates how the {estilo de exibição p} in the corollary can be effectively produced from the function {estilo de exibição Q} . The function s11 in the code is the function of that name produced by the S-m-n theorem.

Q can be changed to any two-argument function.

(setq Q '(lambda (xy) x)) (setq s11 '(lambda (f x) (list 'lambda '(y) (list f x 'y)))) (setq n (list 'lambda '(xy) (list Q (list s11 'x 'x) 'y))) (setq p (eval (list s11 n n))) The results of the following expressions should be the same. {estilo de exibição varphi } p(nil) (eval (list p nil)) Q(p, nil) (eval (list Q p nil)) Application to elimination of recursion Suppose that {estilo de exibição g} e {estilo de exibição h} are total computable functions that are used in a recursive definition for a function {estilo de exibição f} : {estilo de exibição f(0,y)simeq g(y),} {estilo de exibição f(x+1,y)simeq h(f(x,y),x,y),} The second recursion theorem can be used to show that such equations define a computable function, where the notion of computability does not have to allow, prima facie, for recursive definitions (por exemplo, it may be defined by μ-recursion, or by Turing machines). This recursive definition can be converted into a computable function {estilo de exibição varphi _{F}(e,x,y)} that assumes {estilo de exibição e} is an index to itself, to simulate recursion: {estilo de exibição varphi _{F}(e,0,y)simeq g(y),} {estilo de exibição varphi _{F}(e,x+1,y)simeq h(varphi_{e}(x,y),x,y).} The recursion theorem establishes the existence of a computable function {estilo de exibição varphi _{f}} de tal modo que {estilo de exibição varphi _{f}(x,y)simeq varphi _{F}(f,x,y)} . Desta forma {estilo de exibição f} satisfies the given recursive definition.

Reflexive programming Reflexive, or reflective, programming refers to the usage of self-reference in programs. Jones presents a view of the second recursion theorem based on a reflexive language.[9] It is shown that the reflexive language defined is not stronger than a language without reflection (because an interpreter for the reflexive language can be implemented without using reflection); então, it is shown that the recursion theorem is almost trivial in the reflexive language.

The first recursion theorem While the second recursion theorem is about fixed points of computable functions, the first recursion theorem is related to fixed points determined by enumeration operators, which are a computable analogue of inductive definitions. An enumeration operator is a set of pairs (UMA,n) where A is a (code for a) finite set of numbers and n is a single natural number. Muitas vezes, n will be viewed as a code for an ordered pair of natural numbers, particularly when functions are defined via enumeration operators. Enumeration operators are of central importance in the study of enumeration reducibility.

Each enumeration operator Φ determines a function from sets of naturals to sets of naturals given by {estilo de exibição Phi (X)={nmid exists Asubseteq X[(UMA,n)in Phi ]}.} A recursive operator is an enumeration operator that, when given the graph of a partial recursive function, always returns the graph of a partial recursive function.

A fixed point of an enumeration operator Φ is a set F such that Φ(F) = F. The first enumeration theorem shows that fixed points can be effectively obtained if the enumeration operator itself is computable.

First recursion theorem. The following statements hold. For any computable enumeration operator Φ there is a recursively enumerable set F such that Φ(F) = F and F is the smallest set with this property. For any recursive operator Ψ there is a partial computable function φ such that Ψ(Phi) = φ and φ is the smallest partial computable function with this property. Example Like the second recursion theorem, the first recursion theorem can be used to obtain functions satisfying systems of recursion equations. To apply the first recursion theorem, the recursion equations must first be recast as a recursive operator.

Consider the recursion equations for the factorial function f: {estilo de exibição f(0)=1} {estilo de exibição f(n+1)=(n+1)cdot f(n)} The corresponding recursive operator Φ will have information that tells how to get to the next value of f from the previous value. No entanto, the recursive operator will actually define the graph of f. Primeiro, Φ will contain the pair {estilo de exibição (varnothing ,(0,1))} . This indicates that f(0) is unequivocally 1, and thus the pair (0,1) is in the graph of f.

Próximo, for each n and m, Φ will contain the pair {estilo de exibição ({(n,m)},(n+1,(n+1)cdot m))} . This indicates that, if f(n) is m, then f(n + 1) é (n + 1)m, so that the pair (n + 1, (n + 1)m) is in the graph of f. Unlike the base case f(0) = 1, the recursive operator requires some information about f(n) before it defines a value of f(n + 1).

The first recursion theorem (em particular, papel 1) states that there is a set F such that Φ(F) = F. The set F will consist entirely of ordered pairs of natural numbers, and will be the graph of the factorial function f, como desejado.

The restriction to recursion equations that can be recast as recursive operators ensures that the recursion equations actually define a least fixed point. Por exemplo, consider the set of recursion equations: {estilo de exibição g(0)=1} {estilo de exibição g(n+1)=1} {estilo de exibição g(2n)=0} There is no function g satisfying these equations, because they imply g(2) = 1 and also imply g(2) = 0. Thus there is no fixed point g satisfying these recursion equations. It is possible to make an enumeration operator corresponding to these equations, but it will not be a recursive operator.

Proof sketch for the first recursion theorem The proof of part 1 of the first recursion theorem is obtained by iterating the enumeration operator Φ beginning with the empty set. Primeiro, a sequence Fk is constructed, por {displaystyle k=0,1,ldots } . Let F0 be the empty set. Proceeding inductively, for each k, let Fk + 1 be {estilo de exibição F_{k}cup Phi (F_{k})} . Finalmente, F is taken to be {displaystyle bigcup F_{k}} . The remainder of the proof consists of a verification that F is recursively enumerable and is the least fixed point of Φ. The sequence Fk used in this proof corresponds to the Kleene chain in the proof of the Kleene fixed-point theorem.

The second part of the first recursion theorem follows from the first part. The assumption that Φ is a recursive operator is used to show that the fixed point of Φ is the graph of a partial function. The key point is that if the fixed point F is not the graph of a function, then there is some k such that Fk is not the graph of a function.

Comparison to the second recursion theorem Compared to the second recursion theorem, the first recursion theorem produces a stronger conclusion but only when narrower hypotheses are satisfied. Rogers uses the term weak recursion theorem for the first recursion theorem and strong recursion theorem for the second recursion theorem.[3] One difference between the first and second recursion theorems is that the fixed points obtained by the first recursion theorem are guaranteed to be least fixed points, while those obtained from the second recursion theorem may not be least fixed points.

A second difference is that the first recursion theorem only applies to systems of equations that can be recast as recursive operators. This restriction is similar to the restriction to continuous operators in the Kleene fixed-point theorem of order theory. The second recursion theorem can be applied to any total recursive function.

Generalized theorem In the context of his theory of numberings, Ershov showed that Kleene's recursion theorem holds for any precomplete numbering.[10] A Gödel numbering is a precomplete numbering on the set of computable functions so the generalized theorem yields the Kleene recursion theorem as a special case.[11] Given a precomplete numbering {estilo de exibição não } , then for any partial computable function {estilo de exibição f} with two parameters there exists a total computable function {estilo de exibição t} with one parameter such that {displaystyle forall nin mathbb {N} :nu circ f(n,t(n))=nu circ t(n).} See also Denotational semantics, where another least fixed point theorem is used for the same purpose as the first recursion theorem. Fixed-point combinators, which are used in lambda calculus for the same purpose as the first recursion theorem. Diagonal lemma a closely related result in mathematical logic References Ershov, Yuri L. (1999). "Part 4: Mathematics and Computability Theory. 14. Theory of numbering". In Griffor, Eduardo R. (ed.). Handbook of Computability Theory. Studies in logic and the foundations of mathematics. Volume. 140. Amsterdã: Elsevier. pp. 473-503. ISBN 9780444898821. OCLC 162130533. Recuperado 6 Poderia 2020. Jones, Neil D. (1997). Computability and complexity: From a Programming Perspective. Cambridge, Massachusetts: Imprensa do MIT. ISBN 9780262100649. OCLC 981293265. Kleene, Stephen C. (1952). Introduction to Metamathematics. Bibliotheca Mathematica. North-Holland Publishing. ISBN 9780720421033. OCLC 459805591. Recuperado 6 Poderia 2020. Roger, Hartley (1967). Theory of recursive functions and effective computability. Cambridge, Massachusetts: Imprensa do MIT. ISBN 9780262680523. OCLC 933975989. Recuperado 6 Poderia 2020.

Footnotes ^ Kleene, Stephen C. (1938). "On notation for ordinal numbers" (PDF). Journal of Symbolic Logic. 3 (4): 150-155. doi:10.2307/2267778. ISSN 0022-4812. JSTOR 2267778. Recuperado 6 Poderia 2020. ^ Kleene 1952. ^ Saltar para: a b Rogers 1967. ^ Rogers 1967, §11.2. ^ Soare, R.I. (1987). Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Perspectivas em Lógica Matemática. Berlin and New York City: Springer-Verlag. p. 88. ISBN 9780387152998. OCLC 318368332. ^ Jones 1997, pp. 229–30. ^ Kleene 1952, pp. 352-3. ^ Cutland, Nigel J. (1980). Computability: An Introduction to Recursive Function Theory. Cambridge University Press. p. 204. doi:10.1017/cbo9781139171496. ISBN 9781139935609. OCLC 488175597. Recuperado 6 Poderia 2020. ^ Jones 1997. ^ Barendregt, Henk; Terwijn, Sebastiaan A. (2019). "Fixed point theorems for precomplete numberings". Annals of Pure and Applied Logic. 170 (10): 1151–1161. doi:10.1016/j.apal.2019.04.013. HDL:2066/205967. ISSN 0168-0072. S2CID 52289429. Recuperado 6 Poderia 2020. p. 1151. ^ See Ershov 1999, §4.14 for a survey in English. Further reading Jockusch, C. G.; Lerman, M.; Sol, R.I.; Solovay, R.M. (1989). "Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion". O Diário da Lógica Simbólica. 54 (4): 1288–1323. doi:10.1017/S0022481200041104. ISSN 0022-4812. JSTOR 2274816. links externos "Recursive Functions" entry by Piergiorgio Odifreddi in the Stanford Encyclopedia of Philosophy, 2012. Categorias: Computability theoryTheorems in the foundations of mathematics