2 ms·
"very few approachable ones." I give credit to the author for trying, but having "enjoyed" an automata theory class and having read the textbook there is no "r
by VLM 13y ago
"very few approachable ones."
I give credit to the author for trying, but having "enjoyed" an automata theory class and having read the textbook there is no "royal road to P/NP" much like geometry. Have to take the entire long road to get to the end.
Analogy time... how would you explain recursion to a general populace without first explaining variables, functions, calling by ref vs value (or just the idea of calling a function at all, and that it returns something), stacks, the concept of procedural programming, the idea of a flowchart, some level of error detection so it doesn't run off into the weeds, some basic ideas about scalability... So Colbert invites you on his show and after the HN cheering dies down he says "I don't know much about computer science, could you explain recursion in plain language in a line or two?" Honestly, I'd probably say "No" or some joke about it being turtles all the way down which the general public wouldn't find very amusing but those who know would laugh.
- alex-g 13y agoThere is no royal road; or if we want some mystical woo, we could say that the journey is the destination, or something. I think that if you're trying to understand P-vs-NP it's not a matter of proceeding definition by definition. It's more like simultaneously approaching the question from lots of different angles, in order to build the mental connections between P-vs-NP and other topics. That includes Turing machines, formal languages and automata, reductions, big-O analysis, important concrete problems in P, NP, or neither, important algorithms and methods, and so forth. Recursion is probably the same way. For Colbert purposes you could certainly come up with some glib explanation. When I, or you, or anyone else, have learned recursion we've probably started with that, but then proceeded to build connections with induction, PL semantics, computer architecture, compiler/runtime implementations, and all the other allied topics. But I do think the earliest, most informal, explanation has its place too, because you have to start somewhere. The learning process is (at least for me) more like proceeding through lots of explanations of the same thing, at greater levels of detail and with different metaphors and external references, than it is like a linear progression from topic to topic.