HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Are there lambda-calculus functions which always output booleans, but are not constant functions?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
booleansconstantcalculusarealwaysbutoutputwhichfunctionsthere

Problem

In labmda calculus, true = $\lambda x,y.x$ and false = $\lambda x,y.y$.

Is there a term $f$ such that for any other term $x$, $f x$ normalizes to true or false BUT $f$ does not have the same output for all inputs?

Solution

That is not possible. By the "genericity lemma" (Barendregt book, lemma 14.3.24), if $C[M] = N$ with $M$ unsolvable, and $N$ normal form, then $C[L] = N$ for any term $L$.

So, if $x$ is an unsolvable term (like $\Omega=(\lambda w.ww)(\lambda w.ww)$) and $f x = {\sf true}$ (normal form), then $f y = {\sf true}$ for any term $y$. The same holds for $\sf false$ or any other normal form.

The intuition here is that an unsolvable subterm will make the whole term diverge as soon as it is needed for the computation, much like while (true) {} hangs the program in imperative programming as soon as the loop is executed.

Context

StackExchange Computer Science Q#105426, answer score: 10

Revisions (0)

No revisions yet.