I've taught C, Java and Python at a university and (a little) at the high school level. I have noticed two simple things that people either surmount or get stuck on. The first seems to be even a basic ability to keep a formal system in mind; see the famous Dehnadi and Bornat paper. The second, I have heard less about: in programming, it's the idea of scope.

The idea of scope in almost all modern programming languages goes like this: * A scope starts at some time (some place in the code), and ends somewhere later. * A scope can start before another ends; if so, it has to end before the "outer" scope. * Inside a scope, objects can be created and manipulated; generally even if another scope has started. * Unless something special is done, objects no longer exist after a scope ends. * Pivotally (this seems to be the hardest part), a objects can be created with one name in an outer scope and be referred to by a different name in an inner scope. Inner scopes can likewise create and manipulate objects with the same names as objects in an outer scope without affecting the objects in that outer scope.

It's really hard for me to think of an analogous skill in the real world to keeping track of N levels of renaming (which may be why it gives students such difficulty?). The closest I can think of is function composition; if you don't have to pick your way through symbolically integrating a composed function where the variables names don't match, I have pretty high confidence that you can manage nested scopes.

EDIT: There are two other, well-known problems. Recursion and pointers. I've heard stories about students who were okay for a year or two of programming courses, but never "got" recursion or, never understood pointers, and had to change majors. I've seen students have enormous difficulty with both; in fact, I've passed students who never figured one or the other out, but managed to grind through my course anyway. I don't know whether they dropped out or figured it out as their classes got harder---or just kept faking it (I had team members through grad school that couldn't handle more than basic recursion). I'm not inclined to classify either as "programming gear" that they didn't have, but I don't have data to back that up.

I think you should give a more precise definition of the aptitude needed to be labelled has-a-gear.

I program for a living, and I would like to think that I fall among "those who can" on the bimodal distribution (if one exists). I've seen programmers and non-programmers of all levels of ability (except for far above mine, because those are hard to recognize). One man's programmer is another man's deadweight.

Individual people grow in talent until they stop (and maybe they resume later). So if there exists a test to predict whether they'll stop at some future level, it probably doesn't involve actual programming. (For instance, testing people's understanding of variable semantics is pointless unless you've taught them those semantics first.) It would have to test something else that happens to be strongly correlated with it. So

Incidentally, this was this was recently discussed on Programmers Stack Exchange:

One more behavior: I took a survey (which I can't find again) about hugging from behind, and everyone who answered hated it, except for a few who had a short list of people who they permitted it from.

I didn't have a random or especially large sample, but the unanimity was striking.

I copy and pasted the "Time To AI" chart and did some simple graphic manipulations to make the vertical and horizontal axis equal, extend the X-axis, and draw diagonal lines "down and to the right" to show which points predicted which dates. It was an even more interesting graphic that way!

It sort of looked like four or five gaussians representing four or five distinct theories were on display. All the early predictions (I assume that first one is Turing himself) go with a sort of "robots by 2000" prediction scheme that seems consistent with the Jetson's and what might have happened without "the great stagnation". All of the espousers of this theory published before the AI winter and you can see a gap in predictions being made on the subject from about 1978 to about 1994. Predicting AGI arrival in 2006 was never trendy, it seems to have always been predicted earlier or later.

The region from 2015 thru 2063 has either one or two groups betting on it because instead of "guassian-ish" it is strongly weighted towards the front end, suggesting perhaps a bimodal group that isn't easy to break into two definite groups. One hump sometimes predicts dates out as late as the 2050's, but the main group really likes the 2020's and 2030's. The first person to express anything like this theory was an expert in about 1979 (before the AI winter really set in, which is interesting) and I'm not sure who it was off the top of my head. There's a massive horde expressing this general theory, but they seem to have come in a wave of non-experts during the dotcom bubble (predicting early-ish) and then there's a gap in the aftermath of the bubble, then a wave of experts predicting a bit later.

Like 2006, the year 2072 is not very trendy for AGI predictions. However around 2080 to 2110 there seems to be a cluster that was lead by three non-expert opinions expressed in 1999 to 2003 (ie the dotcom bubble aftermath). A few years later five experts chime in to affirm the theory. I don't recognize the theory by name or rhetoric but my rough label for their theory might be "the singularity is late" just based on the sparse data.

The final coherent theory seems to be four people predicting "2200", my guess here is just that its really far in the future and a nice round number. Four people do this, two experts and two non-experts. It looks like two pre-bubble and two post bubble?

For what its worth, eyeballing my re-worked "Time to AI" figure indicates a median of about 2035, and my last moderately thoughtful calculation gave a median arrival of AGI at about 2037, with later arrivals being more likely to be "better" and, in the meantime, prevention of major wars or arms races being potentially more important to work on than AGI issues. The proximity of these dates to the year 2038 is pure ironic gravy, though I have always sort of suspected that one chunk of probability mass should take the singularity seriously because if it happens then it will be enormously important, while another chunk of probability mass should be methodologically mindful of the memetic similarities between the Y2K Bug and the Singularity (i.e. both of them being non-supernatural computer-based eschatologies which, whatever their ultimate truth status, would naturally propagate in roughly similar ways before the fact was settled).

People say they hated it at first, but over time, grew to love it. One must be trained to like it.

This can raise a warning flag but I've experienced this myself with coffee and some other foods. It didn't take any training for me but a lot of people who like beer don't like the bitter, hoppy beers like IPAs without some training - and while pretentious beer snobs are annoying and amusing on several levels I can't quite doubt them when I have the same preferences.

Phil, I'll remind you of your own comment:

Incommensurate thoughts: People with different life-experiences are literally incapable of understanding each other...

Analogy: Take some problem domain in which each data point is a 500-dimensional vector. Take a big set of 500D vectors and apply PCA to them to get a new reduced space of 25 dimensions. Store all data in the 25D space, and operate on it in that space.

Two programs exposed to different sets of 500D vectors, which differ in a biased way, will construct different basic vectors during PCA, and so will reduce all vectors in the future into a different 25D space.

In just this way, two people with life experiences that differ in a biased way (due to eg socioeconomic status, country of birth, culture) will construct different underlying compression schemes. You can give them each a text with the same words in it, but the representations that each constructs internally are incommensurate; they exist in different spaces, which introduce different errors.

It seems entirely plausible that a person's appreciation of a piece of music depends strongly on all the music to which she's previously been exposed. Two different observers with different music-histories may have very different internal representations of the same piece of new music. A given piece of music may be well-formed or high quality in one representation, but not another.

This is perfectly well true, but I'm not interested in addressing this because I have never known this to be anyone's sufficient objection to eating meat.

Would you eat a well-treated chicken? How about a deer instantly killed by a Predator drone equipped to vaporize its brain faster than neurons react?

I don't want to die but I'm OK with other people dying. In most cases, to put it bluntly, I don't think it is a significant loss (although it might be a personal loss to me). There are some people in the world I'd fight very strongly to see them remain alive for as long as possible, even if they were reluctant (I speak here not of friends and family but of valuable contributors). But I've never understood the desire to save every life. It seems obvious to me that only a few people are here for the Life's Great Adventure and most are killing time until they kick the bucket. I take some issue with that (I think they're falling short of the Good) but it's not a problem that would be fixed by convincing them to change their attitudes towards death (the problem is their attitude towards life). The reason I want to live indefinitely is straightforward: I have some really longterm goals.

Isn't it better if we blow the money on cocaine and hookers, to maximize the pain of giving it to us? :) (Seriously though, this is highly valuable feedback; really appreciate it!)

StickK.com originally envisioned being the beneficiary of people's commitment contracts but found that people would not go for that. That should certainly give us pause, but here's why we think it could make more sense in our case:

1. The exponential fee schedule [http://beeminder.com/money] makes a big difference. In addition to removing the difficult choice about how much to risk, it makes it feel more reasonable for Beeminder to be the beneficiary. You're starting with a small amount at risk after you've already gotten value out of Beeminder. (That could change if you climb up the fee schedule very far though so we need to keep thinking about options for specifying other beneficiaries.)

2. I think we're fundamentally providing more value than StickK because of the pretty graphs and storing your data.

As for where the money is going, well, it's still on the early side to say much about that, as you can see from these dogfood graphs:

http://beeminder.com/meta/atrisk http://beeminder.com/meta/paid

We'd love to hear more thoughts on this, like are we in fantasyland with the above rationalizations for being the beneficiary?

O(log n) stack size is allowed (since normal loop would also take O(log n) just to write down n), but you need to keep each stack frame constant size, not O(log(n)), since otherwise you get O(log^2 n) total space complexity.