Remembering (or forgetting) math (October 2, 2016)

As much as conventional wisdom says, “If you don’t use it, you lose it”, I still find myself remembering most of the core mathematical ideas surrounding my field of work. Basics of computational complexity theory, logics, some parts of discrete mathematics that Donald Knuth calls “concrete mathematics,” as well as some of the graph theory, I can recall and reason on without much trouble. Now, more than ten years after me graduating from my alma mater, Moscow Aviation Institute, these topics probably got mostly connected together in my mind, each reinforcing the understanding of another.

But despite that, I sometimes notice glaring — and embarrassing — omissions from this interconnected picture. Some parts of mathematical theory won’t stick, and keep evading me even after I refresh them as needed. My brain seems to try to avoid walking around some dangerous areas.

Sometimes it is a question that I feel almost scared of asking because the answer seems to lie outside of what I know. And it keeps hanging in the background of my mind, but never prevents me from using the parts of the theory I do know. Sometimes it’s pieces that haven’t got connected to the big picture, and are important enough in isolation, but they never commit to my memory being well-connected to other parts.

To put an end to this embarrassment, here’s an incomplete list of my glaring omissions, with the answers to them (that I spent some time finding).

Q: If Gödel’s Second Incompleteness Theorem put an end to an attempt to formalize mathematics, how come mathematicians still feel it’s OK to continue doing what they’re doing using Zermelo-Fraenkel set theory, that, in turn, is also susceptible to Incompleteness Theorem?

A: The set of axioms for a system as powerful as Peano Arithmetic indeed can’t prove its own consistency, but a wider set of axioms may be able to do it. So axioms in Zermelo-Fraenkel exist to prove consistency not of itself, but — you guessed it — of less powerful Peano Arithmetic. In order to prove consistency of Zermelo-Fraenkel you need a larger system, which will again be inconsistent with regards to itself.

Q: What’s the difference between propositional logic, first-order logic and logic of higher orders?

A: I won’t even put an answer here, so simple it is. Back in my university days I needed to deal with description logics a lot and still didn’t manage to remember the computation complexity of the problem of reasoning over different logic classes.

Q: Nothing in the known complexity theory prevents us from building something that’s more computationally capable than Turing Machine, isn’t it? We just use Turing Machine as a convenient model, right?

A: Not so. Or, strictly speaking, it’s not known yet whether something more powerful does exist, but most bets are on the side of not existing. Note that quantum computers are known not to be more powerful than the Turing Machine. This one is particularly embarrassing, as Church–Turing thesis that presumes (but not proves) that every computable function — anything that computes — can only be computable on a Turing Machine is studied in the first year of Computer Science course! It just never stuck me until very recently that the thesis indeed talks about every computable function. Like, every.

Do you ever feel anything similar about something you know?

On being an adult (September 24, 2016)

I’ve recently turned 35, which is normally well beyond the age where one can safely assume one is an adult. I remember myself very clearly in my twenties — maybe even a bit too clearly — and I’m totally sure I wasn’t yet an adult when I was 23, for instance. Somewhere late in the last decade, a change has happened.

What changed? What part of me is now different from the 23-year-old me? The answer actually lies on the surface: interacting with the world of other adults has gotten much easier than before. The world of adults holds very tightly onto one notion that has now taken a common hold over all the different ways I think and do things. That notion is that everyone in the world is very different.

This may sound simple at first, but here’s what I mean by that. Accepting that everyone is different means you accept that you can never be sure or fully aware about other people’s motives, desires, intentions, feelings or thoughts. Even when someone’s behaviour seems familiar — this happens, for example, with someone you closely know — there can always be something very unpredictable they can do once and this still won’t come into conflict with the image of the person that you had in mind. You wouldn’t imagine or even think about someone doing what they did, but this still fits well with the rest of your image of them. The world is just so very flexible that it allows that too.

This manifests itself the most in the fields that are normally considered “very adult”. Take law: nothing can be taken as obvious and unshakable by a judge in court. They know too well that the factual evidence nobody could’ve predicted may easily beat some “obvious” assumptions. And in politics, no issue comes without a second side; everything is open to a new interpretation that has a chance of remaining valid even in the crowd of the old ones.

The flexibility of meanings and the ability to control it is clearly something that separates an adult from a child, or a teenager. Both teenagers and adults use the same words, but teens apparently tend to think that words have fixed and obvious meanings — that they know for sure how things are because “obviously” it can’t be any other way. Adults, on the other hand, can bend and control the meaning of the words they say. For them, it gets easy because there’s one thing you can be sure of: if you attach certain meaning to a word and release it into the world, you will be amazed with what new meanings it will get back to you.

I don’t remember exactly when this understanding has come to me — I think this was a slow process around the age of 27 — but that clearly was the end of my non-adult life.

Steve Reich, Jan van Eyck and human perception (June 17, 2015)

