Mtraven,
"There is nothing physical in common with these two activities, but surely they have something in common."
Having something in common is an easy hurdle. Pen and pencil is vastly more prone to error. You have to remember that when you conceptualize the similarities that doesn't mean the reality matches your conception. You might thing the counting of apples maps nicely onto the integers but it doesn't. Not for very large numbers. A pile of three apples maps nicely to the number three, but a pile of 1x10^34 apples would collapse into a black hole.
"You don't have to consider this mysterious if you don't want to. But it suggests to me that the reductionist way of looking at the world is, if not wrong, not that useful." Reductionism properly understood is but one tool in a toolkit, and one that has an extremely successful track record.
My position on this is very close to Dawkins.
"Reductionism is one of those words that makes me want to reach for my revolver. It means nothing. Or rather it means a whole lot of different things, but the only thing anybody knows about it is that it's bad, you're supposed to disapprove of it. (Dawkins)"
Remember we are talking here about your sentence: "Nonetheless, it is mysterious how physical systems with nothing physical in common can realize the same algorithm."
Why classify as "reductionist" my ability to directly understand what you find mysterious. I've got a degree in Computer Science so I damn well better understand why the same algorithms can run on different physical systems. In fact part of my job is designing such algorithms so they can run on physically different systems. An IBM mainframe, a Mac, and an Intel box are completely different physical systems even if you don't recognize that fact.
I also fully understand how pen and paper calculations and those done by a calculator or computer map onto each other. Thirty years ago computer time was far more valuable and access to time on computers was much less available. I had to actually write machine code with actual ones and zeros, and then hand simulate the running of those particular bytes on a computer. I did a respectable enough job to find bugs before I got shared time on the computer to actually run it. I understand precisely the mapping and why it works. Hell, I understand the electronics behind it.
The mystery evaporates with understanding.
Fundamental physics—quarks 'n stuff—is far removed from the levels we can see, like hands and fingers. At best, you can know how to replicate the experiments which show that your hand (like everything else) is composed of quarks, and you may know how to derive a few equations for things like atoms and electron clouds and molecules.
At worst, the existence of quarks beneath your hand may just be something you were told. In which case it's questionable in one what sense you can be said to "know" it at all, even if you repeat back the same word "quark" that a physicist would use to convey knowledge to another physicist.
Either way, you can't actually see the identity between levels—no one has a brain large enough to visualize avogadros of quarks and recognize a hand-pattern in them.
But we at least understand what hands do. Hands push on things, exert forces on them. When we're told about atoms, we visualize little billiard balls bumping into each other. This makes it seem obvious that "atoms" can push on things too, by bumping into them.
Now this notion of atoms is not quite correct. But so far as human imagination goes, it's relatively easy to imagine our hand being made up of a little galaxy of swirling billiard balls, pushing on things when our "fingers" touch them. Democritus imagined this 2400 years ago, and there was a time, roughly 1803-1922, when Science thought he was right.
But what about, say, anger?
How could little billiard balls be angry? Tiny frowny faces on the billiard balls?
Put yourself in the shoes of, say, a hunter-gatherer—someone who may not even have a notion of writing, let alone the notion of using base matter to perform computations—someone who has no idea that such a thing as neurons exist. Then you can imagine the functional gap that your ancestors might have perceived between billiard balls and "Grrr! Aaarg!"
Forget about subjective experience for the moment, and consider the sheer behavioral gap between anger and billiard balls. The difference between what little billiard balls do, and what anger makes people do. Anger can make people raise their fists and hit someone—or say snide things behind their backs—or plant scorpions in their tents at night. Billiard balls just push on things.
Try to put yourself in the shoes of the hunter-gatherer who's never had the "Aha!" of information-processing. Try to avoid hindsight bias about things like neurons and computers. Only then will you be able to see the uncrossable explanatory gap:
How can you explain angry behavior in terms of billiard balls?
Well, the obvious materialist conjecture is that the little billiard balls push on your arm and make you hit someone, or push on your tongue so that insults come out.
But how do the little billiard balls know how to do this—or how to guide your tongue and fingers through long-term plots—if they aren't angry themselves?
And besides, if you're not seduced by—gasp!—scientism, you can see from a first-person perspective that this explanation is obviously false. Atoms can push on your arm, but they can't make you want anything.
Someone may point out that drinking wine can make you angry. But who says that wine is made exclusively of little billiard balls? Maybe wine just contains a potency of angerness.
Clearly, reductionism is just a flawed notion.
(The novice goes astray and says "The art failed me"; the master goes astray and says "I failed my art.")
What does it take to cross this gap? It's not just the idea of "neurons" that "process information"—if you say only this and nothing more, it just inserts a magical, unexplained level-crossing rule into your model, where you go from billiards to thoughts.
But an Artificial Intelligence programmer who knows how to create a chess-playing program out of base matter, has taken a genuine step toward crossing the gap. If you understand concepts like consequentialism, backward chaining, utility functions, and search trees, you can make merely causal/mechanical systems compute plans.
The trick goes something like this: For each possible chess move, compute the moves your opponent could make, then your responses to those moves, and so on; evaluate the furthest position you can see using some local algorithm (you might simply count up the material); then trace back using minimax to find the best move on the current board; then make that move.
More generally: If you have chains of causality inside the mind that have a kind of mapping—a mirror, an echo—to what goes on in the environment, then you can run a utility function over the end products of imagination, and find an action that achieves something which the utility function rates highly, and output that action. It is not necessary for the chains of causality inside the mind, that are similar to the environment, to be made out of billiard balls that have little auras of intentionality. Deep Blue's transistors do not need little chess pieces carved on them, in order to work. See also The Simple Truth.
All this is still tremendously oversimplified, but it should, at least, reduce the apparent length of the gap. If you can understand all that, you can see how a planner built out of base matter can be influenced by alcohol to output more angry behaviors. The billiard balls in the alcohol push on the billiard balls making up the utility function.
But even if you know how to write small AIs, you can't visualize the level-crossing between transistors and chess. There are too many transistors, and too many moves to check.
Likewise, even if you knew all the facts of neurology, you would not be able to visualize the level-crossing between neurons and anger—let alone the level-crossing between atoms and anger. Not the way you can visualize a hand consisting of fingers, thumb, and palm.
And suppose a cognitive scientist just flatly tells you "Anger is hormones"? Even if you repeat back the words, it doesn't mean you've crossed the gap. You may believe you believe it, but that's not the same as understanding what little billiard balls have to do with wanting to hit someone.
So you come up with interpretations like, "Anger is mere hormones, it's caused by little molecules, so it must not be justified in any moral sense—that's why you should learn to control your anger."
Or, "There isn't really any such thing as anger—it's an illusion, a quotation with no referent, like a mirage of water in the desert, or looking in the garage for a dragon and not finding one."
These are both tough pills to swallow (not that you should swallow them) and so it is a good easier to profess them than to believe them.
I think this is what non-reductionists/non-materialists think they are criticizing when they criticize reductive materialism.
But materialism isn't that easy. It's not as cheap as saying, "Anger is made out of atoms—there, now I'm done." That wouldn't explain how to get from billiard balls to hitting. You need the specific insights of computation, consequentialism, and search trees before you can start to close the explanatory gap.
All this was a relatively easy example by modern standards, because I restricted myself to talking about angry behaviors. Talking about outputs doesn't require you to appreciate how an algorithm feels from inside (cross a first-person/third-person gap) or dissolve a wrong question (untangle places where the interior of your own mind runs skew to reality).
Going from material substances that bend and break, burn and fall, push and shove, to angry behavior, is just a practice problem by the standards of modern philosophy. But it is an important practice problem. It can only be fully appreciated, if you realize how hard it would have been to solve before writing was invented. There was once an explanatory gap here—though it may not seem that way in hindsight, now that it's been bridged for generations.
Explanatory gaps can be crossed, if you accept help from science, and don't trust the view from the interior of your own mind.