Thursday, September 1, 2016

Can we prove a dog is happy?

The previous post talked about qualia, or subjective experiences, but why should we care?  This being a matter of philosophy, there are a variety of answers to that, starting with "Why care about anything?" but nonetheless, there seems to be something significant about the question.  At least from my own subjective point of view.

For one thing, it seems like one of those fundamental questions.  How can we come to a complete understanding of the universe without understanding how we experience it?  Perhaps more than that, there are ethical concerns.  If we wish to increase happiness or we do not wish to cause unnecessary suffering in the world, we should understand what happiness and suffering are.  Outward appearances will only tell us so much.  It would be good to have more reliable indicators, or at least to know how reliable the ones we have are.

The problem with subjective experiences, though, is that they are subjective.  I can be well convinced that my own subjective experience is real.  Sentio ergo sum -- I feel, therefore I am.  There are several reasons for me to believe that someone else's feelings are real: I can see their reactions, they can tell me, and we know that humans have, for the most part, essentially the same neural apparatus.

Nonetheless I cannot know for sure what another person's feelings are in the same way that you and I could both put the same object on a balance scale and agree on its mass.  Each of the common-sense indications I just gave can fail.  Someone may not react visibly to a feeling or experience, or I may not catch the reaction.  They may not be able to tell me for any number of reasons.  Different people can have different ranges of feeling -- what seems intense to me might seem like nothing special to you, or vice-versa.

From a purely philosophical point of view we don't know for sure that having the same kind of neural pathway means having the same kinds of experiences.  Perhaps the ability to experience requires both a certain type of pathway and something else intangible that not everyone has.   Even if there is no such intangible, we're still far from knowing what physical pieces are associated with experience, though we do have some clues.  Without knowing just what pathways gives rise to subjective experience we have no way to be sure everyone has it.

When we go beyond human experience to other species, which react differently, can't verbalize their experiences (or at least not in ways we can presently understand), and have clearly different neural circuitry, we have even less to go on.  We can presume that a dog wagging its tail and barking when its human returns is happy, but it's always possible that dogs have simply co-evolved with us for long enough that they are able to act happy when that would be to their advantage (most people with dogs would dispute this, I expect).

Artificial constructs are even more problematic.  If I build a robot that avoids walls even if you push it toward one, it's easy to say "it doesn't like walls" because it's acting like a sentient being that disliked walls would, but it seems a much bigger step to say "it avoids walls because it experiences negative emotions when it's near one", particularly when we can point to the exact code that causes it to avoid walls.

Even if the code for the control system is extremely complex or has gone through some sort of machine learning process to develop an avoidance of walls, so that we couldn't point to exactly what was making it avoid walls, it still seems hard to argue that the robot is feeling emotions.  If incomprehensible code were the basis of sentience, there would be a lot of sentient software around.

When it comes to what we generally refer to as inanimate objects, the best we can say is that we have no reason to believe that a rock feels pain if we smash it with a hammer.  Nothing in our understanding of how we feel pain seems to apply to something like a rock.  Even so, how can we really know?


But how do we know anything?  We have no way of knowing whether we really live in a universe where the laws of physics hold.  It's possible that tomorrow things dropped will fall up instead of down.  Some theories of cosmology assign a non-zero (but still exceedingly small) chance that we live in such a universe.

In the absence of certain knowledge all we can do is try to build a coherent framework and constantly test and adjust the assumptions it rests on, a process we call "science".  From a scientific point of view we can figure out what sort of neural structures correspond with the subjective experiences that people report.  We can assess whether other organisms have such structures and even whether a particular combination of hardware and software has something functionally equivalent.

We can tell whether something's reactions to various stimuli are consistent with it having such capabilities, based on what people have reported.  We can conclude from that that it's likely or unlikely that the organism or construct we're examining is experiencing feelings, but we can never know for sure, no matter what philosophical machinery we develop for understanding qualia.

But this is nothing new.  Recently it was announced that gravitational waves had finally been detected, stemming from the collision of two black holes over a billion years ago.  The chain of inferences that rests on is mind-boggling.  A more accurate statement would have been "In two separate places, specially constructed instruments registered a signal that indicated that test masses had moved, over a distance much less than the size of an atom, in a way that indicated that space-time had been distorted in a way consistent with the collision of two black holes over a billion light-years away.  We feel confident about this because we believe that science works in general and we're convinced by a large web of observations and theoretical conclusions that the observable universe is billions of years old and billions of light-years in extent, black holes exist and, consistent with a distinct but overlapping web of observations and theoretical conclusions, in certain cases they should produce detectable gravitational waves.  We have also done extensive measurements to convince ourselves that the detectors are in fact detecting gravitational waves and not just trucks driving by ..."

And that would be the short version.  The full version fills textbooks and takes entire careers to grasp even a small portion of.

If science can accept that, can it come to accept that a dog is happy?

Not exactly.  The sticking point here is not whether we can accept a long chain of inference like "People report feeling happy when certain neurons are firing in certain ways, they behave in certain ways when this is happening, dogs have analogous neural pathways, and these tend to fire when dogs are engaged in behavior analogous to that of happy people, and/or people report that the dogs seem happy."  That's not a problem, particularly not compared to the detection of gravitational waves.

The problem is that science depends fundamentally on objective, repeatable measurements of numbers.  Happiness is subjective, and happiness is not a number.  Science can get quite close to measuring happiness, but it's up to us to decide where to go from there -- just like with any other scientific result.

Wednesday, August 10, 2016

Qualia, or why do we experience anything at all?

Today I'd like to discuss a topic which has baffled (at least some) philosophers for quite some time and which I am even more ill-qualified to address than usual.  Since I'm giving general impressions from general ignorance I'll be citing a few well-known examples without attribution.  You can find a good summary here, or it least it seemed like a good one to me.  Rest assured I'm not claiming to be doing any original work here, just ... conjecturing.

The term qualia has come to encompass experiences, and in particular subjective experiences.  For example, what is it like to see the color red, or what is it to be a bat.  Such experiences seem to be subjective, in that the experience depends, at least in principle, on who's experiencing it.  To take a very old example, cliche but no less valid for being cliche, I have no obvious way of knowing whether you experience the color red in the way I do.  Perhaps you experience it the way I experience the color blue, and vice versa, or perhaps you experience it some completely different way.

