Looking Out To Sea

Let this be a salutary lesson on the dangers of impulse buying. If you don’t spend a few minutes reading reviews on Amazon you might accidentally buy Amir Aczel’s The Artist and the Mathematician, the “story of Nicolas Bourbaki, the genius mathematician who never existed”. And that would be a mistake.

Nicolas Bourbaki was the pseudonym of a group of French mathematicians who attempted to formalise mathematical thinking in the early to mid-twentieth century. In the author’s opinion Bourbaki’s publications had important influences on the structuralist movement that would spread from linguistics and anthropology to many disparate areas of science.

Well, I wouldn’t know about that; and I still feel like I don’t know about it. The book is filled with tedious and trivial details where it should provide only impressions — and sketchy and vague where it should be exact and clear. In fact it exemplifies everything the Bourbaki group were pushing against. Aczel takes whole chapters to explain the minute detail surrounding the early life of one mathematician (including the life of his parents when they were young…) though this has no real relevance to the work he did. In fact, now I think on it I can’t even remember which mathematician gets all the boring backstory.

Whatever: the point is that the writer doesn’t bother telling you why any of this matters. He name-drops mathematical ideas without context or explanation. They have no more relevance to the reader than the endless litanies of people and parents’ occupations and meetings and so on. Amir Aczel insists that Bourbaki was incredibly influential in whatever it was they did, without bothering to reveal whatever it was they did. And that many other fields borrowed these ideas to do whatever it was that they did, again without explanation or detail. And then eventually we find that Bourbaki became less relevant — though again, without explanation.

It’s quite satisfying to say that an author who talks about abstract algebras and category theory is “over-generalising”. If only the book were as satisfying. Instead, I can heartily recommend Mario Livio’s The Equation That Couldn’t Be Solved — a proper tribute to genius mathematics.

Today’s crazy thought was inspired by Scott Aaronson’s lecture notes/discussion on The Emperor’s New Mind. He notes that, for human thought to be computable then it must be equivalent to a Turing machine. So, the author of The Emperor’s New Mind, Roger Penrose, must be equivalent to a particular machine M.

Does M output the following sentence?

“Roger Penrose will never output this sentence.”

Well, we don’t know what that means — for a person to “output a sentence”. For a classically defined Turing machine we know what it means, but not for humans. I’m sure Roger Penrose could say the above sentence but that’s not what the statement means. I certainly don’t know, though I can talk nonsense as much as anyone.

It did bring to mind a discussion with Nick in a previous comment thread, about believing one’s own opinions. From the accusation that “you always believe your own opinions are right” it seems reasonable there must be people who believe their own opinions are wrong. Why would one hold opinions that you acknowledge to be wrong? Is it even possible?

I suggest that one of the limitations of the Turing machine M, which we call Roger Penrose, is that it cannot believe things it doesn’t believe. Obviously! The fact that I thought it worth writing a blog post about is probably what makes this crazy.

There was a man on the bus this evening who was furiously scribbling little mathematical notations on a grubby piece of paper. I was so curious to find out what he was doing! He was really going for it — several lines of closely-written squiggles. The only things I could make out properly were the long division lines separating numerator from denominator, and some Σs.

Was it maths? Physics? Engineering? I want to know! :-) It makes such a change from people reading Jackie Collins or talking loudly on their phones.

I got a phone call this afternoon from my aunt and uncle asking if my parents were okay in China. They are fine, though there might be difficulty getting out of the country now? I’m not sure, maybe there is not much disruption. It’s a very large place, after all.

This is written with the inspiration of Simon Peyton Jones’ talk about pudding combinators. (He may also have mentioned financial contracts.)

Imagine we have a board game, with two opposing sides. To make things easy, this board game only has one type of piece on each side — there are no rooks and bishops and cuddies.

A Strategy is a mapping from the circumstances you find your players in to a move you can make.

type Strategy = Situation -> Direction
type Situation = (Location, [Location], [Location])

The situation for any one piece is its location, the location of the pieces on its side and the location of pieces on the opposing side.

The base Strategy is to not move at all. This is no way to win, so we need to improvise a few strategies. We could move all of our pieces towards the enemy in a mindless deathmarch:

attractfoes :: Strategy
attractfoes (me, _, foes) = attraction me foes

We can do the same for friends (so that pieces can clump together) and with repulsion (so pieces avoid their team-mates, for example).

repelfriends :: Strategy
repelfriends (me, friends, _) = repulsion me friends

Brief diversion: Attraction and Repulsion

So far I’ve assumed the existence of a few things. Some of them you can guess at (eg, Location is just a tuple of x and y co-ordinates). The functions attraction and repulsion need some more explanation. From the given type signatures we can infer that their type is:

attraction, repulsion :: Location -> [Location] -> Direction

The first argument is the piece under study and the second argument is all the pieces it is attracted to/repelled from. Between each pair of locations (pieces) there is a force — either toward or away:

attract, repel :: Location -> Location -> Direction

