You are currently browsing the monthly archive for November 2011.

I failed to post a blog entry last week, and in order to make up for it, I should post two this week. Here’s the second one.

Lesswrong is a blogging group that is “dedicated to the art of refining human rationality”. There are a lot of posts about Bayesian probability, Cognitive biases, Artificial intelligence etc, and if you’re new to it, I’d recommend starting at one of the sequences. Apart from online discussions, lesswrong community has come to realize the importance of meeting up in person. This is particularly important considering the kind of audience and participants the blog attracts – slightly geeky individuals possessing high IQ who are presumably not the most social people. I can relate.

The Ottawa meetup group started sometime in the summer with an average 6 people attending every week. For various reasons, people have stopped coming. It seems, those who were aware of it when it started were the only ones to join the group – around 10 people. We did not make any efforts to spread the word around. In any case, the average group size is 3 ( Alex, Andrew and me), and occasionally a couple of other people show up. So, here’s a summary of what goes in a typical meetup. This one was a couple of weeks ago.

Summary of Monday’s meeting –

We were supposed to meet at Andrew’s at 7.30, but it got postponed to 8. Alex was 15 minutes late, and when he arrived at 8.30 he brought a pack of “Set” cards. The three of us played one round while doing some bistro combinatorics on the game. As usual, for every game there’s a mathematician who’s studied it. http://www.math.rutgers.edu/~maclagan/papers/set.pdf

We then moved over to the couch. I had printed 3 copies of chapters 2 and 3, and surprise surprise!! only 3 people showed up. Talking about making decisions under uncertainty, I asked Alex to ask me about any outward-looking issue lesswrong deals with ( not the self-help ones ), and I said I’d reduce it to an issue in complexity. He asked something along the lines of “making decisions under uncertainty”, and I quickly interpreted it as “optimal decisions” and hand-wavingly introduced bounded rationality – the process of optimization of ones perceived “decision function” is critically ,possibly non-linearly, affected by ones intelligence. Alex then asked for some examples of problems in P and some in NP. After an embarrassing amount of thought to come up with a simple example, i gave a couple of terrible examples. But since I’m writing stuff down, here are some better ones –

NP Complete – http://en.wikipedia.org/wiki/List_of_NP-complete_problems#Games_and_puzzles

P – I mentioned matrix multiplication.

TODO for next monday – Clarify the meaning of decision problems and then the classes P, and NP. And basically why P=NP is the most important problem in math.

Other usual favourite topics that surfaced included the genetic influence of homosexuality, cryogenics etc. Andrew asked the following question : What if there was a machine into which you stepped, and out came an exact copy of you but your original was destroyed. I obviously pointed out the no-cloning theorem while Alex remarked that perhaps no significant things that make us us have Quantum origins. Then we proceeded into debating about how we compute “I” – this was a long conversation. I pointed out that until very recently in human evolution any definition of “I” had a significant genetic/family/culture factor, where as now. in the context of “uploading our brains”, we’re defining “I” in a purely intellectual manner. Basically arguing about whether it’s ok for genes to ‘go jump in the lake”. This went on for a while, and Alex remarked that my thoughts race ahead of my words to the extent that the conversation seemed like a random walk. On homosexuality, I quickly mentioned that it wasn’t an ESS – homosexuals will not procreate and will die out. Alex mentioned that a recessive gay gene could exist in a person, while his homosexual brother who has two recessive gay genes can help him survive and procreate by providing resources. Andrew pointed that incidence of homosexuality is observed to be higher in the younger siblings. I wasn’t totally convinced that Andrew’s gay-producing theory and Alex’s gay-maintaining theory added up to their prevalence. We also wondered about homosexuality proportions in animals.

