## Archive for September, 2012

### Gell-Mann on learning

September 27, 2012

Murray Gell-Mann on why being in awe inhibits learning:

I said I’d rather be poor or die than be an engineer because I would be no good at it. If I designed something it would fall down. When I was admitted to Yale, I took an aptitude test, and when the counselor gave me the results of the exam, he said: “You could be lots of different things. But don’t be an engineer.”

After my father gave up on engineering, he said, ‘How about we compromise and go with physics? General relativity, quantum mechanics, you will love it.’ I thought I would give my father’s advice a try. I don’t know why. I never took his advice on anything else. He told me how beautiful physics would be if I stuck with it, and that notion of beauty impressed me. My father studied those things. He was a great admirer of Einstein. He would lock himself in his room and study general relativity. He never really understood it. My opinion is that you have to despise something like that to get good at it.

If you admire it sufficiently, you’ll be in awe of it, so you’ll never learn it. My father thought it must be very hard, and it will take years to understand it, and only a few people understand it, and so on. But I had a wonderful teacher at Yale, Henry Margenau, who took the opposite attitude. He thought relativity was for everybody. Just learn the math. He’d say, “We’ll prepare the math on Tuesday and Thursday, and we’ll cover general relativity on Saturday and next Tuesday.” And he was right. It isn’t that bad.

__________

Source:

Susan Kruglinski, The Man Who Found Quarks and Made Sense of the Universe, DISCOVER Magazine, April 2009.

### My implementation of (!!)

September 20, 2012

In Haskell we can easily create a list and then access its elements using the (!!) function, which is defined in the Prelude. Here is a very brief GHCi session:

Prelude> let xs = [7,8,9]
Prelude> xs !! 0
7
Prelude> xs !! 1
8
Prelude> xs !! 2
9

So far, so good. What if the index is negative or equals / exceeds the list’s length? Let’s see what happens in those cases:

Prelude> xs !! (-1)
*** Exception: Prelude.(!!): negative index

Prelude> xs !! 3
*** Exception: Prelude.(!!): index too large

As expected, we get error messages. What if we used the Maybe data type to avoid exceptions? This is exercise 4 in chapter 3 of O’Donnell & Hall & Page [1], which is phrased as follows:

Write (!!), a function that takes a natural number $n$ and a list and selects the $n$th element of the list. List elements are indexed from $0$, not $1$, and since the type of the incoming number does not prevent it from being out of range, the result should be a Maybe type.

The aforementioned authors propose the following implementation:

import Prelude hiding ((!!))

(!!) :: Int -> [a] -> Maybe a
(!!) n [] = Nothing
(!!) 0 (x:xs) = Just x
(!!) n (x:xs) = (!!) (n-1) xs

where I added the import line to hide the standard (!!) function that is defined in the Prelude. My first thought was that the authors switched the function arguments, which makes the function look silly. Let’s give it a try. Here’s another GHCi session:

*Main> let xs = [7,8,9]
*Main> 0 !! xs
Just 7
*Main> 1 !! xs
Just 8
*Main> 2 !! xs
Just 9
*Main> (-1) !! xs
Nothing
*Main> 3 !! xs
Nothing

It appears to be working, but specifying the index before the list looks rather ugly. Wait, what if the index is negative? For example, why does (-3) !! xs return Nothing? Let’s use equational reasoning to find out:

(-3) !! [7,8,9] = (-4) !! [8,9] =
= (-5) !! [9] =
= (-6) !! [] =
= Nothing

This reveals a fatal flaw in the authors’ implementation: if the list is infinite, then the recursion will never terminate. For example, (-1) !! [0..] will never terminate, because when the initial index is negative, decrementing the index will never get us to the zero index.

Therefore, I propose the following implementation:

import Prelude hiding ((!!))

(!!) :: [a] -> Integer -> Maybe a
(!!)     [] n = Nothing
(!!) (x:xs) n | n > 0  = (!!) xs (n-1)
| n == 0 = Just x
| n < 0  = Nothing

where the first argument is now a list, and the second argument an integer. Note that I used indices of type Integer (“mathematical integers”), instead of type Int (“computer integers”). Let’s see if this implementation works:

*Main> let xs = [7,8,9]
*Main> xs !! 0
Just 7
*Main> xs !! 1
Just 8
*Main> xs !! 2
Just 9
*Main> xs !! (-1)
Nothing
*Main> xs !! 3
Nothing

It appears to be working. No errors. No exceptions. If you, dear reader, happen to be acquainted with Haskell you will almost certainly be shocked (!!!), for this function is trivial! Well, that is true, but I allow myself to be intrigued by trivialities. Moreover, this function is simple enough to allow us to use equational reasoning. For example, let’s compute xs !! 2 using equational reasoning:

