I think it can be done in 40 minutes, one hour tops. 15 minutes to explain what a function is:
f1 : ℝ -> ℝ
f1 = x |-> a × x + b
f2 : (ℝ × ℝ) -> ℝ
f2 = (x, y) |-> x + y - 1
f3 : ℝ -> ℝ -> ℝ
f3 = (x, y) |-> x + y - 1
(I fear curryfication can't be skipped)
f4 : (ℝ -> ℝ) -> ℝ -> ℝ
f4 = f |-> x |-> f(x)
f5 : ∀ a, ∀ b, (a -> b) -> a -> b
f5 = f |-> x |-> f(x)
(Polymorphic types may be left out, but I think
they're important)
Then 5 minutes to explain what a recursive function is: fac : ℕ -> ℕ
fac = 0 |-> 1
x |-> x × fac(x - 1)
Then 5 minutes to present a fix point combinator… fix : ∀ a, (a -> a) -> a
fix = f |-> f (fix f)
(or we could just say that a is ℕ)
…and implement the factorial with it. ffac : (ℕ -> ℕ) -> ℕ -> ℕ
ffac = f |-> 0 |-> 1
f |-> x |-> x × (f(x - 1))
fac : ℕ -> ℕ
fac = fix(fac)
We can do a step by step, normal order evaluation. If any question is asked, just say that evaluating the arguments first just won't work here.Then, maybe 5 more minutes to explain the concept of self reference without actually naming oneself:
~PM(~P)
Where you assume that for any "printable" string X, PX is true, ~PX is false; that for any X such that XM(X) is printable, PM(X) is true; and that any printable string is true, or just don't have the form PX or ~PX. You will note that ~PM(~P) is true and not printable, because it basically says "I am not printable". This is an anonymous self reference.Finally, we can go on and present the Y combinator itself. It does the same thing as the "fix" combinator, we just have to show that's because there is an anonymous self reference somewhere. I think it can be done in 10 minutes.
Phew. Done. And I didn't use any knowledge that a high school kid shouldn't have. Did I miss something?