Skip to main content

Movements of Thought

Why Computers Work (part 2)

(Part 1, part 3, part 4, part 5)

Just as one can describe rules for a card game, it is possible to describe rules for thinking: rules for movement of thought.

This is the study of Logic, and using these rules is called reasoning. Reasoning with logical rules allows others, who know such rules, to follow the movements of thought that brought you to a certain conclusion. Furthermore, because there are rules, it's possible to notice when they're ignored or used incorrectly (when movements of thought don't make logical sense).

There are many types of logic, but the one we're going to examine is called propositional (or sentential, or boolean) logic.

"Propositional" and "sentential" are just descriptive names for a type of logic that deals with forming sentences by combining propositions. In logic, propositions make assertions that are either true or false. George Boole (1815-1864), shown below, invented a system of mathematical algebra that works like propositional logic (it also deals with values that are either true or false) and so the term "boolean" is often used synonymously.

George Boole
Source - this image is in the public domain.

Here's a contrived example of a sentence in propositional logic:

"If it is sunny and I am wearing a thick coat, then I am hot."

I want to draw your attention to some important aspects of this sentence that may not, at first, appear obvious:

  • It contains two propositions called premises ("it is sunny" and "I am wearing a thick coat"). Premises make assertions about states of affairs.
  • It ends with a conclusion ("I am hot"). A conclusion is a proposition that depends upon the premises in some way.
  • The sentence is in the form of a conditional ("if [premises], then [conclusion]"). A conditional is a rule saying that if its premises are true then the conclusion must be true.
  • The premises are related to each other by a logical operator called a conjunction ("and"). This is another rule: if the related premises are evaluated together, collectively they are true only if all of them are true.

Propositional logic describes the rules of a "game" to construct sentences that make logical sense. Playing by the rules of logic forces everyone to reach the same inevitable conclusion: if we accept that the premises are true (it is sunny and I am wearing a coat) propositional logic dictates the conclusion must be true (I am hot). The object of propositional logic is to use the rules to evaluate (work out) if a sentence is true or false.

Here's the brain twist: propositional logic doesn't care about meaning. The important logical aspects of the example above don't concern my state in the real world (which is why the sentence sounds slightly odd). Propositional logic only cares about truth and how propositions fit together. I could revise the example to:

"If A and B then C."

It doesn't matter what A, B or C stand for nor what they may mean -- from the perspective of propositional logic all that matters is there are two conjuncted premises (A and B) and a conclusion (C) expressed in a conditional (if ... then ...). If one or both of the premises is false, then the conclusion must also be false. Why? Because the logical rules pertaining to conditionals and conjunctions (and nothing else outside those rules) make it that way!

The brain twist is divorcing yourself from meaning -- just concern yourself with truth values of the propositions, the structure of the sentence and following the rules.

In the same way the rules of Snap explain what must happen, given card related states of affairs, so the rules of propositional logic do the same with propositions and sentences. The rules of Snap don't care what the specific values of cards are, just that such values may match. Similarly, propositional logic doesn't care what the specific meanings of the propositions may be, only that such propositions connect in a sentence that can be evaluated with rules dealing in just two possible states: true and false.

The simplest way to express the rules that govern such logical operations for connecting propositions is with a truth table.

Here's the definition of "and" (conjunction):

 A | B | A and B
----------------
 F | F |    F
 F | T |    F
 T | F |    F
 T | T |    T

Can you see how it works?

The first two columns represent propositions labelled "A" and "B". The third column represents the outcome of the "and" operation, given the values of "A" and "B" in the first two columns. Each possible combination of truth value for "A" and "B" is enumerated as a row with the resulting truth value for the "and" operation in the third column. It's a simple tabular way to express the rules of propositional logic. If you had any doubt how "and" (conjunction) worked, you'd find the definitive answer in this truth table.

For instance, take the first row: if propositions "A" and "B" are both false (as expressed in the first two columns), then the outcome for this rule (expressed in the third column) must be false.

Here's another truth table that defines the rule for the logical operation called "or" (disjunction):

 A | B | A or B
---------------
 F | F |   F
 F | T |   T
 T | F |   T
 T | T |   T

Let's pretend that "A" is false but "B" is true. How would you evaluate the truth value of "A or B"? Is it true or false?

The answer is that "A or B" is true. Why? Because the second row tells us so: the "A" column is false, the "B" column is true so the result, expressed in the third column, is true.

Here's one final truth table. It's a bit different to the other two since it only works on a single proposition:

 A | not A
----------
 T |   F
 F |   T

It's easy to see what the "not" (negation) operation does to a proposition: it flips its truth value so false becomes true, and true becomes false.

While these logical operations have familiar names ("and", "or" and "not") that appear to relate to how they work, it is the truth table and only the truth table that defines how they behave in propositional logic, not any similarity to how we may use such words in everyday English. There are further rules, expressed as truth tables, for connecting propositions that you may wish to look into. They are XOR (eXclusive OR), NAND (Not AND), NOR (Not OR) and XNOR (eXclusive Not OR).

Logical puzzles become fun when you combine such logical operations to build more complicated structures. Take for example:

(A and B) or (C or not D)

I've put parentheses ("(" and ")") around propositions so you can see how they relate to the logical operators (the and, or and not). If we pretend all the propositions represented by letters are false, what is the overall truth value of the sentence?

To find the answer we play the logical "game" in the same way we would with Snap: we follow the rules.

Start by evaluating the operators within the parentheses. If we replace the propositions "A" and "B" with their truth values (remember, all the propositions are false), we get:

(false and false) or (C or not D)

Given the rule set out in the truth table for "and", the propositions in the first parentheses evaluate to false. Here's how the sentence looks as a result:

false or (C or not D)

To evaluate the "or" in the remaining parentheses we should first evaluate the "not" operator to find the truth value of the proposition on the right. If "D" is false, then the truth table for "not" tells us that "not D" must evaluate to true. Since "C" is false, the sentence looks like this when "C" and "not D" are replaced by their truth values:

false or (false or true)

The truth table for "or", when applied to values in the remaining parentheses tells us that if one of the propositions is true, then the "or" operation must evaluate to true, giving us:

false or true

Re-using this rule to evaluate the remaining "or" operation gives the result:

true

The only way to solve such logical puzzles is by following the inevitable steps dictated by the rules. That's how logic works!

But why does logic work?

For the same reason why the game of Snap works: we modify our behaviour to follow unambiguous rules because we want to determine the truth of sentences in propositional logic (the aim of playing this sort of logic game). Furthermore, by pretending propositions represent states of affairs in the real world, we can use logic to describe and, in a sense, encode aspects of the real world. For instance, we could describe the rules of Snap with logic.

But why is logic useful?

Because logic clearly and unambiguously describes the relationships between states of affairs (premises), and allows us to take action given a resulting truth value. Consider, for example, this conditional statement: IF the card on top of stack A is an ace AND the card on top of stack B is an ace, THEN shout "SNAP!". Logic describes the movement of thought needed to participate in the card game (or any other useful structured activity).

Here's a final "brain twist" for you:

If Logic provides an inevitable, almost mechanical framework for organising and describing movements of thought then we should be able to build machines to work with such seemingly mechanical logical rules.

It turns out that we can, and describing such machines is the next step in describing why computers work!

Why Computers Work: An Introduction to Following Rules

Why Computers Work (part 1)

(Part 2, part 3, part 4, part 5)

This is the first of five short blog posts exploring why computers work.

I'm going to present a friendly introductory overview for laypeople, from zero to Turing machines, automata, abstraction and more. My aim is conciseness and clarity, so I've necessarily missed out, glossed over and simplified things. There are plenty of more advanced resources online should you wish to investigate this subject further.

Most importantly, I hope to stimulate your thinking about computers by creating a place to explore ideas.

I hope you enjoy these articles and, as always, I love getting constructive feedback via email. Unless otherwise stated, all images and diagrams were created by the author.


αἰὼν παῖς ἐστι παίζων, πεσσεύων· παιδὸς ἡ βασιληίη.

(The universe is a child's game. A child's kingdom.)

~ Heraclitus (Fragment B52)

Introduction

Computers are ubiquitous.

They touch all aspects of our lives, from mediating our social interactions to modelling aspects of our culture and managing the everyday infrastructure of society.

Therefore, computers are interesting and, understandably, folks want to know how the machines that automate and control so much of our world work. This is a typical response.

I'm going to take a different approach.

I'm going to explore why computers work.

What's the difference?

Answers to "how?" questions tell us what method or steps make something happen. In contrast, the answers to "why?" questions describe what makes something possible ~ an opportunity to encounter a more fundamental perspective.

It's the difference between a car mechanic who may understand how an engine works (so they can fix broken engines), and a mechanical engineer who understands the physics and chemistry relating to why engines work (so they can improve the design of engines). Knowing how something works means your frame of reference is within the system, whereas if you understand why something works you're not bound by existing products, solutions or cultural practices.

Most importantly, cultivating an understanding of why something is possible is an invitation for playful creativity, fearless exploration and careful refinement of alternatives to the current crop of answers to "how?". It is an opportunity to enlarge and change our world ~ a form of intellectual empowerment and growth.

Knowing how is good, but understanding why is better.

With the scene suitably set, to start our journey, we'll learn all about...

Following Rules

Do you know how to play the children's card game, Snap?

(Bear with me, I promise it'll be worth it.)

Using a standard deck of cards, the aim is to win all the cards by taking turns to play.

Let's follow along as siblings Penelope (11), Sam (8) and Will (5) play a game:

Penelope (for no other reason than she's the oldest) acts as dealer. She shuffles the deck of cards so they're in a random order and deals them, face down and in equal quantity, to each player until there are none left to deal. This is the starting state from which all games of Snap begin.

Sam, the player to the left of the dealer, takes the first turn.

Players take a turn by moving the top card from their face-down stack onto the top of an adjacent stack of face-up cards, so the newly moved card is also facing up. Since this is Sam's first turn, the face-up stack doesn't exist, so a new stack is created with Sam's first face-up card taken from his pile of face-down cards.

So ends Sam's turn.

A game of Snap!
Source - From WikiHow and licensed under CC BY-NC-SA 3.0

The next player to the left, William, takes his turn in a similar fashion and so the game continues from one player to the next.

After a while Sam shouts "SNAP". He's noticed that two face-up cards on top of different stacks have the same value (for example, two aces are visible on top of Penelope and Will's stacks). Since he was first to shout "SNAP" he wins all the cards in the matching stacks of cards. He gleefully scoops up all the cards in the face-up stacks belonging to Penelope and Will.

Play continues to the left of the player who turned up the matching card.

A few moments later Penelope shouts "SNAP". But there is a problem: there are no matching face-up cards! William points this out to Penelope and reminds her she has to pay a forfeit by giving one card to each of the other players from her face-down stack. Sam and Will get a card each and Penelope is two cards down.

At this point in the game Sam has the most cards. Will and Penelope have less with only a few cards difference between the quantities in their face-down stacks.

Things are hotting up and the three children become more excited: when two matching face-up cards appear again all three of them shout "SNAP" at the same time. Since nobody can claim to have shouted "SNAP" first, and to avoid arguments, both the matching stacks are placed in the middle and added to the "Snap pool". When "SNAP" is next called unambiguously and correctly, the winner will get both the matching stacks and any cards in the "Snap pool". The stakes have suddenly got higher.

Things quieten down for a few rounds until Penelope runs out of face-down cards to put onto her face-up stack. At this point she simply flips over her face-up stack and it becomes her face-down stack. Play continues as before.

Eventually, after a few more calls of "SNAP", Penelope finds that she's run out of cards and so out of the game.

Sam and Will play together until, through luck and fast reactions, Sam finds himself with all the cards and he's declared the winner of the game.

That's how you play Snap..!

The rules illustrated in this deliberately precise story describe how, given certain states of affairs, such-and-such things must happen. States of affairs unambiguously describe how things are in the world. For example, "there are two stacks of face-up cards whose top cards are of matching value". When I describe how such-and-such must happen, I mean clear and unambiguous instructions describe how play proceeds given a certain state of affairs.

Put simply, this is how the game of Snap is played.

But why is Snap played?

Because, in addition to knowing the rules, we understand that playing the game of Snap means modifying one's behaviour to follow these rules. If everyone modifies their behaviour in accordance with the rules then folks can play together. Obviously, we don't explain card games in such a formal manner to very young children. But, as my description shows, children discover it's lots of fun to informally learn and skilfully follow rules that bring about exciting situations in games.

Knowing how to play Snap is analogous to knowing how computers work. Looking beyond the rules of Snap to appreciate that human behaviour and enjoyment motivates people to follow the rules of the game, shows us why Snap is played. This insight may also inspire us to invent new games. Perhaps we become inspired to explore further aspects of human behaviour relating to following rules, or we may even reflect upon the nature of play or games. In any case, exploring why rather than how provides a fascinating perspective from outside the system (of Snap, in this case).

We need to achieve an analogous enlargement of perspective beyond how computers work in order to understand why computers work. Only by acquiring a perspective outside current norms can we possibly hope to invent or improve technology and explore the nature and use of such devices. The alternative is churn and recycling of existing ideas within the current system ~ a situation that stifles innovation or positive change.

The computing-related rules and states of affairs I'm going to describe are not much more complicated than the game of Snap explained above. However, what follows may include a few brain twists where I expect you to use your imagination to see things in a seemingly unusual or unintuitive way! I'm challenging you to acquire a new perspective about seemingly everyday things. The external world remains as it was before, but you will have changed. Your newly acquired perspective reveals a deeper understanding of what you're observing and why this makes computing possible. It's fun and can result in rather pleasant "aha" moments (if you were a cartoon character, it's that feeling you get when a lightbulb appears above your head).

The next chapter in our story is a beautiful brain twist: to think about thinking...