Jan. 4th, 2019

https://en.wikipedia.org/wiki/Lambda_calculus#Undecidability_of_equivalence - it's been there all along...

There is no algorithm that takes as input two lambda expressions and outputs TRUE or FALSE depending on whether or not the two expressions are equivalent. This was historically the first problem for which undecidability could be proven.
...Building on earlier work by Kleene and constructing a Gödel numbering for lambda expressions, [Church] constructs a lambda expression e that closely follows the proof of Gödel's first incompleteness theorem. If e is applied to its own Gödel number, a contradiction results.

(Now the entire discussion about equality in lambda calculus looks pretty funny)

Profile

sassa_nf

January 2026

S M T W T F S
    123
45678910
111213141516 17
18192021222324
25262728293031

Style Credit

Expand Cut Tags

No cut tags
Page generated Jan. 23rd, 2026 02:44 pm
Powered by Dreamwidth Studios