Bernard (almost) gets it right

Theoretical computer science would exist even if there were no computers. Computer science is not bound by the laws of physics; it is inspired by them but, like mathematics, it is something that is completely invented by man.

Not true! Long before Australopithecus or even Dilpodous walked the earth, ages before the primoridal slime dreamed of phtosynthesis, eons before the sun coalesced from the scattered ashes of its garishly suicidal parents, 2+2 was 4, π was transcendental, any formal system powerful enough to include arithmetic admitted true but unprovable statements, and comparison-based sorting algorithms required Ω(n log n) time. These are not mere human inventions, Bernard, but deeply humbling discoveries. These are necessary truths, in a far more fundamental sense than the so-called laws of physics.

Scott gets a little closer:

The first lesson is that computational complexity theory is really, really, really not about computers. Computers play the same role in complexity that clocks, trains, and elevators play in relativity. They're a great way to illustrate the point, they were probably essential for discovering the point, but they're not the point. The best definition of complexity theory I can think of is that it's quantitative theology: the mathematical study of hypothetical superintelligent beings such as gods.

Update (Feb 19): Bernard graciously points me to his longer essay, in which he not only hits the target smack in the center, but fires several arrows directly into their predecessors' feathery back ends. Load up your iPod with verlan-laced rap, or perhaps some vintage Wesley Willis, and read the whole thing.

An algorithm is, in essence, a work of literature.

Comments

[Mikey Starfish]

>These are necessary truths, in a far more fundamental sense than the >so-called laws of physics.

Not true! Or maybe more accurately: who knows! You may buy into Platonic mathematical realism, but remember that there are plenty of (well-reasoning) formalists, empiricists, and wacky postmodern social constructivists who don't.

[HH]

Well, here is my 2cts, without evenly remotely claiming to know anything about this:

Isn't mathematics (including theoretical computer science) a formal system? It did not exist before we came up with the form. 2 + 2 was never 4 before we set up a system (chose some axioms etc.) in which we say that it is true that 2 + 2 is 4.

Mathematicians create a complicated world from simple rules, so complicated that after setting the rules, we are surprised to discover what we have created. As far as I understood, it is essentially the same in physics, or in law, for that matter. The main difference between these academic disciplines being that:

- Mathematicians and theoretical computer scientists are happy with their axioms: they have created their world and are now busy discovering it. They do not care much about how their world looks like: they just want to see it.

- Physicists are still in doubt about their axioms. They have more or less created their world but they would really like their world to look like the real world around them (so that it helps explaining it). Therefore they keep running tests to check if the real world matches their world and if they should revise the latter.

- Jurists are in doubt about their axioms all the time: their problem is that throughout the ages, they continuously change their mind about how they want their world to look like.

Mathematicians making humbling discoveries? Their main achievement is that they managed to join forces to study a relatively stable world of their own creation for many generations, and persist regardless of what they find, so that they have the time to study their world in great depth. This has proven to be very useful, although sometimes, mathematicians and theoretical computer scientists wander off into the world they created themselves, only to never be seen alive again.

2 + 2 was never 4 before we set up a system

So when you take two apples and add two apples you usually get five oranges, unless you have set up an axiomatic system beforehand in which case you do get four apples?

[HH]

You first have to define such things as "two apples", "and", "four apples", and equivalence. Doing so is a human invention.

[Scott Henson]

Though not a mathematician, I have to agree with our host that math is not just a human construction. As a wiser soul said to me recently, if you don't think your dog can count, show Fido three dog treats, put them in your pocket, then give him two of them. :)

Thanks, too, for linking to Aaronson's neat piece.

[JeffE]

When I was a teenager, I briefly flirted with solipsism—the self-absorbed but logically consistent philosophical position that nothing exists except when I perceive it. Inevitably, when I would attempt to explain to one of my adolescent peers that he didn't REALLY exist, he'd say "Oh yeah?" and smack me in the head.

Later I read warm fuzzy quantum consciousness philosophers espousing the theory that the probabilistic emergence of the human mind collapsed the cosmic wave function, truly bringing the universe into existence for the first time. Now I wonder why someone don't just smack these modern geocentrists in the head.

Certainly I've played the game "let's make up rules and see where they go". I might have made up the rules, but I certainly didn't make up the fact that THESE rules lead to THOSE conclusions. The formal systems themselves may be human inventions, but the consequences of those simple rules spring forth of their own accord.

When plants grow from seed, the farmer may claim (with some hubris) that he put those plants there. But they did not create the process by which THIS seeds leads to THAT plant. Agriculture is a human invention. So is domesticated corn. But genetics is not.