For that matter, how do I know that you experience anything?  If you and I are at an intersection, stopped at a red light, I can see you react to the light turning green, but that doesn't mean that you had the same experience I did of seeing a red light and then a green light.  I assume that you experienced the sensation of something red and then something green, and that the color red seemed essentially the same way to you as it did to me, but how would I know?

Suppose you were actually in a self-driving car browsing the news on your phone.  You didn't see the light at all.  Rather, the car's cameras recorded the light changing and the car's control system caused the car to go when the light turned green.  I'm perfectly comfortable saying "The car saw the light change and drove through the intersection when it turned green", anthropomorphizing the car, but that doesn't mean I think the car experienced the colors red and green in anything like the way you or I would (or at least, I think you would).

Trying to account for distinctions like this in some objective way has been referred to as "the hard problem of consciousness", as opposed to easier, more empirical problems like "How does the brain record memories?" or "To what extent are we conscious of our own decisions?"

In some sense it's quite likely that all experiences are distinct.  If I see a red paint chip today and then again tomorrow, I will almost certainly have different associations each time.  The first time might put me in mind of a stop sign, or blood, or a red apple.  The second time I might be more focused on whether it's the same paint chip I saw yesterday.  Likewise, you will almost certainly have different associations than I will even if we're looking at the same chip.

And yet, we would probably all agree that we are experiencing seeing something red, and that it feels like something to have that experience.   Even if there's no emotional response, you're still having some sort of experience.  How do we account for that?

Suppose we could account for every firing of every neuron in the nervous system (including the optic nerve, which is actually doing quite a bit of processing before the signal even gets to the brain).  Have we accounted for the experience?  Suppose that after decades of research we compile an exhaustive list of experiences and how they correlate to brain activity.  We bring in a new subject and scan their neural activity.  Pointing at a display, we say "That pattern of firing always occurs in response to seeing the color red".  We can say "that person is experiencing the color red", but how, exactly, do we know that for sure?

It's not hard to imagine what kind of data would back this up.  We hook hundreds of subjects from all over the world and all walks of life up to our highly-advanced brain scanner, flash colors at them and note the results.  We may even ask them to describe what they're experiencing.  When we see the same patterns for our new subject it's a reasonable inference that their brain is processing the color red, and it's reasonable to expect that if we ask them what they're experiencing, their answer will involve the color red.

That's probably good enough for a cognitive scientist, but not a philosopher.  The philosopher may well insist that you don't know what the subject experienced, but only how they would answer a question.  They -- and for that matter any of your other subjects -- might just as well be philosophical zombies who exhibit all the expected behaviors and responses without actually experiencing anything.  We may know intuitively, but we can't prove that the test subjects aren't just like the self-driving car, only on a more elaborate level.


There are a couple of ways out of this.  One is to deny that qualia exist in any well-defined way.  From a logical point of view, this seems quite plausible.  We can talk about the abstract concept of redness, but in real life we don't experience redness in the abstract.  We experience a particular something red at a particular place and time.  That feels a particular way at that place and time, and quite possibly nothing has ever felt quite the same before or ever will.  Maybe we should just stick to our knitting and figure out what happens in real brains in response to real stimuli.  We can still generalize and define abstractions, but if we want an objective description of the world we have to start with objective data.

