Insights by Danielle Fong

notes from a girl from the future

Incompleteness and Halting. Gödel and Turing.

The following occurred to me on a run about two years ago:

It’s not given much press, but the the Halting Problem is intimately related to Gödel’s First Incompleteness Theorem. Indeed it produces it as a correllary. Historically, Gödel’s incompleteness results were proved by hacking arithmetic into a Turing complete system, and this is still how they’re explained today.

There’s a one-to-one bijection between computability of a function and provability of a statement. Hence, the short, and generally accessible proof that the Halting problem is not in general computable for an arbitrary input is also a proof of the ‘most important, surprising result in logic’, namely, that some results, which have may have a perfectly valid truth-value outside a system, cannot be proven within it. One only needs the notion of a computer to follow this line of thinking, which is, in essence, what Gödel did. But the Halting problem is much easier to grasp. I’ve had children understand it, though it does take some walking through!

The interesting thing about the Halting problem is that it’s unsolvable in full generality, independent of whatever special capabilities the system has available. To see this clearly, consider the proof.

Question: Does there exist a (halting) program H which, given any program P, figure out if it would halt, for any input I?

Assume there exists such a program H. Construct a program T as follows.

(Program P, Input I) => (Boolean Halts):
if H(P,I) is true run forever
otherwise halt

Now, call T on itself, with itself as an input. Our assumption presupposes that H always halts. If T would halt on input T, then T will run forever. And if T would run forever on input T, then T would halt. This is a contradiction, so no such program H would exist.

Read the rest of this entry »

On Outliers: What they represent, and why the Central Limit Theorem is Typically Off.

A Bell Curve

The central limit theorem states that if you have many small, independent, random variables, then their sum is distributed approximately as a bell curve. Strikingly, almost everything is made up of many small parts, and these parts don’t tend to influence each other very much.

So much of what can measure seems to fit a bell curve. This is why the normal distribution works. Because this assumption tends to work well, it is usually taken as a matter of course. Students are taught it, lecturers preach it, researchers apply it, and startlingly few stop to question it.

Suppose the variables are not small, or suppose they’re not independent. Suppose, under certain conditions, the value of one variable would seriously affect another. Suppose we’re talking about the buildup of snow on a mountain slope. Most of the time, snowflakes can gradually build, without significant effect. But once enough builds, you don’t find snowflakes resting calmly upon a drift. What you find is an avalanche.

Violent nonlinearities...

The sum total of snowflake movement isn’t what we might expect. The snowflakes on the top used to be lightly packed by the new, gradually coming down. The snowflakes on the bottom used to just sit there. But they’re not just sitting there. They’re moving fast, and they’re moving down.

Read the rest of this entry »

Quantum Field… Finance?

One morning around the graduate college dining hall, there was a gathering of physicists, finance students, and economists. The physicists are always quite amazed by those people who decide to forgo the life of the ivory tower, and choose to strike out into the real world, and so could not be kept from asking what the economists actually did. Furthermore, we could not be kept from wondering aloud what type of mathematical models they built and polished, and whether any of them had a physical interpretation.

One of the economists scratched his head, drew a sip of black coffee from his porcelain cup, and mumbled something about how a large proportion of the physics department of Harvard University was hired by a trading company, with the lure of riches beyond the pale of the meager imaginings of the physicists (“you mean I can afford a house?!”).

Read the rest of this entry »

Third Places

Caffe Strada

Tonight it’s winter in Berkeley. 53 degrees and raining, and outdoors, warmed by a heat-lamp, sheltered by an awning. I draw spiced apple cider through my lips. Classical music plays. An earbudded minority vote silently with their ears. Old men watch hooded students roll down the hills towards Telegraph Ave, Berkeley’s epicenter of hippiedom. Moist, newspapers ink the hands of activists, busily plotting the victories in the years long struggle to ‘save the oaks’. A young man lids a drink and smiles at me. Separated by glass, headphones, and 12 feet, I smile back. We wave.

There’s something magical about this place.

I don’t know anyone here. To arrive I flew four thousand miles from my place of growth. This place isn’t home. Yet there are few places that attract me so strongly. Modern life has been made private. And in doing so, life’s become a little lonely.

Builders of great cities have long understood that life would, but for misfortune, consist of more than work and one’s home. The vibrancy, energy, and community grown in what are sometimes called ‘third places’ played part in much of the world’s social, political and intellectual revolutions. The roles that the Roman forae, French salons, and English learned societies played in scholarship has been tremendous, as has been the influence of American chautauquas, worker’s taverns, and artist’s ghettos in social and political spheres. These public, accessible, talkative, comfortable playful places are magnets for folks of many stripes. Creativity can thrive there. Unconstrained by work’s implied unity of purpose, and decoupled from the tight bonds around one’s family and home, third places give marginal people, ideas, and voices room to grow, people to hear them, perspectives to challenge them, and food to help keep the conversation going.

Read the rest of this entry »