Kleene-Rosser paradox

From Wikipedia, the free encyclopedia

This article or section is in need of attention from an expert on the subject.
Please help recruit one or improve this article yourself. See the talk page for details.
Please consider using {{Expert-subject}} to associate this request with a WikiProject

In mathematics, the Kleene-Rosser paradox is a paradox that shows Church's original lambda calculus is inconsistent. It is similar to Russell's paradox, in that it is a statement that asserts its own falsehood if and only if it is true; that is, it is a self-negating statement. The paradox was developed by Stephen Kleene and J. B. Rosser in 1935, to show that the lambda calculus was inconsistent.^{[citation needed]} The resolution of the paradox is the recognition that recursion is central and fundamental to the notion of computation.

[edit] The paradox

Defining the function $k = (\lambda x. \neg x x)$ , one then may deduce

$kk = (\lambda x. \neg x x) k = \neg kk$

and so this function, when combined with itself, negates itself.

Several solutions to avoid the paradox were proposed, including type theory or typed lambda calculus. However, typed lambda calculus is not very expressive, indeed, it is not Turing complete. An alternate solution is to re-interpret lambda calculus not as a theory of logical assertions, but rather as a means of expressing computation. In this way, the paradox can be "solved" by reinterpreting it as a recursive statement, that is, the infinite recursion implying

$p\rightarrow \neg p\rightarrow \neg \neg p \rightarrow \cdots$

where $p = k k$ is the paradox. In this way, the inconsistency of lambda calculus is revealed to be a central and essential property of computation.^{[citation needed]}