And yet, we still experience things, subjectively, each of us (or at least I'm pretty sure about me).

So how do we distinguish between a person at a stop light and a self-driving car?  Maybe we don't need to make a strong distinction.  Maybe we're ... not so different.

There's no particular reason, beyond our innate sense of specialness, to assume that only human beings can have experiences.  If we see a hungry dog, our intuition tells us the dog is experiencing hunger.  Our intuition is probably right.  The dog may not be having exactly the same kind of experience we do, but there's no reason to assume it's a philosophical zombie that only looks like it's experiencing hunger.

One way of handling this is to assert that along with the physical properties of the world -- mass, position, velocity and so forth -- there is an experiential component that's completely distinct but which we might still be able to reason about.  Perhaps we will even discover laws that govern it and develop a comprehensive theory of experience.

One objection to this approach is that it seems to imply panpsychism, the idea that everything has consciousness.  There are already schools of thought that believe exactly that, but the concept doesn't sit particularly well in materialist circles (materialist in the philosophical sense).

However, this seems misguided.  If consciousness in the sense of being able to experience qualia is a property in a way similar to mass being a property of things, that doesn't mean that everything has to have that property.  Just as photons are massless, there's no contradiction in saying a rock is unconscious.

Rather than stating that everything has consciousness, we are asserting that objects can have consciousness, and we are trying to investigate under what circumstances that happens.  However, we are explicitly punting on the question of how it has consciousness.  We are saying that when the conditions are right "it just does", just as when a particle interacts with the Higgs field it has mass* (I believe physics has a more detailed account of this than "it just does", but at some point even physics has to make some base assumptions).

From that point of view it's still reasonable to say that a rock has no feelings or consciousness, but a human does, a dog does and just possibly a self-driving car has some limited degree of consciousness as well.  Moreover we may be able to prove that in the scientific sense of having a coherent theory and data to support it.  If so, it seems this theory will look a lot like a purely material explanation of memory, attention and other aspects of consciousness, together with an assertion that when certain of these are present, the thing in which they are present experiences qualia.

What is it to be a self-driving car?  Probably not much, but perhaps something.

* [That's not a really rigorous way to phrase that, but I don't know well enough to give a better one --D.H.]

Saturday, June 11, 2016

Doctors Fermi, Drake and Strangelove

By now it's well-accepted that there are large numbers of planets in the universe that could plausibly support life more or less as we know it.  From this, it follows that unless civilizations like ours are exceedingly rare on such planets, there must be a great number of them in the universe, if not now then at least over history.  A recent paper argues that "... as long as the probability that a habitable zone planet develops a technological species is larger than ∼10−24 [that is, about one in a trillion trillion], humanity is not the only time technological intelligence has evolved".

I've argued elsewhere that numbers like that are beyond our ability to understand directly.  For practical purposes, we can call one in a trillion trillion "zero".  The paper is essentially concluding that, based on what we know now, there (practically) certainly have been other intelligent civilizations in the universe.

In evaluating a statement like that it's important to keep in mind the scales involved.  We're talking about the whole universe here, of which our galaxy is only a tiny part, and we're talking about the entire history of the universe, of which human history is only a tiny part.  The authors make a point of not addressing the question of how many such civilizations there might ever have been in our galaxy, much less close enough for communication with Earth to be practical.

They also make a point of not addressing how many such civilizations there might be right now (regardless of where they might be).  I want to get into the significance of that.


Questions of how many intelligent civilizations there might be generally center around the Drake Equation, which is probably best thought of as a framework for breaking down the problem.  The breakdown is that the number of civilizations we could communicate with must be the product of
  • Three factors representing the rate at which planets form that might support life appear (we're assuming here, for better or worse, that life lives on planets)
  • Three factors representing what portion of those actually produce life that would put out a detectable signal
  • How long those civilizations actually put out a detectable signal (the 'L' factor, for 'lifetime').
We now have a pretty good handle on the first bullet point above.  On the other hand, we don't really know how likely it is that a planet that could support life actually develops life or how likely it is that such life actually puts out a detectable signal.  I've previously argued that, because of the distances involved there's a big difference between "detectable" and "detectable by us" and that the last factor, how long there would be a detectable signal, could be very, very short on a cosmic scale.

The paper I referenced sidesteps these questions by considering everything everywhere and over all time, regardless of whether we could hope to make contact or would even be around to try.  That's fine, but in doing so it shifts from the practical question of "Are we alone?", or Fermi's "Where is everyone?", to the more philosophical question of "Are we unique?".  That's an interesting question, but it somehow lacks the emotional resonance of the other two.



I grew up during the Cold War.  I remember the electricity of the Berlin Wall opening, and the profound feeling of disorientation that came with it.  All my life the East and West had been locked in a permanent stalemate with no sign of an end.  And then it ended.  Now what?

For the most part, life went on.  That's not to say that the transition was smooth, particularly if you had lived in the Soviet Union or its satellites.  My point is more that the "western" developed world, at least, went on more or less as it was.  McDonalds is still McDonalds, Hollywood still makes films, football (or soccer, if you prefer) is still the world's sport, the US still doesn't care greatly that it is, and so forth.  MTV is still the place to go for music videos ... oh, wait ...

Except for nukes.

The amount of nuclear weaponry developed during the Cold War is staggering.  The only two nuclear weapons that have actually been used militarily, the ones dropped on Hiroshima and Nagasaki, yielded under 150TJ (or if you prefer, around 35 kilotons) .  We saw what that did.

Modern nuclear warheads are generally in the thousands of TJ, and tens of thousands of those have been made.  While you can't just multiply numbers and say "Ten thousand times as many bombs each yielding ten times as much means a hundred thousand times as many people killed," it was really no exaggeration, at all, to say that humanity now had the means to cause much, much more destruction than had ever been possible before.

This was a fact of life growing up in the cold war.  My high school newspaper once had a debate in the editorial columns about whether a nuclear war could be survived, at all, and if so whether you should even try.  The bidding started at "The US government would no longer exist" and from there it wasn't far to "Industrial civilization would collapse, bringing about a new Dark Age lasting centuries" or "All humans would die as nuclear winter wiped out agriculture and plunged temperatures by 20 degrees Celsius for decades".  It wasn't completely outlandish to speculate that multicellular life would be wiped out.

This colored our outlook on the world.

Today, not so much, which is interesting since there are still thousands of extremely powerful nuclear weapons in the world and it's not clear that they're as tightly controlled now as they had been.  Just why attitudes might have changed is for another discussion.  For now, let's just take it as a given that "nukes could kill us all" is not nearly as prominent a thought in the early 21st century as it was in the mid to late 20th.



That L factor of the Drake equation represents the amount of time during which an intelligent civilization puts out a detectable signal.  This could be a very short time, on cosmic scales, if only because unless you're actually trying to be detected, putting out radio or other signals that could be detected dozens or hundreds of light years away is a large waste of energy.

If you're streaming video over the internet, for example, no one has to broadcast a signal from a tower.  Even if radio signals are involved they are more likely beamed from one microwave station to another or otherwise narrowly focused.  An intelligent species could quite likely get along just fine for almost all of its existence without producing a detectable signal, if it so chose.

When the Drake equation was first developed, however, this wasn't the interpretation that people tended to use.

At the time, we had no idea whether there were many habitable planets out there, but we had made a few efforts to contact other stars and to listen for signs of life on them (including Drake's own Project Ozma), without any clear success.  That suggested that the factors of the Drake equation must multiply out to a small number.

Since we knew even less then than we know now, most of the factors of the equation were little more than wild guesses.  But we did have at least one data point for an intelligent species (at least by our own definition of "intelligent"), and there was one ready explanation that fit with our understanding of that species and the lack of signs of other species like it: Intelligent species didn't last long.

There was ample reason to believe that.  Perhaps it was inevitable that, at least on the cosmic scale, it would not be long between a species developing technology that could have a major impact on its planet and that species destroying itself.  In 1961, when Frank Drake put forth his equation, it had been less than 20 years since the end of World War II and nuclear weapons testing was in full swing.  It was the most natural thing in the world to wonder if we would make it another 20 years.



Now that we've made it over fifty years since then, it may be more natural to assume that we'll still be here in another fifty, or thousand, or whatever, and either to assume that the L factor could be small for any number of non-lethal reasons or to neglect it altogether on the assumption that we'll be around and detectable forever.  What strikes me here is how much room, within the broad limit that our theories need to be consistent with the facts as we know them, there is for them to reflect who we are at the moment. Then as well as now.

Saturday, May 28, 2016

What is syntax and how much does it matter?

From a computing point of view, when we say "syntax" we're largely talking about "parse trees".  A parse tree breaks a text into components, which are in turn broken down into sub-components, and so forth down to basic pieces analogous to words and punctuation in natural languages.  The largest unit is the root of the tree, and the tree branches wherever you break a larger component into smaller.  As I've said before, this is just like breaking a sentence down into, say, a noun phrase and a verb phrase, breaking the noun phrase into a determiner and a noun, and so forth.

I've also noted that this isn't the only way to break sentences down.  In fact, if you search for sentence diagramming, you're more likely to turn up material on the Reed-Kellog system, and there has been quite a bit of research on dependency grammars.  Both of these have tree structures implicit in them, but you could argue that pretty much any formal system does.  The more relevant point is that they don't emphasize constituency, that is, what's a part of what.  They're more interested in what modifies what, or more generally, what depends on what.

So, what is this syntax that we speak of?  I previously defined it as "the study of how words fit together in sentences".  Wikipedia has it as "the set of rules, principles, and processes that govern the structure of sentences in a given language, specifically word order", which seems pretty similar except for the emphasis on word order.  What sparked this post, however, was a statement in an Nat Geo blog post on killer whales (a.k.a. orcas, but that's a separate discussion), that
Language in the strict sense means syntax, which means that word placement determines meaning. So, “Put the blue pillow on the red pillow” means something different than, “Put the red pillow on the blue pillow.” Same exact words, different order. That’s language. Some dolphins and some apes have the ability to understand human syntax.
Killer whales are dolphins—the biggest ones. I am not aware of whether they understand human syntax. 
Initially I was struck by the simplicity of "word placement determines meaning" followed by a convincing example.  Later, I wondered how well that notion (or "specifically word order" in the Wikipedia definition) applies to languages with free word order.  Certainly order matters in narrating a story, or in figuring out which noun a pronoun might refer to, but in many languages ordering is more a matter of emphasis than meaning.

But now what strikes me about this passage is the emphasis on understanding.  This tends toward a more operational definition of syntax, for example, can you understand the difference between Put the blue pillow on the red pillow and Put the red pillow on the blue pillow.

Intuitively it seems like understanding the difference between Canis hominem mordet (dog bites man) and Canem homo mordet (man bites dog) would be much the same task, even though the word order is the same for both of those sentences.  So what are we really after here?

Fundamentally the problem to solve is communicating information reasonably efficiently and accurately.  I almost said "communicating concepts", but this depends on what concepts the parties involved can understand.  I may have a perfectly concise way to say "The square of the hypotenuse is equal to the sum of the squares of the legs", but that's not going to help much if my listener doesn't know what a hypotenuse is.

There's one other piece here, though.  Many species are capable of communicating a repertoire of messages, and even of learning new messages for that repertoire.  Vervets famously have different alarm calls for their main predators (leopards, eagles, pythons, and baboons).  They can also adjust to individuals that consistently make the wrong call, recognize their offspring by their calls and possibly invent new calls for new dangers.  Some dogs can be taught names for dozens of different objects which they can then retrieve by name.  Neither, however, seems to have language in the same way we do.

To establish that something unusual is going on, as with theories of mind, we need some sort of combinatorial explosion, that is, a situation in which a small number of basic pieces generate a very large number of possibilities.

For example, if we have a red pillow, a blue pillow, a red box and a blue box, and any one of them can be put to the left of, to the right of, in front of, behind, on top of or under any of the others, there 72 different combinations (red pillow to the left of blue pillow, red pillow to the left of red box ... blue box under red box), though since "red pillow to the left of blue pillow" is the same as "blue pillow to the right of red pillow" there are really only 36 possibilities, but 72 ways of expressing them.

The number of possibilities increases as the square of the number of objects.  If you double the number of objects, there are four times as many possibilities.  Similarly, if you add a new directional relation, say "to the left of and in front of", you've added as many possibilities as there are pairs of objects.  If you add a new kind of relation, say "close to" vs. "far from" (leaving aside whether you can place a red pillow far above a blue box), you've multiplied the total number of possibilities by a new factor.

For example, if you have ten objects, twelve directional relations and "touching", "close" and "far apart", you now have 1620 possibilities.  You haven't added much to the original setup, but there are now 45 times as many possibilities as before.  It's easy to see how you could make this much, much bigger just by adding more different kinds of distinctions.

Imagine an experiment where your subjects are (somehow) taught signs for the four objects and six directional relations, and then (somehow) required to communicate a particular arrangement.  Say subject 1 is shown an arrangement that subject 2 can't see, and if it can convince subject 2 to create the same arrangement they both get a reward.

If your test subjects can handle the original setup of 36 possibilities, it's possible that they learned the examples you gave by rote and guessed on ones they hadn't already seen.  You could control for that by making sure the two subjects are shown different examples, but if you want to run several trials and there are only 36 possibilities to choose from, it's hard to be sure that any significant syntax is involved.

On the other hand, suppose you have a pair of subjects that can handle the small setup, and then you add a new object.  After they see a couple of examples involving the new object they can handle unfamiliar setups involving it about as well as they can handle the originals.  You then give a few examples of a new relation (say, diagonal as above) and their performance doesn't suffer.  You then show a new kind of relation (say, distance as above) and they can still handle it.  You've now got a reasonably large space of arrangements to choose from and you can easily do repeated trials without repeating the exact arrangements.

At that point, I'd say you can infer that the communication system has some way not only of distinguishing "red pillow on top of blue pillow" from "blue pillow on top of red pillow", but distinguishing "A on top of B" from "B on top of A" in general.  I'll claim that at that point you can reasonably say there is syntax in some form, as well as some form of "abstract relation".


This is not the same as saying the experimental subjects have the same kind of language as we do.  You can solve the problem in the experiment with any way of selecting an directional relation, a first object, a second object and an distance relation.  That could be as simple as listing the four in order, as "red-pillow blue-pillow in-front-of close".

Handling new kinds of relations or constraints (e.g., put the pillow fuzzy side up) doesn't require much more syntax.  If the system can distinguish one relation/constraint from another, then something like "direction: red-pillow in-front-of blue-pillow, distance: close, orientation: red-pillow fuzzy-side-up" packs in a lot of information, and it's easy to see how you would extend it.


Where does that leave constructs that we tend to think are unique to human language, including dependent clauses like that I saw yesterday in The movie that I saw yesterday was two hours long?  I'm not sure how to set up an experiment like the previous one that could distinguish a language with dependent clauses from one without.  After all, I could just as well say I saw a movie yesterday.   That movie was two hours long.  This requires using that in its sense as a determiner to link the sentences together in a particular way.  This is still a pretty powerful construct, but it doesn't require tucking I saw the movie yesterday in as a direct modifier to movie.

From this point of view, the distinction between having dependent clauses and not having them is not particularly important.  This is in contrast to the computer science-y view that I've been most familiar with, where there is a huge distinction between recursive structures -- ones that can contain sub-parts of the same general form as the structure they're part of, such as sentences acting as clauses inside larger sentences -- and non-recursive structures, which can't.  One important distinction from that point of view is that there are in principle infinitely many possible structures -- sentences, say -- if recursion is allowed but only finitely many if it's not.

This is true in the mathematical world, but it's less important when considering real communication.  On the one hand, there are only finitely many sentences that are short enough for a real person to say or understand.  In practice, we rarely nest more than a few levels deep.  When we do, the result is often pretty hard to understand.

On the other hand, "finite" as a mathematical concept includes numbers large enough to be infinite for any practical purpose.  In fact, I've argued, almost all numbers are vastly too big for us to comprehend, let alone to occur in any natural context.  In practice, this means that even if you have only a handful of template sentences to fill in and you can't nest sentences within sentences, you can still end up with a gargantuan number of possible sentences -- and there's no reason you can't use more than one sentence in a conversation (technically, stringing sentences together can be expressed as recursion, but let's not get into that).



What if you can't do a controlled experiment to figure out how complex a communication system is?  What if all the data you have is from observations in the wild?  What if you're not sure what part of the noises, gestures or whatever else you observe are or aren't significant?  The task is certainly harder, then, but maybe not infeasible.  You're still looking for signs of combinatorial explosion, particularly the ability to deal with novel combinations of factors in a way that requires communication, that is, where
  • Different individuals have different information,
  • they need to share that information,
  • the exact information to share varies within a combinatorially large space of possibilities, and
  • the individuals involved are able to act usefully in ways they couldn't have without sharing the information.
The first two and the last are easy to find in any number of situations (arguably the second and last points are just different ways to say the same thing).  When a vervet sees a baboon, it shrieks out the alarm call for baboons and all the vervets skedaddle, you've met all but the third point.  From observation, it's reasonably clear that there isn't a combinatorially large space of possibilities.  There is a relatively small and constant set of calls.

Human communication clearly satisfies all four points.  Most of the sentences in this post, for example, are not only unique to the post but most likely unique to all human communication (I'm going to guess that the phrase "vervets skedaddle" is fairly rare in its own right -- it didn't turn up when I googled it with quotes, though that should soon change ...).  This is not something I consciously aimed for, just a natural consequence of writing reasonably long sentences in English (or any other natural language for that matter).

The interesting question is whether anyone else meets the third point.

Saturday, April 30, 2016

Yours for a the special introductory price of ...

The student housing I lived in as an undergrad was modeled after, among other things, European monasteries, which is a nice way of saying the rooms were rather on the small and plain side ... which in turn is a nice way of saying you wouldn't want to live in them unless you really wanted to live in the student houses. Which most people did.

You may not be surprised to hear that people cared a lot about which room they ended up in.  There was a whole ritual at the beginning of the school year to decide in what order people got to pick rooms, based on one's class, status as a house officer and possibly other factors I no longer remember.  Ordering within groups of equal rank, for example most if not all the freshmen, was decided by drawing cards, and so the whole boisterous mess was called "room draw".

Why did people care so much which of several possible broom closets they ended up in?  Well, you wanted to be in the same cluster of rooms with people you liked, you might not want a room over the courtyard where the garbage trucks came at uncivilized hours of the morning, you might feel better at the end of a hall, or in the middle, you might want to be near the showers or not so near ...

The reasons were limitless and probably largely subconscious.  Sometimes it didn't matter.  Sometimes the people picking ahead of you had different priorities and you ended up with something close your ideal, but not always.  Some rooms were almost universally considered good -- and were almost always occupied by seniors -- or not so good -- "Welcome to the house, frosh.  Here's your room!"

It was not unknown for people to run for house offices in which they had little interest simply for the room pick.  Does anyone really want to be house secretary?



Did you know you can buy land on Mars?  It's not clear under what legal authority one can own land on Mars, but that hasn't stopped people from selling it.  Apparently copyright law is involved, and that ought to tell you about all you need to know.  One site quotes $30/acre.  The surface area of Mars is about 36 billion acres, so there's quite a bit of "upside potential".  I'm guessing that the site in question has sold considerably less than the full allotment, but they have sold some.

OK, let's assume that you really can own a claim on a piece of Mars.  What are you getting?

There's always the small chance that someone will set up an outpost on land you own, in which case you can say "Hey, buddy, I own that" and they can say "OK, nice to know, but we're actually on Mars and we care about your claim, why?"

What you're really buying is bragging rights.  You can say to your friends "Hey look, I own a piece of Mars.  Says so right here."  I can easily see someone wanting to pay $30 for that, especially if someone is keeping track of all the claims and you can honestly say "This particular area is mine and nobody else's (at least according to this particular keeper-tracker-of-er)".

Likewise, you can buy your name on a star.  The International Astronomical Union, being the body in charge of giving stars boring catalog numbers, won't be particularly impressed, but that won't stop people from accepting your money.  I sincerely hope that nobody is pretending that this is anything more than buying the right to have a name of your choice associated with a star of your choice in somebody's list, but again I could understand someone paying a small fee for the privilege because why not?



On the other blog I wrote about the fascinating case of Cow Clicker, a Facebook game reduced to its very essence, in which people eventually ended up paying for the right to click on a space where a virtual cow had once stood.  During the period when there were actual (virtual) cows to click on, people willingly paid for custom cows, including a $100 "Bling Cow".  Basically you were announcing to your friends "I bought a Bling Cow", plus you had the pleasure of clicking on a cow with gold accessories.



But is this business of buying virtual cattle or pieces of the sky really abstract or arbitrary enough?  We can do better.  For the low introductory prices of ... leaving a message in the comments section, I will give you your very own number.  That's right.  Just leave a short, innocuous piece of text you want immortalized, and I will send you the output of

GIBBERISH=<some randomness I will keep to myself>
MESSAGE=<your message>
echo "print 0x$(echo "${GIBBERISH}${MESSAGE}" | sha256sum | cut -c 1-64)" | python

This lovely shell incantation pastes my gibberish together with your message, uses the SHA256 cryptographic hash algorithm to boil this down to 64 digits of hexadecimal and then uses some hackery to convert that to decimal.

So long as the SHA256 algorithm remains secure, the odds that someone could find another message that gave the same number as your message are astronomically low.  For that matter, so are the odds that anyone in human history has ever seen the number for your message before, and so are the odds that anyone who doesn't know what gibberish I chose could tell you what number would result from any given message.  Yes, the recipe for mapping messages to numbers is mine ... all mine ... BWAHAHAHA!

Sorry, let it go to my head for a moment.

To get the ball rolling, I claim "squeamish ossifrage" as my message, and I am therefore proud to announce that my personal number is

71550457262820168189328333318549162861663280827014445611156956018117368386158

Let the games begin.

Saturday, April 9, 2016

Primitives

Non sunt multiplicanda entia sine necessitate.

This is one of several formulations of Occam's razor, though Wikipedia informs us that William of Ockham didn't come up with that particular one.  Whatever its origins, Occam's razor comes up again and again in what we like to call "rational inquiry".  In modern science, for example, it's generally expressed along the lines of "Prefer the simplest explanation that fits the known facts".


If you see a broken glass on the floor, it's possible that someone took the glass into a neighboring county, painstakingly broke it into shards, sent the shards overseas by mail, and then had a friend bring them back on a plane and carefully place them on the floor in a plausible arrangement, but most likely the glass just fell and broke.  Only if someone showed you, say, video of the whole wild goose chase might you begin to consider the more complex scenario.

This preference for simple explanations is a major driving force in science.  On the one hand, it motivates a search for simpler explanations of known facts, for example Kepler's idea that planets move around the Sun in ellipses, rather than following circular orbits with epicyclets as Copernicus had held.  On the other hand, new facts can upset the apple cart and lead to a simple explanation giving way to a more complicated revision, for example the discoveries about the behavior of particles and light that eventually led to quantum theory.

But let's go back to the Latin up at the top.  Literally, it means "Entities are not to be multiplied without necessity," and, untangling that a bit, "Don't use more things than you have to", or, to paraphrase Strunk, "Omit needless things".  In the scientific world, the things in question are assumptions, but the same principle applies elsewhere.



The mathematical idea of Boolean Algebra underlies much of the computer science that ultimately powers the machinery that brings you this post to read.  In fact, many programming languages have a data type called "boolean" or something similar.

In the usual Boolean algebra, a value is always either True or False.  You can combine boolean values with several operators, particularly AND, OR and NOT, just as you can combine numbers with operations like multiplication, addition and negation.  These boolean operators mean about what you might think they mean, as we can describe them with truth tables very similar to ordinary multiplication or addition tables:

ANDTrueFalse
TrueTrueFalse
FalseFalseFalse

ORTrueFalse
TrueTrueTrue
FalseTrueFalse

NOTTrueFalse

FalseTrue

In other words, A AND B is true exactly when both A and B are true, A OR B is true whenever at least one of the two is true, and NOT A is true exactly when A is false.  Again, about what you might expect.

You can do a lot with just these simple parts.  You can prove things like "A AND NOT A" is always False (something and its opposite can't both be true) and "A OR NOT A" is always True (the "law of the excluded middle": either A or its opposite is true, that is, A is either true or false).

You can break any truth table for any number of variables down into AND, OR and NOT.  For example, if you prefer to say that "or" means "one or the other, but not both", you can define a truth table for "exclusive or" (XOR):

XORTrueFalse
TrueFalseTrue
FalseTrueFalse

If you look at where the True entries are, you can read off what that means in  terms AND, OR and NOT: There's a True where A is True and B is False, that is, A AND NOT B, and one where B is True and A is False, that is, B AND NOT A.  XOR is true when one or the other of those cases hold. They can't both hold at the same time, so it's safe to use ordinary OR to express this: A XOR B = (A AND NOT B) OR (B AND NOT A).  The same procedure works for any truth table.

In a situation like this, where we're expressing one concept in terms of others that we take to be more basic, we call the basic concepts "primitive" and the ones built up from them "derived".  In this case, AND, OR and NOT are our primitives and we derive XOR (or any other boolean function we like) from them.

Now consider the boolean function NAND, which is true exactly when AND is false.  Its truth table looks like this:

NANDTrueFalse
TrueFalseTrue
FalseTrueTrue

This is just the table for AND with True entries changed to False and vice versa.  That is, A NAND B = NOT (A AND B).

What's A NAND A?  If A is True, then we get True NAND True, which is False.  If A is False, we get False NAND False, which is True.  That is, A NAND A = NOT A.  If we have NAND, we don't need NOT.  We could just as well use AND, OR and NAND instead of AND, OR and NOT.

Since NAND is just NOT AND, and we can use NAND to make NOT, we don't need AND, either.  A AND B = (A NAND B) NAND (A NAND B).  So we can get by with just NAND and OR.

As it turns out, we never needed OR to begin with.  Quite some time ago, Augustus De Morgan pointed out that A OR B = NOT (NOT A AND NOT B), that is, A or B (or both) are true if both of them are not false, a rule which sometimes comes in handy in making "if" statements in code simpler (the other version of the rule, with the AND and OR switched, is also valid).  Using NAND, we can recast that as A OR B = (NOT A NAND NOT B), and we can get rid of the NOT, leaving A OR B = ((A NAND A) NAND (B NAND B)).

Summing up, we can build any boolean function at all out of AND, OR and NOT, and we can build all three of those out of NAND, so we can build any boolean function at all from NAND alone.

For example A XOR B = (A AND NOT B) OR (B AND NOT A).  We can use DeMorgan's rules to change that to (NOT (NOT (A AND NOT B) AND NOT (B AND NOT A))), that is, (NOT (A AND NOT B)) NAND (NOT (B AND NOT A)), or more simply, (A NAND NOT B) NAND (B NAND NOT A).  We can then replace the NOTs to get (A NAND (B NAND B)) NAND (B NAND (A NAND A)).

Yes, it's ... that ... simple.  Feel free to plug in all four combinations of A and B to check.

As silly as this may seem, it has real applications.  A particular kind of transistor lets current flow from its source terminal to its drain terminal when the voltage on a third terminal, called the gate, is high.  Put a high voltage on the source and let current flow either through the transistor or through an output for the whole thing.  Tie the gate of the transistor to an input.  If the voltage on the input is high, current will flow through the transistor and not to the output.  If the voltage on the input is low, current will flow to the output and not through the transistor.  That is, the output voltage will be high when the input voltage is not.  The whole thing is called a NOT gate (or inverter).

If you put two transistors in a row, then current will only flow through both of them when the voltage on both of the inputs is high, meaning it will flow through through the output, and the output voltage will be high, unless the voltage on both of the inputs is high.  The whole thing is called a NAND gate, and as we saw above, you can build any boolean function you like out of NANDs *.

In fact, we have it a bit easier here because we can build NOT A directly instead of as A NAND A, and for that matter we can build a three-input NAND  -- NOT (A AND B AND C) -- easily as well, but even if we couldn't, being able to build a NAND would be enough.



There are other cases where we can build up a whole system from a single primitive.  Notably, any computer program (technically, anything a Turing machine can compute) can be expressed in terms of a single instruction or, alternatively, a single "combinator".   This includes any boolean function, any numerical function, an HTML parser for web pages, whatever.  Of course, there's a difference between being able to express a computation in theory and being able to run it on your laptop or tablet.  We'll come back to that.

Before we go on to what all of this might mean, it's worth noting that many significant areas of thought haven't been reduced to simple primitives.  For example, chemistry is built from around a hundred elements (there are currently 118 on the periodic table, but you can't do meaningful chemistry with all of them).  An atom of any element is composed of protons, neutrons and electrons in varying numbers.

The Standard Model recognizes electrons as elementary, that is, primitive, while protons and neutrons are composed of quarks.  In all, it holds that there are 17 particles that everything is composed of  -- six quarks, six leptons (including the electron), four gauge bosons and the Higgs.  So far, no one has found anything simpler that these might be built up of, but not for lack of trying.

In mathematics, you typically start with a handful of axioms -- statements you assume to be true without proof -- and build from there.  There has been extensive work in reducing this to a minimal foundation, but the current formulation of set theory together with model theory has several important basic pieces, not one single concept to rule them all.  And, in fact, there are several ways of describing both set theory and model theory, not one single definitive way.

In short, some things can be reduced to a single primitive, but most can't.  Even when you can reduce something to a single primitive, there are typically several ways to do it.  For boolean algebra, you can just as well use NOR as NAND.  In computing there are several universal operations with little to pick among them.



In theory, there is no difference between theory and practice. But, in practice, there is. (attributed to Jan v/d Snepscheut)


If you can reduce any boolean function to NAND, is Boolean algebra in some meaningful sense really just NAND?  Is computing really just the study of a single instruction or operator?  If we're trying to reduce the number of entities involved, following Occam, is it not better to study a single operation than many?

I think most working mathematicians and computer scientists would answer "No" to all of the above.  A general Boolean algebra is a set of objects and operations that follow certain rules.  We noted above that A AND A = A.  In set theory, the union of a set with itself is that set, and there are other examples.  We would like to capture that common behavior somehow, and we do it by defining rules that hold for anything that behaves in the way we're interested in, that is, axioms.  In the case of Boolean algebra there are five (chase the link if you're interested).

It just so happens that in the simple case of True, False and the operations on them, NAND and NOR can be used to build all the others.  That's nice, but not essential.  It's of interest in building circuits out of transistors, but even then there's no requirement to build everything from one type of gate if you don't have to.  As noted above, it takes fewer transistors to build a NOT directly, and that's how real circuits are built.

Even from the point of view of Occam's razor, it's not clear that reducing everything to NAND is a good idea.  Yes, you have only one operation to deal with, but you can define one truth table just as easily as any other.  If you want to use XOR, it's simpler to define the truth table for it than to define the truth table for NAND and then define XOR in terms of it.

In computing, if you have the machinery to rigorously define one instruction or operation, you can define as many as you like with the same machinery.  It may be interesting or even useful in some situations that you can define some operations in terms of others, but it doesn't make the system more useful.  In practice, I don't care how many instructions the processor has.  I care very much if there's an easy way to talk to the network or write to a file, things which are not even mentioned in theoretical discussions of computing (nor should they be in most situations).

So why even bother?  Is reducing a system to a single primitive just an interesting academic exercise?  Not necessarily.  If you're trying to prove properties about circuits or programming systems in general, it can be useful to divide and conquer.  First prove, once and for all, that any circuit or program can be reduced to a single primitive, then prove all sorts of useful properties about systems using that primitive.  Since you only have a single operator or whatever to deal with, your proofs will be shorter.  Since you've proved your operator is universal, they'll be just as powerful.  Essentially you've said that when it comes to general properties of a system, adding new operators or whatever doesn't do anything interesting.

You don't have to reduce everything all the way to a single primitive for this to be useful.  If you can only reduce a system to five primitives, doing proofs using those five is still easier than doing proofs on an equivalent system with twenty.


In general, there's a tension between keeping a system minimal and making it easy to use.  A minimal system is easier to build and it's easier to be confident that it works properly.  A larger system is easier to use, as long as there's not too much to take in.  Typically there's a sweet spot somewhere in the middle.

There are sixteen possible boolean operators on two variables, and you can build any of them up from NAND (or NOR), but usually we focus on three of them: AND, OR and NOT.  These are enough to build anything else in a way that's straightforward to understand.  They also correspond fairly closely to familiar concepts.   In some useful sense, they minimize the number of things you have to deal with in normal cases, and William of Ockham can rest easy.

It doesn't only matter how many things you have.  It matters which things.




* As usual, there are a few more wrinkles to this.  You have to tie the output of the last (or only) transistor to ground for current to flow, you need a resistor next to the input, the output also needs to be tied to ground eventually, and so forth.

You may have noted that current is flowing through the two transistors in the NAND gate precisely when both inputs are high, that is, the current is flowing through them (and not to the output) when one gate voltage is high AND the other is.  You might think it would be simpler to build an AND than a NAND.  However,  the current will only flow if the drain of the last transistor is connected to a low voltage.   That voltage will be low regardless of what's happening on the gates.  To see a difference in voltages, we have to look at the voltage at the top, which will vary depending on whether current is flowing through the transistors (that's probably not too clear, but it's the best I can do).

Sunday, February 14, 2016

Chaotic demonyms

I don't recall having run across the word demonym before Wikipedia, though I may well have run across it and forgotten it.  It's certainly one of those words that appears disproportionately often in Wikipedia (Note to self: What are some others?  Despite the title, this post on the other blog doesn't really offer any)

So what's a demonym?

A demonym (demos = people, nym = name) is a word for someone or something from a particular place.  At least in Wikipedia, a demonym is a noun (I met a Canadian the other day).  The adjectival form is generally the same (We stopped at the Canadian border), but not always (I met a Swede at the Swedish embassy).

Demonyms are a bit of a mess.  Why is it Canadian and not Canadan (or why isn't the country Canadia)?  Why is someone from Washington a Washigtonian but someone from London a Londoner?  Why is someone from Manchester a Mancunian?  From Monaco a Monegasque?  What about Michigander and Arkansawyer, not to mention Hoosier?

Language is full of cases like this that can't be fully described by hard and fast rules, but aren't completely random, either.  For example, let me digress a bit about English regular and irregular forms.

In English, most verbs can be completely described by rules (I rest, he/she/it rests, you rest ... I/he/she/it/you/... rested, I/he/she/it/you/... have rested, I/he/she/it/you/... will rest).  One English verb is highly irregular: I am, he/she/it is, you/we/they are, I/he/she/it was, you/we/they were, I/he/she/it/you/... have been, I/he/she/it/you/... will be).  This is an example of suppletion, where entirely different words fill in for different roles.  Another example is can in dialects that don't use forms like might can but instead say might be able to.

Quite a few English verbs, including many of the most common ones, are somewhat irregular.  They follow the rules in present tense (I sing, he/she/it sings ...) but use a slightly different form for the past tense (I sang) and possibly yet another for the past participle (I have sung).  These are mostly if not entirely holdovers from older Germanic ancestors of modern English, which used vowel changes to indicate tense (more on the ancestry of English here and here) [one exception is snuck, which used to be sneaked].

There are similar cases for nouns (one goose, two geese), but nouns have an extra wrinkle.  For some borrowed nouns we also borrow a plural form (one alumnus, two alumni).  In at least one case we try to borrow a plural but miss (one octopus, two octopi ... but that should probably be two octopodes, or just say two octopusses and be done with it).  When we borrow a plural we're generally not too fussy about the exact details of the source language's inflections.  We say of alumni and not alunorum, for example.

None of this is unique to English.  Languages in general tend to have irregular forms due to ancestral holdovers, borrowing and such.

So where does that leave us with demonyms?

Just as with nouns and verbs, there are some regular cases.  I can't think of any place ending in -ia that doesn't have -ian for its demonym: Asian, Bavarian, Croatian, Dalmatian, ...  This is the "unmarked" case.  If we want to designate a place and its people in English, regardless of what the locals call the place and themselves, we tend to take some root particular to the place and use -ia for the place -ian for the demonym.

On the other hand, there are plenty of cases of full-on suppletion: Bay Stater (Massachusetts), Hoosier (Indiana), Tar Heel (North Carolina), Scouser (Liverpool) ...

And then there's a lot of interesting territory in the middle.  I'd break it down into
  • Cases where we use some variation of -ian, but it's hard to predict which one: Canadian, Floridian ... but Manitoban, Kansan, Canberran ... and even European and Panamanian.  My guess is that most of these can be described by assuming a basic form, probably -ian, together with some rules that would change Iowaian to Iowan and Kansasian to Kansan.  That's not to say that we actually think that way, just that such rules may do a decent job of describing what's going on.  With, of course, some inevitable exceptions because ... language.
  • Cases where we use a different form instead of -ian and its relatives.
In the latter case there are still regularities.  Generally if the place is X-land, the demonym will be X-lander (Rhode Islander, Newfoundlander ...), notwithstanding the Irish, English, Poles, Marshallese and almost certainly some others.  There are also several cases, generally from western Asia, where we borrow the -i suffix: Gujarati, Kuwaiti, Israeli, Pakistani ...  Those appear to be generally regular, just using a different set of rules.

Even accounting for cases like "use -er with -land" and "OK, so we borrowed Gujarati", there is still a region of apparent chaos.  I can see why Wyomingian would be a bit of a mouthful, but why Wyomingite in particular and not, say, Wyominger?  Why Connecticutter and not Connecticutite?  For that matter, why Vermonter and not Vermontian?

Have a look at these lists in Wikipedia (here, here and here).  Maybe you can set out some nice, crisp rules for the various -ites, -ers (besides -landers), -eses (c.f. -esians) and so forth.  I couldn't, and my guess is that it can't be done in a way that doesn't end up looking highly ad hoc (or post hoc?).

I chose the word "chaos" above not just to suggest disorder, but to suggest a particular kind of disorder.  Mathematical chaos often occurs at the boundaries between otherwise regular regions.  Outside a small region, the Mandelbrot iteration always diverges.  Inside a fairly simple boundary, it always converges.  Only in between those two, where it's not clear which outcome will happen, do things get messy.  Finding roots of equations with Newtonian iteration behaves similarly.  In most cases you quickly find one of the roots but in the boundary regions you can't really tell where you end up.

I suspect something analogous is going on here.  Most places are inhabited by -ians, but where that doesn't work and you don't have a definite alternative, what you end up with is essentially luck of the draw.