It seems to me that these should be the “primitives” of this system. (In a sense they are, but not in any formal way. That’s just what these strategies ultimately rely on.) Maybe working up from these functions would reveal a nicer system. (I say “these functions” but really there is only one: each is the negation of the other, so either could be implemented in terms of the other.)

Now where was I? Combining strategies

Assuming we have four simple strategies (attracted to and repelled from both friends and foes) we probably want to combine them. The simplest means is by addition:

(<+>) :: Strategy -> Strategy -> Strategy
s1 <+> s2 = \x -> s1 x + s2 x

Let’s say that s1 is attracted towards enemy pieces but s2 is repelled from them. (This is a silly example, but instructive.) The combinator shown above allows these two urges to neutralise each other — since as I’ve already mentioned, attraction and repulsion are negations of each other anyway.

Of course we may decide that some urges are more important than others. The urge to clump with friends is more important than the urge to avoid the enemy. So we want a scaling system, to increase or reduce the importance of a particular strategy compared to others.

(<*>) :: Double -> Strategy -> Strategy
n <*> s = scale n . s

(The scale function scales a Direction tuple by its first argument.) We can then increase or decrease the importance of a strategy by scaling it:

(0.7 <*> attractfriends) <+> attractfoes :: Strategy

So far we’ve assumed that one strategy is applicable in all cases. This is never the case — there are always corner cases and special situations which we should test for and evaluate accordingly. Let’s say we want our pieces to clump together until the crowd reaches a certain critical point. Then they march out to war or something.

I imagine we would run such a system a bit like the ?: operator from C.

condition <?> consequent <:> alternate :: Strategy

Let’s break it down. The part after <?> is a choice of two strategies, only one of which is applied. The choice is as simple as a tuple of (Strategy, Strategy) — so <:> is essentially an alias for the tuple constructor.

(<:>) :: Strategy -> Strategy -> (Strategy, Strategy)
(<:>) = (,)

The condition is slightly more intricate. What kinds of things would the predicate test? I guess anything that can be determined by looking at the circumstances of this player.

(<?>) :: (Situation -> Bool) -> (Strategy, Strategy) -> Strategy
predicate <?> choices = \x -> if predicate x
                                    then fst choices
                                    else snd choices

The conditional combinator is brand new for this post — I haven’t implemented it in the code yet. So I don’t know how horribly wrong it is! More on that later.

And because my post yesterday was mostly about baking but slightly about Haskell, I suppose I should balance things up by noting that yesterday’s loaf tasted even better this morning. Slightly moister and very tasty. But I’m going outside into the sunshine now!

This is a round-up of things that don’t deserve their own blog posts.

• My birthday seems to fall right in the middle of Homeopathy Awareness Week. The ignominy.

• Last week Rowan Williams appeared to have contracted Hovind’s disease, a condition common in the United State of America, with symptoms such as absurd mischaracterisation of biological theories. The speech took place on 17 March as the first of three lectures, Faith and Science, Faith and Politics and Faith and History. The official transcripts of these lectures have not appeared online yet. I still don’t know whether he’s merely a nutty man with bushy eyebrows or something even weirder.

• I’m re-reading Neuromancer for the Nth time and I’ve only just noticed that the Finn wears a tweed jacket. I don’t know how, but I always pictured him in a dishevelled wax jacket. Also, despite the nay-sayers, it’s still an awesome book.

• I’ve decided not to wait to get myself an Eee PC. The beefier one probably won’t appear until the end of the year and I can always upgrade if it seems worthwhile. Now I just need to find someone who has them in stock…

