If I understand correctly, in the post you linked Scott is saying that Haitians are functionally innumerate, which should explain the difficulties with numerical sorting.

My point is that the partity function should be learnable even without basic numeracy, although I admit that perhaps I'm overgeneralizing.

Anyway, modern machine learning systems can learn to perform basic arithmentic such as addition and subtraction, and I think even sorting (since they are used for preordering for statstical machine translation), hence the problem doesn't seem to be a lack of arithmetic knowledge or skill.

Note that both addition and subtraction have constant circuit depth (they are in AC0) while parity has logarithmic circuit depth.