When a pitcher throws the ball across home plate, she is exploiting the universe's desire to move objects along paths of minimum energy. She lets the ball go, knowing from experience that it will fly through the strike zone, but she does NOT direct the ball through its trajectory. This correspondence between action and consequence—moving THESE muscles like THIS will put the ball THERE—was never invented, but is discovered and rediscovered by every child who picks up a rock. Baseball is a human invention. The trajectory of a thrown baseball is not.

Math is the same, only more so. The language we use may be an invention—in as much as anything that evolved over millenia can be considered an invention—but the message is not.

At least, that what it looks like here inside my head. All you zombies may have another opinion.

[HH]

"Math is the same, only more so. The language we use may be an invention—in as much as anything that evolved over millenia can be considered an invention—but the message is not." Sure, but indeed, as you illustrate above, this also applies to other academic disciplines.

[David Klempner]

The difference, however, is this necessary truth business. The notation (and, maybe, arguably, the significance) is all that is man made, and the underlying symmetries and properties are still there whatever notation you might want to use. That's the whole point of algebra. Unlike genetics, these symmetries are still there even if you are in an entirely different universe.

Oh yeah, and the "(well-reasoning) formalists, empiricists, and wacky postmodern social constructivists who don't [buy into Platonic mathematical realism" are wrong.

[Brian]

Batman got on my nerves.
He was running me amok.
He ridiculed me, calling me a bum.

--You first have to define such things as "two apples", "and", "four apples", and equivalence. Doing so is a human invention.

No I don't. I have two apples in front of me, and I don't need to define them anymore that you have to define anyother concept from the real world you wish to talk about. Say if you want to describe the fundamental physical fact of gravity you need to define what you mean by gravity. This does not make gravity an artificial construct. Ditto for the apples.

[Joe]

Though I agree with the overall message that computer science and complexity theory in particular are pretty fundamental, Bernard's longer paper doesn't convince me of that. One major mistake is that it conflates the idea between a problem overall being hard and a particular instance being hard. The question of whether P=NP has little to do with rather particular instance of NP complete problems are hard.

> Ever wondered if your iPod's 5000-tune library is rich enough to let you compile a playlist of a thousand songs, no two which have ever been played back-to-back on MTV? Let's hope not, because not even an IBM Blue Gene/L could do the job in less time than has passed since dinosaurs were last seen roaming the earth.

If my iPod has 1000 songs that have never been played on MTV, I won't need Blue Gene to make a playlist containing them.

[JeffE]

Superman had a big "S" on his chest.
He was drawing on my nerves.
I got mad at his drunk ass.
I gave him a war hell ride.

Spiderman thought he was bad.
He was screwing my day up.
He was bothering my girlfriend.
He tried to con her out of $70.

[HH]

It seems we agree that there is no essential difference between academic disciplins regarding the role of definitions (even if we may disagree on what that role is), so we can put that discussion to rest. Then David Klempner argues: "The difference, however, is this necessary truth business. [...] Unlike genetics, these symmetries are still there even if you are in an entirely different universe." I agree. Truth in mathematics is context-free: it can be established without considering the universe in which the research takes place. By choice, this is not true for physics, or for law. Does that make mathematical truths more fundamental truths? Maybe. It depends on what you consider to be the foundation of your studies. Is it what you can prove? Is it what in the world around us you are trying to understand? Or is it how you want the world around you to be?

Mathematicians who can take different viewpoints here, will not need to contemplate early retirement when somebody proves that P is NP. Formerly difficult problems will still be difficult and formerly easy problems will still be easy. Heuristic solutions that used to be practical will still be practical, and polynomial-time algorithms with exponents > 1 will still be pretty much useless for massive amounts of data.

That notwithstanding, I think that the P = NP question is a good illustration of what theoretical computer science is about.

Disclaimer - I profess to be an absolute ignoramus on this and most other subjects. Reply only if you think this merits a response :)

You said :
>eons before the sun coalesced from the scattered ashes of its garishly suicidal parents, 2+2 was 4, π was transcendental, any formal system powerful enough to include arithmetic admitted true but unprovable statements, and comparison-based sorting algorithms required Ω(n log n) time.

Perhaps. Your point is well taken.

>These are not mere human inventions, Bernard, but deeply humbling discoveries. These are necessary truths, in a far more fundamental sense than the so-called laws of physics.

This is where i get a little jittery. What do you mean by far more fundamental that the laws of physics? It seems to me, your "necessary truths" are necessary only within the framework imposed by the laws of physics of our universe.

