@futurebird I think that's a very good point. I would blame this on CS being young, and on an inherent tension between "teach people to code (vocational) because it's useful" and "teach people to code (principled) because it's important knowledge", so to speak.

I do think there's a bit of a curriculum for the latter: automata, language hierarchy, TMs, important limits of computation (halting problem, Rice's theorem), space and time complexity, compilers, interpreters... but it's probably hard to do this in pre-uni? Though I'm always a bit sceptical about that sort of thing too, back when calculus arose people thought it was too difficult.

@modulux

We touch on the halting problem a little in the hardware unit of all places. We make a bit adder from transistors and logic gates. Talk about bootstrapping (but we don't do bootstrapping which I would like to change) then we talk about Turing machines and use https://turingmachine.io/

Basically, I want them to have some sense of where these machines come from, how they are made. A feeling that it's not just magic.