Research proof index

Correctness for the elimVar algorithm, which provides the inductive step of the bracket abstraction algorithm. We induct backwards on the list, corresponding to applying the transformation from the inside out. Since we haven't defined reduction for polynomials, we substitute arbitrary terms for the inner variables.

Correctness for the toSKI (bracket abstraction) algorithm.

The inclusion (· ⭢ ·) ≤ (· ⭢ₚ ·).

Rice's theorem: no SKI term is a non-trivial predicate. More specifically, say a term P is a predicate if, for every term x, P · x reduces to either TT or FF. A predicate P is trivial if either it always reduces to true, or always to false. This version of Rice's theorem derives a contradiction from the existence of a predicate P and...

Sqrt correctly computes Nat.sqrt.

Registers preservation: both reach states with the same registers.