Tag Archives: computer science

(Yet Another) Theory vs Systems Ramble

Theoretical research is like a mighty battle against a noble King. Your foe is not a ruthless warlord — he, on the other hand, is the master tactician that has seen hundreds of wars. He has a versatile and innumerable army, highly trained, unflinching and ready to make a kill when they have to.

Nevertheless, you can trust the king to not breach the rules of war. His army will take you head on, face to face, and you can count on them to fight a fair battle and not to backstab you. You can fight a fair, disciplined war, and count on your foe to do the same. You can even challenge the King to a game of chess and have the winner take the land.

However, you can’t get a mallet and bash your way through the army. There is no sidestepping and backstabbing the king. Your opponent is too good for that. To win, you have to bring in your best; bring in a clever, disciplined and dedicated fight, and hope to bring the King to your knees in the end.

Systems research is plenty different. It is like battling a ruthless werewolf. It knows no rules, other than to go for your neck. You are up against a mindless beast. Your tactics or strategies won’t help you here—only your instinct, and generous helpings of luck will. You’ll need to move fast and keep an eye behind you to survive.

However, killing the beast might be as simple as one simple, clean thrust of your sword right into it’s heart. The harder part is to survive till you get to make the swing.

The Irony of Logic

The Illusion of Black and White

Mathematical Logic is a queer field. Its ways are abstract yet rigorous, its results incredibly simple yet often surprising. It is also a much under-appreciated field – its concepts and results, besides being so fundamental to the mathematical formalism we are familiar today, is the only reason why we have computers.

Logic also is an ironic field, in fact, quite profoundly so.

Look around, look at the real world, in all it’s complexity and ambiguity; and try to frame a statement about it that is purely binary – a statement that is either True or False entirely, but never in between.

The world is not black and white. It’s really, really gray. — Joshua Topolsky

You’ll probably be surprised that you are unable to do so. The real world is never black-and-white, there is little about the world that fits an absolute “yes” or “no”.
The real world doesn’t afford the luxury of being so flawlessly deterministic. Things are often indeterminate. Physical quantities settle down at intermediate values. Things come in whole or part. It’s a whole mess of “almost”, “somewhat”, “quite” and “fairly”. Mapping this gray, gray world to an abstract, black-and-white model is seemingly a crude abstraction to make – almost shockingly so. In this regard, the entire field of Logic feels so badly grounded.

Yet here we are, with a profoundly developed field of study that frames a large bodies of our scientific studies and technological endeavors; yet is nearly diametrically opposite to what we experience in the real world. If this isn’t irony, what is!

About Automata Theory – The Need of an Axiomatic Approach

JARGON ALERT: This post is related to Computation Theory, and anyone but Computer Scientists or Engineers (or budding ones) might find this crap.

Formal Languages and Automata Theory – FLAT in short – is what our paper on Computation Theory, Automata and Language Theory called; a core paper for our Computer Engineer course. Automata and theoretical computer science were fields that used to interest me from when I was a high-school student (that was when I first read about the halting problem), and it still does – however, I found the paper less than extremely appealing – it was good and rather easy to handle, but somewhere lacking the elegance.

When I started to think why, I was asymptotically approaching a possible answer – the lack of a proper axiomatic approach. The entire science is infested with a lot of conjectures, lemmas, models and theorems, many of them fundamental and clever in their own respect – however, most of the arguments and proofs where rather tangled, with a lot of obscure number theoretic and inductive arguments involved. Does this point to the lack of an axiomatic base to the entire field?

While recursion is elementary to language and automata theory, and recursion and induction a straightforward way to approach things, this can’t be no reason that there cannot be an axiomatic approach to the science, building up on some basic axioms, and constructing further proofs and dijectures upon these, without needing to resort to contorted verbal arguments or qualitative descriptions. Could this be possible?

I really hope this is possible and might probably pursue this very aspect as my term-end project; axiomatizing the field of theoretical computer science. If I succeed, that would be the achievement of my life as a computer scientist. Thoughts?