My contention is that 2+2=4 only post the big bang and the establishment of the laws of physics in our realm. Even if we dont know all the axioms yet, or have trouble verifying their correctness, let us simply assume that they (a set of absolute axioms and rules governing our universe) exist. Now it is only after they came into existence that you could make a claim that 2+2=4. Representation apart, the intrinsic meaning of 2 apples + 2 apples = 4 apples is governed by physical law.

So assume there exists a definitive "physics(small p) of the universe". Physics(capital P) the subject, is just a formalism to represent/capture the same. Mathematics is again a formalism, and like Physics, its axioms are defined to reflect the reality of physics.

Theres no saying 2+2 apples dont coalesce into 5 oranges given another physical reality. Wouldnt your mathematics change then? So in a sense mathematics is as old, and not any older than the universe.

[JeffE]

Even in our universe, 2 hyrogen atoms and 1 oxygen atom make up 1 water molecule, but that doesn't mean that 2+1=1.

I can imagine a physical universe where physical constants are different, or where Newtonian mechanics is actually correct, or that has six spatial dimensions instead of three (or eleven). Those universes are physically inconsistent with ours, but (as far as I know) they would still be logically consistent. But a universe where 2+2=5 would be LOGICALLY inconsistent, even with itself.

Oh, sure, I can imagine consistent logical systems where the sentence "2+2=5", but only by giving at least one of the symbols "2", "+", "=", and "5" different meanings. But then it isn't the same sentence at all! In logical terms, the two systems don't have a common model. It's like saying you can imagine a country where people sit on email to take a crap, instead of reading it on their computer. In fact, there is such a country: France! (Email is the French word for enamel.)

And yes, our choices about which parts of the mathematical universe to explore have been heavily (perhaps even exclusively!) influenced by our experience in the physical universe. But mathematics isn't about the physical universe. It's about abstract entities, some of which crudely describe attributes of the physical universe—or as Plato would probably insist, some of which are crudely approximated by attributes of the physical universe. The intrinsic meaning of "2+2=4" isn't "two apples and two more apples is four apples". No apples are required; 2+2 would still be 4 even if there were no apples. So why should the rest of the universe be required?

[Snehit]

>The intrinsic meaning of "2+2=4" isn't "two apples and two more apples is four apples". No apples are required; 2+2 would still be 4 even if there were no apples. So why should the rest of the universe be required?

Analogously, that would be like saying "events 1,2 and 3 took place in so and so chronological order before the big bang", when in reality time didnt exist. Consequently "chronological order" would have no meaning. So, arguably, didnt logic or mathematics, as we define it.
All the same we claim that they are abstract, and not constructs like time, which are manifestations of a physical reality. A counterargument would be : so what? Logical consistency seems to me to be a concept thats defined within, and therefore whose validity is restricted to, the universe.

Assume that at the outset (pre big bang), there was/is a meta-model of sorts, where 2+2 could be anything. The mathematical reality we see today could be just one branch - one instantiation of the same. The same for logic. Of course this is all handwaving conjecture.

Like you said, changing the semantics associated with the terms in the sentence "2+2=5", would mean it doesnt share a common model with the "2+2=4" system (our mathematics). Why must they share a common model? Simply because we wish to compare the two using the same rules of logic (using which we can claim that 2+2=5 is logically inconsistent). Shouldnt this other model be entitled to its own logical framework? Why must it be subjected to the rules that prevail within our system, if it doesnt exist within it in the first place?

The apple example only served to confuse my argument. As if i dont have enough trouble putting my point accross already. I didnt say "2+2apples=5oranges" to exemplify different interactions in a different physical system. I meant it as 2+2=5 is true if you change the rules of logic.

Does it all still sound like drivel? :)

[JeffE]

No, no, not at all. "Events 1,2,3 took place in chronological order" isn't undefined independently of the physical universe because ORDER requires physicality, but because TAKING PLACE requires physicality. The abstract mathematical concept of a total order requires no physical anything.

(I prefer to say "if the universe didn't exist" to "before the big bang" because, to quote Hawking, the latter phrase may be as meaningless as "south of the South Pole". And yes, I recognize that "if the universe didn't exist" is also arguably meaningless.)

Similarly, "time" can be defined abstractly as the weird dimension in a certain metric defined over a certain four-dimensional manifold. That's a purely abstract, non-physical definition; although it profitably models (an abstraction of) the physical world, it's not really about the physical world.

"Why must they share a common model?" Because that's what it means for two mathematical sentences to have the same meaning. 'Model' is a technical term. No, the alternate logical system need not conform to the rules we're used to, but there must be a common logical system that accurately models them both. Otherwise, in what sense does your 2 mean the same thing as my 2??

Sorry, but yes, it all sounds like drivel to me. But it's fun drivel!