Tag Archives: logic

Island of Blue-Eyed People

Expert Logician

For a little Friday Fun I have a logic puzzle for you. I’ll give you the puzzle at the beginning of the post, detour to some unrelated topics (to act as a spoiler barrier), and then explain the puzzle in the latter part of the post. I would encourage you to stop reading and think about the puzzle first — it’s quite a challenge. (I couldn’t solve it.)

The puzzle involves an island with a population of 100 blue-eyed people, 100 brown-eyed people, and a very strange social practice. The logic involved is downright nefarious, and even after reading the explanation, I had to think about it for a bit to really see it. (I still think it’s twisted.)

To be honest, I’m kinda writing this to make sure I understand it!

Continue reading

Sideband #61: Tock

relaysYou’ve been waiting for the other shoe to drop, right? The tick to finally tock? (My clock is — as usual — running a bit behind; this should be #62, but that’s another story.) Today’s tale involves electro-mechanical logic! Computing with relays rather than solid-state gates.

Rather than the tick-tock of a mechanical clock, the tock-tick of lots and lots of relays! Aisle after aisle of racks of relays, many thousands of them all clicking away like chattering insects. That’s what is (or was) inside some of those windowless buildings found in every neighborhood with local phone service.

However, today the focus is quite a bit smaller…

Continue reading

Logically Speaking

ttab adder fullIf it hasn’t been apparent, I’ve been giving a bit of a fall semester in some computer science basics. If it seems complicated, well, the truth is all we’ve done is peek in some windows. From a safe distance. And most of the blinds were down.

I thought we’d finish (yes, finish!) with a bang and take a deep dive down into the lowest levels of a computer, both on the engineering side and on the abstract logic side. When they say, “It’s all ones and zeros,” these are the bits (in both senses!) they mean.

Attention: You need to be at least this geeky for this ride!

Continue reading

180 Years of Venn

John VennIn my family, we were rather casual about birthdays and other event days. It wasn’t  unusual to celebrate a birthday, not on the exact day, but on a nearby day. We were fairly poor, so birthdays mostly consisted of a cake and a token present of some sort. (Put it this way: I can’t recall a single birthday present I ever got. We just weren’t that into birthdays.)

But I don’t recall ever not celebrating Christmas or Easter on the day. That may be as much due to my father being a pastor and having to do his thing at church on those days. The religious upbringing — and the strong streak of anti-materialism that went with it — likely accounts for downplaying birthdays and other gift-giving occasions.

Which is all to say that I missed posting on John Venn‘s birthday!

Continue reading

BB #24: No Service

Brain BubbleThe countdown to retirement continues. As I mentioned last Tuesday, this week I pulled the lever on making it official. Six more weeks, and I can put The Company in my rear-view mirror and speed off in my own directions. The big project I’ve been leading looks like it will complete before I exit. We should begin end-to-end system testing in a week or so.

The flip side is that, between tension over retirement and massive project effort during the week (and trying to catch up on blog reading and commenting (and watching baseball)), there isn’t much left for blogging right now.

So you get another Brain Bubble. I would have called this post “No Shoes,” except that it sends the wrong message. This post isn’t about lacking shoes. Or shirts.

Continue reading

Theories About Swans

I’ve written articles here that touched on art theory, quantum theory, science fiction theory and number theory. There are many more theories: gravitational, electromagnetic, economic, social. Of course, there is also pure, practical and applied theory. The idea gets around. On the outskirts there are theories about UFOs, ghosts, Noah’s Ark, many more!

And there are the my theory theories put forth from soap boxes, fliers and now blogs such as this. Literally such as this, since here’s my theory about theories.

A theory, generally speaking, is a kind of statement about some aspect of reality, existence, life. A theory is proven or unproven. If it’s proven, it’s either proven true or proven false. While it is unproven, the matter of whether the statement is true or false remains open. Theories almost always start unproven; some later graduate to proven status.

The goal of any theory is to be proven. In the abstract, it doesn’t matter if a theory is proven true or proven false. (It may matter if you were hoping for a particular outcome!) Once proven, a theory is a foundation on which to build new thoughts, new theories. In fact, proving a theory false can be a good result because it closes all paths leading from that theory. This frees you to explore other areas, which is good; there are so many areas to explore!

It turns out that theories can be hard—or impossible—to prove one way, but much easier to prove the other way. (Which way is true and which is false depends on the theory.) One easy way to prove a theory involves finding an exception to the theory’s statement(s). This leads to the idea of a falsifiable theory; that is, a theory should be something we can try to break. If we can break it, the theory is false. The longer it survives our efforts to break it, the more likely it is the theory is true.

To understand why it works this way we can think about swans…

There’s no such thing as a black swan

Consider two parallel theories. One says that there are no black swans; the other that all swans are white. The two theories are similar in that both make statements about the colors of swans. But the first says there is no such thing as a certain type; the second says they’re all a certain type.

(It is probably easier to imagine proving a much smaller theory: there are no black swans in my yard right now; or if you prefer, all swans in my yard right now are white. Note that although neither theory requires any swans in your yard at all, the second one seems to imply them. More importantly, notice that small theories don’t necessarily translate into big theories. The fact that there are no honest politicians in your yard right now doesn’t necessarily mean they don’t exist at all. More to the point, if there are swans in your yard, theories about their color may not be the best focal point for you right now.)

We can prove the first theory (no black swans) two ways: we can examine every swan that ever was, is now, or ever will be. If we can do that (we can’t, but if in “theory” we somehow could) and find none that are black, then the theory is finally proven true. But if we find a single black one along the way, we stop; the theory is proven false!

The very important point is that proving it false lets us stop testing. It also elevates the theory to a proven status, but—and this is the crucial part—it lets us stop testing. Of course, so would proving it true…

But proving the theory true requires searching all possible swans, and that’s not possible. Generally speaking, a no such thing as theory is, impossible to prove true. It’s impossible to prove that there’s absolutely, 100%, no such thing as UFOs, ghosts, God(s) or flying spaghetti monsters. The only way to prove there’s no monsters under the bed is to check under the bed. Every bed. In all of time and space.

Now consider the second theory (all swans are white). As before, to prove the theory correct we need to examine all possible swans. Again, each swan must confirm to our theory—it must be white—or the theory is proved false (and we stop). But so long as each swan we find is white, the theory is open, and we must continue with the swan search.

A difference is that the second theory (swans all white) is a statement that all swans have a specific trait (color=white). Any color variation makes the theory false. The first theory (no black swans) is a statement that all swans lack a specific trait (color=black). Color variation doesn’t matter so long as it doesn’t vary to the color black. Assuming different swan colors, the second theory should be easier to prove false, because any variation of the trait makes it false.

That is why all X are Y theories tend to end up proving false. The all swans are white theory is as easy to prove false as the all Bruce Willis movies are good theory. Or just about any other theory making universal claims about a group of whatevers. And such theories tend to be ugly when applied to groups of humans—plus they tend to be false—so they are doubly wrong.

Note that the assumption a trait is distributed isn’t always warranted. This is why swans are a canonical theory metaphor. A theory that all swans are white is sensible, because most swans are, in fact, white. And since most swans are white, or at least more white than not, it’s easy to guess that there are no black ones. Swan color, we can imagine, is not distributed. Swan are white; swan are not black.

In any event, proving either theory false—which we can do if we find the right sort of swan—graduates the theory to proven (proven false). We can do this because the theories makes statements we can test and possibly prove false. Both theories are falsifiable.

Reverse Theories

The natural question is, does it work in reverse? Are there theories that are easy to prove true but impossible to prove false? In fact, there are, but in some cases all we end up with is different wording. We’re still breaking the theory by finding an exception to what it says.

Consider the theory some swans are black. This is precisely the reverse of the original black swan version. In this case, finding a black swan makes the theory true (not false, as in the original) and lets us stop. And we must check all swans in creation (and find no black ones) to make the theory false.

A reverse version of the second theory is some swans are not white. Again, the true/false outcomes are reversed. Again, one outcome lets us stop the proof process, the other requires (literally) forever.

Both these theories use some with regard to swans. If a swan qualifies as some swans, then these are precise mirrors of the original theories. But a theory can also involve a group. The theory there are at least 100 black swans, for example. The question is whether a theory about some things is useful. It’s the theories about all things tell us important things about reality.

Getting Formal

For those interested in the technical details, our two theories have formal logical expressions; they can be stated mathematically. Let’s first state the theories a little more formally and then a lot more formally:

For all swans, no single swan is black.
For all swans, each single swan is white.

The formal logic (mathematical!) versions go like this:

s ∈ Swans: ~black(s)
s ∈ Swans: white(s)

The little s stands for a swan; the upside-down ∀ means all (∀ll); the ∈ symbol means is a member (element) of (∈lement); the tilde (~) means not.

So the first one reads as “for any swan in the class of all Swans, that swan is not black.” The second one reads as “for any swan in…all Swans, that swan is white.” In both cases, the theory asserts the formula is true. If we find a case (a swan) that makes the formula false, the theory is falsified.

Keep in mind that black swans and white swans are just a metaphor with no connection to actual blackness, whiteness or swanness. It was all theoretical theory anyway.