patternModerate
Are there lambda-calculus functions which always output booleans, but are not constant functions?
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?
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
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.