It’s currently my holidays, and I have no plans to blog about anything serious during this time. So I’ll write about music and arts instead.

I recently went to a concert to hear Steve Reich’s one long piece, called Drumming, performed by a New York musical collective So Percussion. Reich’s work wasn’t previously unfamiliar for me, but I’ve never heard it live before and only had some surface knowledge about him being a minimalist-academic and an important figure in NYC musical avantgarde of the sixties. For me “minimalism” in this context meant that his work is about getting rid of decorative elements in music — such as melody — in an attempt to get to the music’s essential bare bones. Whereas “academism” was about keeping the musical semantics aligned with the academic tradition, i.e. that even this stripped bare music has certain expressive qualities that cannot be substituted with something else, like silence, for example.

Drumming essentially consists of short repeating percussion patterns, gradually shifting relative to each other and slowly mutating by either adding a beat (substituting the rest with the beat) or removing a beat. And that’s all.

When performed though, Drumming exhibits much more complicated effect on listener that it may seem from this description. First of all, although the tempo of the piece is not changing — and this is meant in the strictest sense, as the entire structure of composition depends on the rigid rhythm, — two repeating patterns with a small phase difference between them effectively sound slower compared to the same patterns later, when their phase shift reaches about half of the phase. This makes the music sound slow and then gradually get certain “merry galloping” quality, very unexpected from a simple piece like this.

Second interesting effect was the “roar” that echoing percussion establish in the large concert hall — this one is completely absent in the recordings I previously heard. It sounds like a constant standing sound wave formed by precussion sounds being reflected by the auditoriums walls. It sometimes “swallows” simple vocalizations in Drumming or tricks your listening into thinking you actually hear some sounds when there’s nothing to produce them.

Have a look for yourself (the video below only shows a part of a first movement, the entire piece lasts more than an hour):

Both described aspects of Drumming are interesting to me because they deal with our perception of music. Reich knew that the listener’s brain tends to group close beats together into one, and although musicians are instructed to play as strictly to the rhythm as they can, your listening perception just can’t help itself and assigns subjective qualities to shifting patterns, like “jumpy” or “restrained”. Note that musicians in other styles are fully aware of this effect. In funk and soul, slight off-tempo beats are used to give the music special groove, that pulls the listener ahead. Reich’s rhythms are restricted a very formal scheme, that looks cold and austere and certainly has no groove, but it also opens an extra dimension of the piece’s richness when off-tempo beats appear and disappear.

If this all sounds like a useless theoretical exercise to you, here’s another example of using mechanisms of perception from a different field.

This is Jan van Eyck’s Arnolfini Portrait, dating from 15th century. This masterpiece warrants a much longer description of its qualities, but I’ll focus on very few of them here. Van Eyck’s goal with this and other paintings was to reach the ultimate levels of authenticity, i.e. he wanted to make his paintings looks exactly like the reality they depict. Now, we, humans, can only get an image of reality through our sensory devices, like eyes (or ears). Does Arnolfini Portrait, being as detailed as it is, triggers exactly the same reaction in our eyes as the scene where it was painted?

To a modern viewer it’s obvious that it doesn’t. Despite putting immense number of details into the painting and strictly adhering to the rules of perspective (only have a look at the spherical mirror!), Van Eyck lacked some understanding of visual perception that was only established much later, with the invention of photography and understanding, among other things, what “depth of focus” is. Have a look at a much later painting by Gerhard Richter, called Betty.

This is not a photo, it’s a painting, which certainly looks more “real”. Note that the human eye doesn’t have a depth of focus the way photographic camera does, and the “blurring” in our perception of reality is not due to some optical effect, it’s a property of our visual cortex.

So what are the similarities between Reich and Richter in their respective fields? In the case of Gerhard Richter, he advanced our understanding of painting to a new level by reading into the visual properties of the photographs. Steve Reich advanced our understanding of music by restricting his practice of composing to some formal rules. In both cases, it took a genius to see beyond the medium and into perception mechanisms for it.

Open-plan offices, creativity and programming (June 8, 2015)

This is a very important text for me. If my reasoning is even remotely correct, this is going to have a very significant influence on how I — and probably many other people — think about their career in programming in the future.

Let’s look at some headlines:

• Google got it wrong: the open-office trend is destroying the workplace (Washington Post)
• Open-plan offices makes employees less productive, less happy and more likely to get sick (Quartz)
• The open-office trap (The New Yorker)
• You’re not alone: most people hate open offices (Fast Company)

Plus thousands of blog posts and comments in online communities. There seem to be a consensus: overwhelming majority of people dislike open-plan offices, but are left with no choice. I’m among those who put “good office” close to the very top of my list of priorities when looking for a new job and yet, of my fourteen years in the industry I spent ten in open-plan offices due to the complete absence of alternatives.

