if you genuinely understand something — really, truly understand it — then it doesn’t seem complicated and you can explain it rather simply
Uh, no? Some things are inherently complex. Try explaining how the Y combinator works (not what it does - why it works) to a layman in simple terms. I don't think it can be done.
I once explained it to a literature PhD, weak at math, who'd taught a course on writing under censorship. I told a short self-referential story whose structure mirrored the Y combinator's -- about tricking censors charged with banning self-referential stories.
(Yes, many things are just complicated. But confusing explanations usually could be improved, just as confusing code usually could be lots clearer.)
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?
Of course, the raw text above won't suffice. However, you will note that the notation I used is learned in high school.
To me high school mathematics are quite accessible, though I understand that most people forget it as soon as they can. So, I just assume I will have to start from kindergarten arithmetic. And I had, in fact.
I once explained functions to a 14 year old girl. I went as far as high order functions (function composition, I think), and she understood. I checked, she could answer my questions correctly. She was bright, but still. I think I was able to explain functions in rather simple terms.
Now, if I can explain functions to a 14 year old girl, the rest is certainly doable.
Phew. Done. And I didn't use any knowledge that a high school kid shouldn't have. Did I miss something?
One thing. How long it takes most people to understand a concept. It took me much more than 15 minutes to understand what a function is in high school, and I have spent far more than 15 minutes explaining it to other people. And it definitely took more than 5 minutes to understand the concept of a recursive function.
And you are assuming they have knowledge of concepts like string and whether or not they are printable...
Now, understanding a concept and grasping it to the point it becomes part of yourself are not the same thing. I don't expect people to remember the whole thing in less than an hour. Just to understand it, and being able to read supporting material without drowning.
A string is a sequence of characters, and "printable" is some arbitrary property. I would of course say as much in my real explanation.
Understand that my comment was just a sketch. I wonder If I shouldn't actually try to flesh it out. A video, maybe…
Uh, no? Some things are inherently complex. Try explaining how the Y combinator works (not what it does - why it works) to a layman in simple terms. I don't think it can be done.