"It's all just bit-flipping and timing"

This was stated to me by a coworker at my first job. It was at a formative moment in my life: getting ready to start college, working at a then-startup doing data entry and computer repair, and learning to program in C++ in my spare time. My coworker said this while I was shoulder-surfing his efforts to program an embedded computer to display text on a small serial-driven LCD screen. He was effectively instructing the computer to set particular bits on the display (bit-flipping) at specific times (timing). It's all just bit-flipping and timing...

Four years later I was taking CSSE 380, Organization of Programming Languages, learning Scheme and writing continuation-passing interpreters with garbage collection and static type checking. Which is to say, bending my mind on a nightly basis. (I recall discussing with my roommates - also in the class - starting a band called Dr. Scheme and writing heavy metal songs that always ended in "cond, lambda, define!" But I digress...)

Looking back on it now, that course wasn't really about learning Scheme, nor was it about coding garbage collection or type checking. It was about arriving at the fundamental realization that under the hood of the language compilers and interpreters we use on a daily basis lives an amazing paradox. Each one is a transformation on some language, turning it into yet another language (e.g., assembler) or into a sequence of operations performed immediately within that very transformation, producing a final result. And what is amazing is that these transformations are often built using the very language they transform! One can craft a Scheme interpreter in Scheme, using Scheme lists to represent Scheme code. Likewise (with a bit of parsing), one can write a C compiler in C. It was recognizing the duality of a program represented as code (text) and textual strings that can be manipulated in a programmatic way that opened my eyes to a part of what really goes on inside a computer.

Suddenly, the magic of a programming language, hand-crafted by wizards in underground dwellings, was transmuted into a very real, if not easy, undertaking that even us wee burgeoning Computer Scientists could approach. All of the abstractions that we took for granted when hitting the Compile button boiled down into the "bit-flipping and timing" of compilation and interpretation. I would call this a transformative moment in my Computer Science education, where my understanding of the discipline underwent a fundamental shift. And over time, I have come to recognize other moments in a CS education that bear this same mark.


Last week, I substitute lectured in my advisor's Automata course. I've done this a few times in the past, generally going over the previous week's homework but sometimes presenting new material such as undecidability. That one is always fun, watching individual brains click as the concept becomes apparent to each student. This time, however, I was preparing the class for their final exam, going over a variety of example problems. Much of the material pertained to undecidability and in particular, properties of languages. Languages in Automata refer to collections, or sets, of strings composed from some alphabet of symbols. For instance, if the alphabet is just 0 and 1 (we write this as {0, 1}), then 0, 11, 01010111100011001 are all valid strings. Each language is a subset of all possible strings for that alphabet. So the even-length strings consisting of just 0's is a language. And we can consider properties of languages, such as whether a language contains only even-length strings of 0's (which is broader than the language which contains all even-length strings of 0's).

Herein lies another seeming paradox. To check a property of a language, the language needs to be given to a machine (essentially a program, but let's call it M for machine) as input, with the hopes that M will (eventually) output a "yes" or "no," depending if the language has that property. Yet many languages, such as the one given above, are infinite in size. If an infinite language is fed into M, it will never be able to finish computing its result since it will forever be reading its input, right?

So instead we give M a finite string representing the language. But what is this finite representation that can represent all of an infinite language? None other than a machine, of the same type we wish to feed languages! This second machine (the one representing a language, which we might call N) is written as a finite string, effectively a program itself. N must be able to generate (or equivalently, "accept") all the infinitely-many strings in the language. Although the typical way of writing N is as a binary encoding of a Turing Machine, one can think of N as program code (again, text) being fed into M - another program which can be represented in the same kind of code. In fact, it turns out that all the N's that have this property form a language of their own: the language of strings representing machines that accept languages with that property. Another duality: languages represented by machines become strings in another language!

As it turns out, Computer Science as well as Mathematics abound with such dualities. The proofs of many important theorems leverage the fact that machines, which accept strings as input, can themselves be represented as strings and fed into yet other machines or even themselves. Alan Turing himself used this to demonstrate certain kinds of questions for which an answer cannot be produced - these are among the undecidable problems mentioned above. Kurt Gödel, a mathematician living around the same time, came up with a similar result about logical systems, by framing logical "sentences" as numbers that could themselves be reasoned about using that same logical system.

While this can get complicated in a hurry, the interesting thing to note is the abundance of these "paradoxes" as I like to call them, or dualities, that Computer Scientists use to better understand everything from programming languages to decidability of problems. They also turn out to be, in my opinion, some of the most difficult yet rewarding concepts to learn and to teach. I witnessed this first-hand last week, as students at first struggled to simultaneously understand the duality and the distinction between languages, machines that accept them, languages composed of machine encodings, and properties of language expressed as languages composed of machine encodings. That said, once a person has a clear grasp, it opens their mind to understanding what is going on inside a computer at multiple layers of abstraction simultaneously. In my current research, I have to consider programs that can be an execution in progress inside a computer, a data structure representing that execution at any step, a string of characters representing that data structure, or a packet containing that string. Dualities abound!

I would be interested to hear what other CS students, teachers, and practitioners consider to be their transformative moments. Do they typically center around realizing such dualities? Or, is there something else (or something more fundamental) that defines these moments?