Kleene-Rosser paradox

From Wikipedia, the free encyclopedia

This article 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. The resolution of the paradox is the recognition that recursion is central and fundamental to the notion of computation. See self-reference (especially the sentences sub-section of the examples section there) for some examples about how recursion (which is an instance of, or an example of, self-reference) can lead to paradoxes.

[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, most typed lambda calculi are not very expressive, indeed, are 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 \neg \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]}