That’s about as much as my aching head could remember. We did not cover much of the paper, but we will continue doing it. Next week, I propose we play some card game ( Sets was fun ), sit down and go through some concepts and try to cover chapters 2 and hopefully some part of 3 in reasonable detail. “Fart sessions” as we used to, in undergrad, refer to any undirected, dissipative discussion sessions ( http://archiv.tu-chemnitz.de/pub/2006/0020/data/MAthesis_EvelynRichter.pdf ) will inextricably follow.

In Ottawa lesswrong meetups, we’ve started to discuss Scott Aaronson’s Why Philosophers Should Care About Computational Complexity. We read and discuss three chapters every week, and I figured it’d be nice to summarize the material. The original pdf is by itself isn’t very long at all, and contains summaries – I’d highly recommend you read that instead of this. In any case, I’ve decided to create a summary and add context to make things clearer for me. I’ll keep adding chapters as we cover them.

Chapter 1 – Introduction [ Added background. Pedagogic ]

Analogous to how cars and other mechanical inventions were developed to cater to our laziness, computers are devices onto which we offload our most boring and repetitive thought cycles. Computability theory is the study of the extent to which it is possible to identify and demarcate those boring human thoughts, “algorithms”, and have them work on other devices, “computers”. In the 1930s, people came up with different models of computation, but most surprisingly they all turned out to be equivalent! Any boring thought you might have will run the same on any computer you make. Turing machines became a popular model for analysis, but you’re free to choose your own – ants (Langton’s), game of life (Conway’s ) or lambda calculus (Church’s).

You can see why philosophers got excited – they wanted to know if all human thoughts are boring. In other words, can we come up with a thought that is not boring but well-defined? One of the first questions posed about this was Hilbert’s Entscheidungsproblem. He was a mathematician and he knew that statements about numbers are really boring. But is it possible that there are some statements about numbers that are not boring? Can we come up with such a statement? How? – simple – Figure out a way to ask the same question using numbers! – “Can you come up with a boring thought that’ll classify statements about numbers as true or false?”. Kurt Godel figured out a way to ask that question precisely by mapping it to numbers. Viola! All hell broke loose. The answer was a loud screaming “NO! Not all true statements about numbers can be proven to be true” – Godel’s incompleteness theorem. But wait. What do we mean by true? Can we even define precisely what we mean by true. This time Alfred Tarski yelled “NO! Arithmetical truth cannot be defined in arithmetic.” – Tarski’s undefinability theorem. The hardest blow came when Turing asked a similar question “Can you build a Turing machine that can tell if a given Turing machine halts”, and elegantly explained “No, you cannot” – the Halting problem. This was worse because it wasn’t about numbers anymore, or about the nature of truth – it was about actual real physical devices you can build. All these powerful negative results led to the Foundational Crisis of Mathematics. For decades to come, mathematicians and logicians provided enough fodder for generating non-boring thoughts in the minds of philosophers. They devoured it.

But that was a long time ago. Since the 1970s, when we started building real computers, we became increasingly concerned with the complexity and efficiency of algorithms – how much space and time are required for efficient computations? Computational complexity theory was born. It has now developed into a rich theory but it appears that philosophers are still dining on computability theory. We have a new restaurant at this end of the universe not yet frequented by philosophers. Scott Aaronson is our cook and I’m your waiter.

Chapter 2 – Complexity 101 [ Added background ]

If we know something is computable does it matter if it can be computed in 10^5 seconds (1 day) or 10^100 seconds? Yes. Our universe is less than 10^20 seconds old. Clearly, the problem is in the exponent. So, if you want to solve a problem of some size, n, and the most efficient algorithm to do it takes time 10^n, then you’re screwed. If the size is in the exponent, we’re not efficient. But if it takes something like n^10 or even n^100, we’re happy. If the size occurs in the base, our algorithm is efficient. The next obvious thing we’d like to know is which problems admit efficient algorithms and which don’t. Just like in computability theory where we figured out that many models of computations were equivalent, we’ve now learned that many hard problems are equivalent. They’re called NP(Non-deterministic, Polynomial time) -complete problems. It doesn’t matter which problem you figure out an efficient algorithm for – if you find for one, you’ve found for all. The efficient ones, where size occurs in the base and not in the exponent, are called P (Polynomial time) solvable problems.

I will take a moment here to explain what NP-completeness means, because it is crucial. Imagine you’re asked to solve a problem, for e.g sort a pack of cards. You may be interested to know how many cards you’d have to compare in the process – so you ask “What is the minimum number of comparisons needed?”. This is an optimization problem and the answer is a number. Other problems may have answers in various other forms – list of all cities in the shortest route etc. In order to be able to compare these problems and their algorithms, it’d be nicer to have answers that are comparable, and the simplest such form is a boolean value. So, you instead ask “Is the minimum number of comparisons needed to sort greater than 100”, to which the computer only answers True or False – these are called decision problems. Another feature of any algorithm, you might have noticed, is that it must make choices and depending on the outcome of these choices has to proceed further. Think of it as a binary tree – you start at the root, make your choice and proceed leaf-ward. Leafs contain answers – True or False. When a Deterministic Turing machine (DTM) makes a choice, it has to go down its chosen path, and if it turns out that it was a bad decision, it has to come back and go down the right path. A Non-Deterministic Turing machine (NTM), on the other hand magically always make the right choice. All problems efficiently solvable using a DTM is defined as the set P, and all problems efficiently solvable by the NTM is defined as the set NP. Good. Now to NP-Completeness. Stephen Cook in 1970s discovered that many many problems ( but not all ) in NP were equally hard and were the hardest problems in NP – these are called the NP-complete problems. What exactly is the power of this hypothetical magic in an NTM ? We don’t know – that is the P =? NP question.

After that long digression which has hopefully brought most readers on a common footing, let me return to what Scott Aaronson has to say in this chapter. First, why are we so comfortable in dividing up efficiency ranges into polynomial and exponential, and not something in between like n^logn ? A second objection is that in practice algorithms that take an exponential 1.00001^n time might run faster than n^100000, because in practice inputs are bounded. These questions are tackled in later chapters. A third point noted is that while computability theory concerns itself with logic about what can and cannot be computed, complexity theory deals with what can be done best given some resources, and in this sense it is more closely related to physical sciences. So, one can ask, if we could travel backwards in time, could be compute faster, or is there a limit physics poses on the amount of information a limited space can store.

Chapter 3 – The relevance of polynomial time

3.1 The Entscheidungsproblem Revisited

Church and Turing showed that even if you take an incomplete formal system, you cannot classify all statements into “provable in F”, “disprovable in F”, and “undecidable in F”. Godel in a famous “Lost letter” wrote to von Neumann asking if there would be a way to decide if a given statement has a proof in F of length n bits or less efficiently. i.e if a proof of a reasonable length exists, can it be found in a reasonable amount of time? Godel had anticipated the P vs NP problem.

3.2 Evolvability

Is 4 billions years time enough to construct a human body ( which presumably optimized many of its inner workings w.r.t its environment ) from a much more homogeneous environment that formed the earth? Godel thought not, but modern biology says otherwise. Basically, complexity theory is nowhere near even hinting at us an answer to the possibility of Evolution.

3.3 Known Integers

This is an interesting question – when you say you know something, what do you mean? Let us, for a moment, keep aside knowledge of the kind most people spend their lives trying to acquire – mating habits or courtship rituals of humans – and ask more specific questions, for instance, ones that mathematicians claim they know – proving something. When a mathematician claims he knows how to prove a statement to you in a system, what he’s saying is that he can, in an amount of time polynomial in the size of the statement, reduce it to something you both agree on. To make this more concrete, when you say you “know” a prime number p what you’re saying is that you have an algorithm that proves in polynomial(p) time that p is a prime. The same thing cannot be said for the prime := “next prime larger than p” even though it is well defined. Although this seems like a very interesting way to think about things, Gil Kalai opines “The opinion that once you show that a certain human activity represents an effort in P means that it is “trivialized” is a bit too far since it is quite plausible that all human activities represent efforts in P”.

Today, I’d like to talk about the idea of permanence from an ontological standpoint. The issue i’m concerned with is the ease with which we talk about the existence of something independent of time. I will make observations in common subjects and move on to less general ones.

Richard Dawkins’ book The Selfish Gene theorizes the gene-centric view of evolution where its phenotypes, you and I, are carriers of genetic material on which selection happens. After reading the book, I was left with a feeling of inferiority in the manner of a helpless subordinate. The feeling might have well been due to a strong sense of associating my self with my mind (“I am the most abstract thought I can think”) as opposed to computing my identity by weighting several well regarded societal good-to-haves. In any case, it is true that certain patterns of A, T, C, G have been very successful over 4 billion years over other patterns of nucleotides . It is true that some biological structures like warm blood or vertebrae or neurons have been more successful than other structures. On the other hand, it is also true that some elements are most abundant in the universe than others – hydrogen and helium for obvious reasons, iron for a more interesting reason ( watch BBC Atom ). Hydrogen atoms are almost as old as the universe, younger by about 300,000 years. Atoms, neucleotides, genes, proteins, organs, individual organisms, species and many distinct layers in between all have existed for different time periods with each comparable layer exhibiting a non-uniform pattern in its space of all possible patterns. All right. With these observations in mind, let us ask some questions :

Q. What is the purpose of life?

A. 101010 due to some random effects in Douglas Adams’ neural connects.

Q. No, seriously. If I think of myself as a computer, as I most often do, what function f(x) do I optimize?

A. When I read Dawkins, one answer immediately seemed to be a perfect match – “Procreate as much as possible to optimize the survival of all your children”, or “Don’t disappoint the genes that formed you”. This explanation of what we’ve unconsciously been doing all along applied very well to the people around me. People and non-human animals spend a majority of time directly or indirectly in search of a mate, or finding resources for the upbringing of a young one. For them, f(x) is necessarily in terms of their gene patterns; “phenotypic” residues ( for ex. intellectual contributions ) have very short life spans. I suspect their strategy of having as many kids as possible is a way to produce future computational instances that can continue crunching on their f(x), just as they had been of their ancestors’. All of this is fine, but I think there was a *very very crucial *event in the 1800s, that changed the whole game. In *On the origin of species*, Darwin clearly explained this in great detail. We now know roughly the characteristics of f(x) that was being optimized, and in my opinion this knowledge has significantly altered that f(x). It is the *measurement problem. *World human population is expected to decline. Populations in developed countries, presumably with “wiser’ people, are already on the decline. Genes that evolved to code for a human phenotype are probably not going to live the longest. Why then should I consider the spreading of my genes as my primary purpose?

Q. So, what has this f(x) become?

A. It can be whatever you want it to be. I realize that doesn’t mean much as it quickly reduces to the problem of free will vs determinism, which is really non-problem. What I mean by that, is f(x) doesn’t have to be continuous. Every once in a while a “level-crossing” feedback loop is completed – f(x) becomes complicated enough to model the previous version of f(x). At that point what appears to be a linear growth of complexity encounters a spike. A black swan. In practical terms, what I’m trying to say is that we as humans seem to be beginning to learn that “permanence” or “longevity” of *something* is a worthy candidate for optimizing. Genetic configuration is not primary anymore. Welcome, gays, lesbians and smart people who don’t want to have kids. Your bodies ( including minds ) have figured out a way to experience the pleasure of sex, possibly created and selected as a major driving force of survival, without procreation. Find your new thing that has a larger value of permanence – contribute to the scientific body! That is the higher being!

I wanted to talk a lot more about permanence in Mathematics. About universal quantifier “for all”, about Continuum hypothesis, about Mathematical platonism etc. I wanted to mention our quest for permanence in Physics – of virtual particles and an obsession with finding theory of everything, Maybe if time permits some other time. Good Night folks!