• If you’ve got some time to spare, and especially if you hated learning mathematics at school, you should read Lockhart’s Lament (PDF). It’s captivating, entertaining and educational — even funny! — not to mention an extremely accurate picture of what school maths was like. (Incidentally, if you search for lockhart's lament there is a lot of discussion, and in nearly all of them someone has pasted the same mini-critique about it being in a “historical vacuum”. It starts “As I see it, Paul Lockhart’s essay would be much more powerful if…”.)

• Our internet connection still seems well screwed up so I can’t access Delicious from home. So if anyone checks my saved links you’ll not find anything new. Sorry about that.

• Alien loves Predator has been updated for the first time in what feels like forever. Now when is Everybody Loves Eric Raymond going to take the hint and follow suit?

That’s all folks.

You will need:

• A deck of cards (it doesn’t matter if a few are missing).
• A table.
• Two hands.

Take the deck and remove the jokers. Shuffle the remaining cards and spread out a number of them on the table in a neat line face down. Start off small — say, 6 cards — and then when you get the hang of it you can use more cards. Put the remainder of the deck to one side; we won’t be needing them again.

In front of you there should be six cards. They are probably not in order because you shuffled them earlier. But if you didn’t shuffle them very well, maybe they are ordered. Your job is to put them into order, but with a number of constraints:

• No memorising values. If you want to know what the face value of a card is, you pick it up and look at it.
• You cannot turn over more than two cards at a time. To make sure of this, hold onto your card as you look at it, then place it back face down.
• You can rearrange cards by swapping pairs or by creating a new line and moving cards into the correct place in the new line.

The ultimate constraint, of course, is your time. Can you do it efficiently, with the minimum of checking and swapping?

(Bonus question 1: Having decided on an efficient way to do it, does it work well on pre-sorted decks? What if the deck is sorted in the opposite direction from your intended arrangement?)

(Bonus question 2: If the original deck was sorted into colours, can you arrange them so that the colours are still in the same order? Eg, if they were originally Red8 Red3 Black3 Black8 (reds before blacks), can you turn it into Red3 Black3 Red8 Black8.)

Some random thoughts on intelligence, language and related matters.

Creating intelligent agents must be done organically

Human babies don’t learn about the world through databases, but through the input of their own senses. So to create a human-equivalent agent it makes sense to give it the equivalent set of sensors and effectors as a human being.

This also suggests that any agent modelled on something else — a spider, a cat, a condor — would be as alien in thought from us as the animal it is designed after.

If you can’t understand how your cat thinks, how can you expect to find something in common with a being whose only knowledge of the world is through a text terminal or a single fixed camera?

Human languages are too opaque for serious use

“Normal” — accepted (behaviour) or average (production) or perpendicular (line)? No wonder people spend so much time arguing.

Shibboleths are words which mark you out as a member of a particular group. What’s the word for a word which different groups have in common, but with wildly different definitions?

Creating a more explicit imperative language

In light of Simon Peyton Jones’ remark of Haskell being an excellent imperative language, what exact combination of “programmable semicolons” is needed to recreate something like C?

newtype C a = C (ReaderT Const (StateT Global IO) a)
    deriving (Functor, Monad, MonadIO, MonadState Global, MonadReader Const)

(The above example is basically just the X monad from the window manage Xmonad.) Is there anything else? Disregarding syntax, is the C monad equivalent to a standard imperative language? (In fact it maybe be more like Python than C, given its higher-levelness.)

Language ambiguity redux

Can we create a similar stack of environments and assumptions for conversation, from more primitive/abstract building blocks? (Obviously, short answer is no. But bear with me.)

More useful would be a type checker for internet arguments that spits out the following when required:

Error: Ambiguous context for keyword `normal' at line 17.

And Reg will not be happy.

module Main where
 
import Data.Maybe
 
fizz = concat $ repeat $ replicate 2 Nothing ++ [Just "Fizz"]
buzz = concat $ repeat $ replicate 4 Nothing ++ [Just "Buzz"]
fizzbuzz = zipWith (maybeWith (++)) fizz buzz
numbers = map (Just . show) [1..]
 
maybeWith f (Just a) (Just b) = Just (a `f` b) 
maybeWith _ (Just a) Nothing  = Just a
maybeWith _  Nothing (Just b) = Just b
maybeWith _  Nothing Nothing  = Nothing
 
-- an infinite list of fizzbuzzes
results = map fromJust $ zipWith (maybeWith const) fizzbuzz numbers

I bothered posting this at all because I feel sure that maybeWith can be implemented as a simple combination of other functions. It’s sort of like liftM2, except it doesn’t throw away good values when it has one good and one bad.

Also, I used it twice in five lines, so it surely must be a known function. But for the life of me I can’t think what it could be.

From a programming language blogger comes this little WTF:

When talking about how dynamic scripting languages are designed, people have a tendency to divide them into “There is more than one way to do it” and “There is one way to do it”. Perl is the quintessential example of “more than one way”, and Python is the opposite, going so far as to make it impossible to have your own indentation.

I am disturbed by the notion that choosing your own indentation counts as language flexibility. Whither the closures, the higher-order functions, the parametric polymorphism? This seems like arguing that a paintbrush that you can also hold in your left hand is inherently more powerful than one you can only hold in your right. And yet neither actually gives you any more interesting abilities than daubing paint.

Spotting patterns is fantastic. There’s something deeply satisfying about bringing together a collection of unrelated items and saying “they all do X”.

We’re all familiar with the concept of addition, and the fact that you can add zero and it doesn’t change the number you’ve added to:

3 + 1 = 4
 
3 + 0 = 3
0 + 3 = 3
 
x + 0 = x
0 + x = x

In this case, we call the number zero the identity for the addition operator. If we use it alongside addition it returns the same number we started with. The same concept arises in multiplication:

3 * 5 = 15
 
3 * 1 = 3
1 * 3 = 3
 
y * 1 = y
1 * y = y

In the case of multiplication, the identity is the number one, but the concept is the same. We have an operation and a special value, and if we use them together on another value, we end up where we started. This works with matrices — adding or mutiplying by the right value can leave us with the original matrix.

[ x y z ]   [ 1 0 0 ]   [ x y z ]
[ m n o ] * [ 0 1 0 ] = [ m n o ]
[ p q r ]   [ 0 0 1 ]   [ p q r ]

Continue Reading »