[7,8,9] !! 2 = [8,9] !! 1 = [9] !! 0 = Just 9

What if the index is too large? Let’s compute xs !! 4 then:

[7,8,9] !! 4 = [8,9] !! 3 = [9] !! 2 = [] !! 1 = Nothing

Step by step, by successively removing the head of the list, we get where we want to. Unfortunately, this suggests that accessing an arbitrary element of the list will not be $\mathcal{O} (1)$.

__________

References

[1] John O’Donnell, Cordelia Hall, Rex Page, Discrete Mathematics using a Computer (2nd edition), Springer, 2006.

### Combinatorial Explosion

September 16, 2012

An amusing Japanese cartoon on combinatorial explosion:

Tastefully done, I would say. The target audience consists not of this blog’s readers, but rather of their children.

Hat tip: Michael Lugo

### A measure-theoretic definition of synergy?

September 14, 2012

Alice and Bob are fruit-pickers at an orange orchard.

Alice can pick 6 baskets of oranges in one hour. In contrast, Bob can pick 7 baskets of oranges in the same period of time. However, if Alice and Bob work together, then they can pick a total of 15 baskets in one hour. As part of a team:

• Alice is now picking 7.5 baskets per hour, a most impressive increase in productivity of 25%.
• Bob is now picking 7.5 baskets per hour as well, a modest increase in productivity of approximately 7%.

Both Alice and Bob benefit if they work together (though Alice benefits more). We thus have an example of synergy. To use a cliché: “the whole is greater than the sum of its parts”. If Alice and Bob work alone, they can only pick 13 baskets per hour in total, but if they work together they can pick 15 baskets per hour. Everyone is happy.

Let $S := \{\text{Alice}, \text{Bob}\}$, let $2^S$ denote the power set of $S$, and let $\mathbb{R}_0^{+}$ denote the set of nonnegative real numbers. We introduce a productivity function $\pi : 2^S \to \mathbb{R}_0^{+}$, enumeratively defined as follows

• $\pi (\emptyset) = 0$
• $\pi (\{\text{Alice}\}) = 6$
• $\pi (\{\text{Bob}\}) = 7$
• $\pi (\{\text{Alice}, \text{Bob}\}) = 15$

where $\pi (\emptyset) = 0$ because the productivity of the “empty team” is zero. Since we have that

$\pi (\{\text{Alice}, \text{Bob}\}) > \pi (\{\text{Alice}\}) + \pi (\{\text{Bob}\})$

we conclude that we have synergy. Note that the existence of a synergistic or synergetic effect is a property of the productivity function $\pi$. We could attempt to study such property in a more general setting.

__________

We now introduce a definition

Definition: Given a finite set $S := \{s_1, s_2, \dots, s_n\}$ and a function $\mu : 2^S \to \mathbb{R}_0^{+}$, if the following conditions are satisfied

• $\mu (\emptyset) = 0$
• $\mu (X \cup Y) \geq \mu (X) + \mu (Y)$ for all sets $X, Y \in 2^S$ such that $X \cap Y = \emptyset$

we say that $\mu$ is a superadditive measure [1].

Using the superadditivity property recursively, one can conclude that

$\mu (X) \geq \displaystyle\sum_{x \in X} \mu (\{x\})$

for every $X \in 2^S$. For example, if $S := \{s_1, s_2, s_3, s_4\}$, then we have that the measure of $X :=\{s_1, s_2, s_3\}$ is

$\begin{array}{rl} \mu (\{s_1, s_2, s_3\}) &= \mu (\{s_1, s_2\} \cup \{s_3\})\\\\ &\geq \mu (\{s_1, s_2\}) + \mu (\{s_3\})\\\\ &\geq \left( \mu (\{s_1\}) + \mu (\{s_2\}) \right) + \mu (\{s_3\}\\\\ &\geq \mu (\{s_1\}) + \mu (\{s_2\}) + \mu (\{s_3\})\end{array}$

Frankly, I have (accidentally) opened a can of worms. I started writing this post thinking about synergy and productivity, and I am now drowning in Measure Theory! As it turns out, the union of all my knowledge of Measure Theory is a set of measure zero ;-) Hence, I will abruptly finish this post with a passage from Wang & Klir [1]:

Observe that superadditive measures are capable of expressing a cooperative action or synergy between sets in terms of the measured property, while subadditive measures are capable of expressing inhibitory effects or incompatibility between sets in terms of the measured property. Additive measures, on the other hands, are not able to express either of these interactive effects. They are applicable only to situations in which there is no interaction between sets as far as the measured property is concerned.

I may return to this topic if I happen to have any interesting ideas.

__________

References

[1] Zhenyuan Wang, George J. Klir, Generalized Measure Theory, Springer, 2009.