Why is it so? Mutiple studies (check any of the links above) confirm that employees in the open-plan offices are more stressed, less productive, take more sick leave and, above all, less creative. The entire idea of being intellectually creative at work is very comforting for us, programmers. Simply being creative is one thing; being creative and being paid for it is completely different. A very famous movie about hackers, “Triumph of the Nerds”, captures this vibe right in its title: this triumph is over the the business people, the dumb MBAs, the managers who demand weekly TPS reports, it’s the victory of the smart underdog.

So surely, with all that creativity hindered by the noise and distractions of the open-plan, there should be a niche for a company that puts smart hackers in comfortable working condition and reaps rewards coming from their increased productivity, right?

Except that it’s not so. One of the studies I found, estimates the average office area occupied by a knowledge worker in an American office with private rooms to be 37.16 m², which is almost three times more than in the open-plan office: 13.94 m². Think about it: the same office building with the same rent can sit almost three times as many people. No CFO would sign-off a private office policy after seeing this difference.

What about creativity and productivity? In most companies programmers require much less of it than they think. The software industry is incredibly commoditized nowadays and the business people are well aware of it. Nobody expects programmers to be creative; merely not being too bad is good enough. Note I’m not saying that those “business people” are evil or incompetent. You can replace “business people” with “free market” with the same result: nobody expects creativity from a person working on a web marketplace for vacation rentals, a taxi ordering app, or supply chain management system. With my anecdotal experience, I estimate the proportion of programmers involved in non-commoditized software development — the tiny innovative core of our industry — to be around 0.1%. This is not as low as it seems. If this estimation is correct, Apple has 50-60 developers engaged in truly creative software and hardware development, Google has 35-40, Facebook around 10. Them, plus other members of their immediate teams (say, ten times as many; those who do gruntwork only partly and have some potential in them) are responsible for most of the technology we see and use today. I am sure they can have any office they like.

The rest of us are not as creative as we like to think and our bosses know it:

A few years ago, I was working at a company where they had just purchased an old shoe making factory and were renovating it into office space so they could have room to grow. In each spot where a person had sat for 8-12 hours hunched over in front of a sewing machine, I was told to install a workstation and run network and electric cable down from the ceiling where the sewing machines had been hooked up.

At the end the project, a co-worker of mine that had the foresight to take a picture of the old setup took one of our finished work and compared the results. The room looked a lot cleaner, and didn’t have the smell of oil and leather anymore, but in the photo, it looked like a factory that you’d see in the early part of the 20th century by its layout. The lone difference being instead of looking like it would make shoes, it looked like it’d make code. They both looked like you’d have the same amount of privacy (aka none), and unless you bought headphones, the same amount of silence for concentrating on your task(s). […]

I see a cleaner, digital sweatshop, a modern version of an age that many thought we had left decades ago. It hasn’t really left, it’s just had the cleaning crew in and been given a few runs through the marketing machine to make what was once undesirable “sauve and sexy!”.

— from Reddit

On reading scientific articles (June 1, 2015)

I have created a shared folder with Computer Science articles I read, understood and liked. At the moment, there are two items in there, but will be more over time. It’s not a surprise that both of them deal with the question of engineering a system as large as a programming language infrastructure and runtime and staying sane — this is a question that occupies lots of my thinking lately (I don’t know the answer yet, but promise not to withhold my findings). Here they are:

• P. Li, A. Tolmach, S. Marlow, and S. P. Jones, “Lightweight Concurrency Primitives for GHC”, in Proceedings of the ACM SIGPLAN workshop on Haskell, 2007;
• K. Wang, Y. Lin, S. M. Blackburn, M. Norrish, and A. L. Hosking, “Draining the Swamp: Micro Virtual Machines as Solid Foundation for Language Development”, in 1st Summit on Advances in Programming Languages (SNAPL 2015), 2015.

This does not mean, of course, that I only read two articles in my life. It’s just that these two I understand much better than the others and I see how they can immediately be useful in my programming practice. Understanding is a key point here: I remember that during my PhD time my approach to scientific articles was utterly wrong. Here are few rules I learned over time:

• Reading and understanding abstract is a prerequisite to even attempting to read an article. There’s a video of one of the Don Knuth’s lectures where he famously answers a question on performance of some tree-based algorithm from the audience and says something in the vein: “I remember seeing an article describing recent advances about this algorithm, but authors didn’t describe performance limits in the abstract, so not sure.” Abstract absolutely must contain each and every key important moment of the entire article.
• One consequence of the above is that there must be articles out there describing important things, but not doing well in their abstract and being completely overlooked because of that. My attitude towards that is sad acceptance: it is simply not possible to assume the best about every article and spend time reading it anyways when article’s abstract is not clear or not exhaustive.
• At the university I read articles trying to get an answer to what-questions: “what kind of new things people work on?” The better question, the way it seems to me now, is how-question: “how do people do those things they do?” The crucial difference between the two is that the second one implies at least a brief familiarity with the field for which the article is written. What-questions, I now think, are better answered on other media, like textbooks.

← Later entries | Earlier entries →