You ask them about Rule 110 and they stare at you blankly...
Stares back at you blankly. Is it a US thing?
Rule 110 from the domain of cellular automata. I would say it's debatable whether that's an essential part of digital (or computational) literacy. If you're getting into gaming or other world simulation work, then yes.
Rule 110 is also the simplest set of known "rules" for a cellular automata that can act as a Universal Turing Machine. I would say knowing this (and knowing what a UTM is, and why it is important to computer science) -is- an essential part of digital literacy for a computer scientist (though not necessarily for child or even an adult learning programming), which is what I was getting at.
The fact that there are people out there graduating from supposed computer science courses without understanding the importance of Rule 110, without understanding what a UTM is, without knowing the contributions of Turing (and Church, and Russell, and Whitehead, and...) to computational theory - it boggles the mind.
At one time, there was this fear that ordinary people wouldn't understand (or care) about what goes on "inside the box", just so long that it worked, and woe to the world should it break. Only the "high priests" of computing would know or understand. What I am now seeing is that the supposed "high priests" of computing now being educated, are also being educated in such a manner that even they don't understand what is going on "inside the box"! It would be like a newly educated phD in chemistry not understanding covalent bonds, instead saying "I'll leave that up to the physicists" - or some such shenanigans!
This really bothers me - computer science encompasses so much - to not understand the basics of it does a real disservice to the field. If you don't understand Rule 110 or why it is important, if you don't understand what a UTM is, or why it works... I'm finding this difficult to relate, but we're (our species) is getting into the territory of learning how DNA really works; at its core, we understand that it -is- the "tape" (indirectly via RNA and tRNA) of a UTM, and that the complexity known as the ribosome is the read/write head and interpretor. We still don't completely understand how the ribosome works, but it is likely going to take the knowledge of UTMs, cellular automate, and Rule 110 (among others) to figure it out (along with how the whole DNA coding system works to generate proteins, etc).
That's the importance of it for computer science, and for biology. We are on the cusp of altering our programming on such a fundamental level it is both exciting, intriguing, frightening and mind-boggling all at once. It makes me giddy knowing there are people out there playing with this stuff (and I sincerely wish I could be a part of it, but my understanding and education does not come close to what is really needed).
To see some schools here in the USA (I can't speak for other countries) gloss over such knowledge frustrates me; perhaps I'm being unfair, maybe this knowledge is considered in another area of the computer science curricula at these schools (though I tend to wonder why it would be broken out like this - it seems that it isn't a requirement, though it really should be - I sometimes wonder how you could expect to write an emulator, say - without understanding what a UTM is).