3 ms·
To me, the most interesting observation about this came from computability theory, of all places. To some extent, in CS we study completely arbitrary construct
by tikhonj 14y ago
To me, the most interesting observation about this came from computability theory, of all places.
To some extent, in CS we study completely arbitrary constructs--Turing machines. Turing machines, indeed, are just tools: they're a simple model of a computing machine that makes sense just based on existing technology. Or perhaps we study the lambda calculus which, while less arbitrary than a Turing machine, is still obviously a tool created by a mathematician to perform a particular task. Or maybe we study existing programming languages which are even more arbitrary and contrived than Turing machines.
All these models? Obviously just tools created by people, often for very specific tasks.
But then a surprising fact emerges: no matter which tool we use, we can accomplish exactly the same things! The set of programs we can run is the same--these arbitrary models are all Turing-complete. Somehow, the notion of Turing completeness is extremely robust against all the different models of computation we've come up with.
In fact, it turns out that any "reasonable" model is going to have the same power. And in this case, "reasonable" actually is reasonable--the main restriction is that the model can only do a finite amount of work at each step.
So while any given model is arbitrary, the class of problems they can solve isn't. Rather, this class naturally emerges from the models. It's a natural property of computation rather than merely a human contrivance.
A similar thing happens when you look at programming and logic. We all know about Curry-Howard: it turns out that writing a program and writing a proof are analogous actions. You can map proof from a logic system to a program in a programming language and vice versa. While both logic systems and programming languages are somewhat arbitrary themselves, the fact that they're somehow equivalent hints at some underlying principle.
And that is why I'm fascinated by category theory, which seems to embody this underlying principle. It unifies proofs and programs with categories in what is very much like an extension of Curry-Howard. But then it goes further, and uses exactly the same model to talk about a whole bunch of different things: set theory, topology and even theoretical physics! (And, doubtless, countless more I'm simply unaware of.) While any of these fields are again just tools--including categories themselves--it seems that they all reflect some deep underlying structure.
Now, of course, I haven't addressed a very important point: is this "underlying structure" a reflection of the universe or just a reflection of the human mind? Is it perhaps a reflection of the underlying structure of reasoning itself?
Coming up with a reasonable answer to any of these questions is going to take a lot more thought and a lot more writing, but I lean towards the latter. The underlying ideas--the minimal starting points that are enough to uncover the structures I talked about--are far too simple to just be an artifact of the human mind which is itself wantonly complex.
So perhaps I am a Platonist myself. I've never thought about it in those terms, but it seems broadly consistent with my general ideas about life, the universe and everything.
- cscheid 13y agoThis is a great post, but > they're a simple model of a computing machine that makes sense just based on existing technology Turing machines were invented before any working (almost-) universal computer existed.
- tikhonj 13y agoHah, yes. I was actually thinking of a literal tape made of paper, or something to that effect. As compared to the lambda calculus which is based entirely on logic rather than some allusion to the real world.
- tel 13y agoCategory theory is beautiful because it's so unavoidable. We might critique Turing machines for being tied intimately to our particular mode of thought—both Turing tape and lambda calculus are a certain kind of specific, at least in comparison to category theory. (Not that I'm arguing that any computational models are somehow not touching on another kind of Platonic ideal) Category theory arises from probably the simplest imaginable notions of "transformation". There's no way to not critique me for being anthropocentric, but it's hard to imagine an alternative theory where this doesn't exist.