Conjuring with logic: the remote control red-black mind meld

Magic tricks are just algorithms – they involve a magician following the steps of the trick precisely. But how can a magician be sure a trick will definitely work when they do it in front of an audience? Just like computer scientists who can prove their algorithms always work, a magician can use logic and deduction to be sure their tricks always work too.

A mixture of spread red and black playing cards
Image from Pixabay

Try the following trick on your own first, before reading about how it works or trying it with a volunteer. Take the role of both the magician and volunteer. I will do my best to remote-control the magic via my own mind-meld with you as you read my words, to try and make sure it works for you!

The magical effect

Take a full pack of playing cards and give them a good shuffle. Fan the cards face down. Now ask a volunteer to think of the colour RED and point to a card. Cut the pack at that point and count the top eight cards into a pile face down. Now ask them to think BLACK and touch another card. Cut the pack there and count out 7 cards onto the pile. Repeat this with 6 cards and then 5 cards having them think RED and then BLACK. Have the volunteer shuffle the selected cards then turn the pile face up.

4 piles of cards with matching "RED" and "BLACK" piles
Image by Paul Curzon

You take the cards that are left and shuffle them, keeping them face down. Have the volunteer now run through their cards taking out groups of cards that are together and of the same colour. They should put them either in a “RED” pile in front of them if they are a group of red cards, or in a “BLACK” pile if they are black, telling you how many cards they have placed in that pile. As they take each group of cards, you, focussing hard on your cards, but without looking at what they are, pick out the same number of cards from points through the pack as the volunteer put down, and put them in your own corresponding “RED” or “BLACK” pile in front of you, Place your cards face down. In this way, they end up with a pile of red cards and a pile of black cards, both face up in front of them. You end up with two corresponding face down piles in front of you. They have seen their cards but yours contain cards that you have not seen. Once they have run out of cards and you have placed your matching cards, stop and think for a moment, then go through your two piles and swap two cards without looking at them, saying you believe you made a couple of mistakes and those two ended up in the wrong piles.

Now, looking happy, tell the volunteer that through a mind-meld between you, them and the red and black cards you have, you believe, succeeded in your aim. Remind them that the piles were shuffled, they were responsible for the way the cards were split which was at random, and you haven’t seen any of your cards. One card out at any point and the trick would not have worked. Despite this, announce that you have managed to place the same number of red cards in your red pile as you have placed black cards in your black pile. Pass them the two piles in turn and ask them to check by first counting the red cards in your face down “RED” pile onto the table, and then do the same with the black cards that are in your “BLACK” pile.

Amazingly you have succeeded, the number of red cards in the red pile is the same as the number of black cards in the black pile.

Proving it always works

Did I mind meld with you to make it work? Or is something else going on? We can actually use logic and deduction (with some algebra) to show it works.

First we need to make a mathematical model of the situation – essentially describe the situation, or at least the parts of it that matter, in maths. That sounds a bit scary but it isn’t really. Its just giving names to some piles of cards! Let’s go through it…

In the trick, we end up with four piles of cards. A RED pile and a BLACK pile, both face up, in front of the volunteer and a RED pile and a BLACK pile, both face down, in front of the magician (see the picture above). We do not know how many cards are in each pile and it will be different each time we do the trick anyway because of all the shuffling. Luckily the actual numbers don’t matter. In the trick we care about the numbers of red cards and the numbers of black cards, Let us therefore use mathematical variables to represent these different numbers (that just means give them names!). Mathematicians often use names like x and y for variables, but to help us remember what they stand for we will use variations on R and B to mean numbers of red and black cards respectively.

So, we will use R to stand for the number of red cards in the volunteer’s face up “RED” pile (which are all red) and B to mean the number of black cards in the volunteers face up “BLACK” pile (which are all black).

Now for the magician’s face down piles. They have both red and black cards in each pile so we will write R1 to mean the number of red cards in the magician’s face down “RED” pile and B1 to mean the number of black cards in the magician’s face down “RED” pile. Similarly, we will write R2 to mean the number of red cards in the magician’s face down “BLACK” pile and B2 to mean the number of black cards in the magician’s face down “BLACK” pile. We have the situation as shown below in the picture..

4 piles of cards showing them labelled with variables R, B, B1, R1, R2 and B2

Image by Paul Curzon

In doing this we are doing a form of abstraction – hiding of detail – we have hidden the actual numbers of red and black cards in each pile within our description, describing them with variables as the precise numbers do not matter (and are different every time we do the trick anyway).

So far so good. Now, we want to try and prove that the trick always works. But how to start? First, just think of any facts you know about the situation (and especially anything you know about red and black cards). It may not be obvious how it can help, but write it down anyway!

Well the first thing we know is that a full pack of cards was used, and there are 52 cards in a pack, half (26) red and half (26) black. All these cards ended up on the table in one pile or another. So that means if we add up all the red cards in the four piles it will equal 26. How can we write this in terms of our variables? It is just:

R + R1 + R2 = 26

We add the three variables that stand for numbers of red cards and it equals 26. There are only three things to add for the four piles as one pile is all black. We can say a similar thing about the black cards:

B + B1 + B2 = 26

Now we have two different sums that equal the same thing (26) so we can put them together as equalling each other to get a combined equation which we will call EQUATION 1.

R + R1 + R2 = B + B1 + B2                                         (EQUATION 1)

That doesn’t seem to tell us much useful, but don’t worry, we are just gathering facts for now. What else do we know about how the trick worked? Well, every time the volunteer put some number of cards in their “RED” pile, the magician puts the same number of cards in their “RED” pile (though those cards may be red or black). That means that, throughout the two “RED” piles hold the same number of cards. The number of cards in one “RED” pile is R and the number of cards in the other “RED” pile is R1 + B1 (the reds plus the blacks in that pile). We can write this out as an equation:

R = R1 + B1

Now, this tells us that R is exactly the same as R1 + B1 so anywhere we see R we can replace it with R1 + B1. In particular, we can make this switch in EQUATION 1 to give:

(R1 + B1) + R1 + R2 = B + B1 + B2                                (EQUATION 2)

With the same logical reasoning, we can deduce an equation for the “BLACK” piles too. The number of cards in one “BLACK” pile is B and the number of cards in the other “BLACK” pile is R2 + B2 (the reds plus the blacks in that pile). We can write this out as an equation:

B = R2 + B2

Substituting R2 + B2 for B into EQUATION 2 we get EQUATION 3

(R1 + B1) + R1 + R2 = (R2 + B2) + B1 + B2                     (EQUATION 3)

Now, this seems to have just made things more complicated and not got us anywhere much, but we can now simplify it. Notice that there are two R1s on one side and two B2s on the other, each added, so we can group them together to get:

2R1 + B1 + R2 = R2 + 2B2 + B1

Also, on each side there is a B1 and that pair can cancel out (just subtract B1 from both sides and the equality holds but it is simpler), and on each side there is an R2 which can cancel in the same way. This leaves us with:

2R1 = 2B2

Of course the multiplication by 2 on both sides cancels too (just divide both sides by 2 and they will still be equal). We get:

R1 = B2

That is a very simple equation. It basically tells us that if you follow the steps of this trick that, whatever numbers of reds and blacks end up in each pile, R1 is guaranteed at the end to be the same number as B2. So what does that mean back in the real world? R1 just stands for the number of red cards in the magician’s “RED” pile. B2 just stands for the number of black cards in the magician’s “BLACK” pile. The equation we are left with just tells us that as long as we follow the steps (actually as long as we make the number of cards in each pair of piles match) then at the end the number of red cards in the magician’s “RED” pile will be the same as the number of black cards in the magician’s “BLACK” pile…and that is the “magical” result we predicted!

The trick will always work if you follow the steps!

Proving software and hardware always works

A magic trick involves the magician following steps precisely – following an algorithm. That is all computer hardware and software do – they follow algorithms to achieve some desired result (a magical effect). Just as we proved the trick always works, we can prove that other algorithms (whether implemented as a program or hardware) work using logical deduction too. That is one of the reasons why logic and deduction are so important to computer scientists. You do not want a trick to go wrong in front of an audience, so it is worth proving it always works. How much more important is it that all that software we now rely on for everyday life is error free. And what about a medical device keeping someone alive, or the software flying a plane. We want to be sure they always work. If they contain mistakes, people die. Logic and proof can therefore save lives, not just magic shows.

by Paul Curzon, Queen Mary University of London

More on …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

EPSRC supports this blog through research grant EP/W033615/1. 

Adrian Stokes: Internet pioneer

An abstract schematic of the UK part of the ARPANET. RAL and others connect to UCL which connects to the US via Norway.
Image by Paul Curzon

We take the Internet for granted now, but it is not that long ago that it did not exist at all. Disabled from birth with spina bifida, Adrian Stokes, OBE was one of the people who helped build it: a celebrated “Internet pioneer”. He was, for example, responsible for setting up the first email service in the UK and so the first transatlantic email system, as well as providing the service linking other universities in the UK to the network making it work as a network of networks in different countries.

He worked on ARPANET, the precursor to the Internet. It was a research project funded by the US department of defence exploring the future of communication networks. Up to that point there were global networks but they were based on what is called circuit switching. Think of an old fashioned telephone exchange, Each person had a direct line – an electrical circuit – connecting them to the operator. When you talked to the operator and asked to talk to someone over the phone, the operator would plug a wire that connected your line to theirs, making a new direct circuit from you to them. When you talked, your voice was converted to an analogue signal (a changing electrical signal) which passed down that wire – along the circuit. Transatlantic telephone cables even allowed circuits, so phone calls, to be set up between countries. Early computers connected to each other, sending data over phone lines in this way by converting them into sounds.

ARPANET worked differently to a circuit-based system. It was a packet switched network. It worked by treating data sent over a network as binary, just as the computer itself does internally. This contrasted with the analogue system then used to send sound over early phones. Importantly, the binary data being sent was divided up into fixed size groups of bits called packets. Each packet was then sent separately over the network. In this system there is no fixed circuit from source to destination that the data travels down, just lots of different computers connected to each other, On receiving packets of data each computer or node of the network passes it on to another until eventually it arrives at the target computer. A key advantage to this is that each of those packets can go by a different route, travelling between different computers. They can even arrive out of order, The data no longer travels along a single circuit. The packets are put back together (in the right order) on reaching the destination, reconstructing the original so that the fact it was ever split up is invisible to the person receiving the data. Extra information is added to the packets beyond the actual data to make the system work: such as a destination address to indicate where it is going to and the number of the packet so the order can be reconstructed if they do arrive out of order. Managing the packets and their journey to the destination is done by software implementing a protocol (a set of communication rules agreed between the computers on the network, that allows them to interpret the streams of bits arriving from other computers).

So ARPANET consisted of a series of computers that acted as nodes of the network. Each had to be programmed with software to run the protocol, passing packets on in their journey to the destination and pulling the original data out and reconstructing it if that computer was their destination. UCL were working with the ARPANET team, exploring how to make it work across continents, so had to program one of their computers to make it an ARPANET node. Once done it could connect to the ARPANET via a satellite link in Norway.

At first, the ARPANET was set up as a way just to access data on other computers as though it was on your own local computer. However, other services could be provided on top of the basic protocols. It just amounts to writing code for your node’s computer to turn data into packets and interpret the data in packets arriving in the way needed for the new application. For example, a way to access files on other computers as though they were on yours were added. Much, much later of course code to allow communication through a web page service was written and the world wide web was born to sit on top of the Internet.

This was one of the jobs Adrian Stokes did. He wrote code for the UCL computers that could treat packets of data as email messages rather than just files. Users could write messages and send them to people on other computers on ARPANET without them needing to know where they actually were. It was the first UK email service.

Once UCL had a link to the ARPANET, they could also extend ARPANET. One of Adrian’s other jobs was in managing onward links around the UK, creating a UK ARPANET network. Researchers in other UK universities could set up their own computers as ARPANET nodes (write and run the software on their computer) and then connect their computers to the UCL one. Networks their computers were linked to could then also connect to the ARPANET. In doing so they created a UK ARPANET network but one that was also connected to the full ARPANET via the UCL computer. It meant, for example, that anyone on the ARPANET in the US could (with permission as UCL added password protection to their node – the first on the ARPANET!) access the powerful IBM System 360/195 computer at the Rutherford and Appleton Labs in Oxfordshire. ARPANET became a transatlantic network of connected networks. Any of those UK universities could also then connect to any computer anywhere on the ARPANET. Their packets just went to the UCL one and then to the US via the satellite link, before being forwarded onwards to other US computers. If these UK university computers had the programs for the file transfer or email services, for example, then they could seamlessly use them to access files anywhere else or send messages to anyone else connected to the ARPANET anywhere.

ARPANET ultimately turned into what we now call the Internet. No single person invented the Internet, it was a massive team effort with lots of people involved each responsible for getting some part of it to work. Those like Adrian who played a critical part in making it work, however, have been recognised as “Internet pioneers”: those who can justifiably claim they were part of the team that invented the Internet, and transformed all our lives as a result.

– Paul Curzon, Queen Mary University of London

More on …

Magazines …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

Herman Hollerith: from punch cards to a special company

Herman Hollerith
Herman Hollerith (Image from wikimedia, Public Domain)

Herman Hollerith, the son of immigrants, struggled early on at school and then later in bookkeeping at college but it didn’t stop him inventing machines that used punch cards to store data. He founded a company to make and sell his machines. It turned into the company now called IBM, which of course helped propel us into the computer age.

Hollerith had worked as a census clerk for a while, and the experience led to his innovation. The United States has been running a national census every 10 years since the American Revolution, aiming to record the details of every person, for tax and national planning purposes. It is not just a count but has recorded information about each person such as male/female, married or not, ethnicity, whether they can read, disabilities, and so on.

As the population expanded it of course became harder to do. It was also made harder as more data about each person was being collected over time. For the 1890 census a competition was held to try and find better ways to compile the data collected. Herman Holerith won it with his punch card based machine. It could process data up to twice as fast as his competitors and with his system data could be prepared 10 times faster.

To use the machine, the census information for each person was recorded by punching holes in special cards at specific positions. It was a binary system with a hole essentially meaning the specific feature was present (eg they were married) and no hole meaning it wasn’t (eg they were single). Holes against numbers could also mean one of several options.

Hollerith punched card from wikimedia
Hollerith punched card (Image from wikimedia, Public Domain)

The machine could read the holes because they allowed a wire to make an electrical connection to a pool of mercury below so the holes just acted as switches. Data could therefore be counted automatically, with each hole adding one to a different counter. It was the first time that a system of machine-readable data had been used and of course binary went on to be the way all computers store information. In processing the census his machines counted the data on around 100 million cards (an early example of Big Data processing!). This contributed to reducing the time it took to compile the data from the whole country by two years. It also saved about $5 million

Holerith patented the machine and was also awarded a PhD for his work on it. He set up a company to sell it called the Tabulating Machine Company. Over time it merged with other companies until eventually in 1924 the resulting company changed its name to International Business Machines or is it is now known, IBM. it is of course one of the most important companies driving the computer age, building early mainframe computers the size of rooms that revolutionised business computing, but later also responsible for the personal computer, leading to the idea that everyone could own a computer.

Not a bad entrepreneurship legacy for someone who early on at school apparently struggled with, and certainly hated, spelling – he jumped out of a window at school to avoid doing it. He also did badly at bookkeeping in college. He was undeterred by what he was poor at though and focussed on what he was good at, He was hard working and developed his idea for a mechanical tabulating machine for 8 years before his first machine went to work. Patience and determination was certainly a strength that paid off for him!

More on …

Magazines …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

EPSRC supports this blog through research grant EP/W033615/1. 

A handshaking puzzle

By Przemysław Wałęga, Queen Mary University of London

Logical reasoning and proof, whether done using math notation or informally in your head, is an important tool of computer scientists. The idea of proving, however, is often daunting for beginners and it takes a lot of practice to master this skill. Here we look at a simple puzzle to get you started.

Two art models shaking hands
Image by GU LA from Pixabay

Computer Scientists use logical reasoning and proofs a lot. They can be used to ensure correctness of algorithms. Researchers doing theoretical computer science use proofs all the time, working out theories about computation.

Proving mathematical statements can be very challenging, though. Coming up with a proof often requires making observations about a problem and exploiting a variety of different proof methods. Making sure that the proof is correct, concise, and easy to follow matters too, but that in itself needs skill and a lot of practice. As a result, proving can be seen as a real art of mathematics.

Let’s think about a simple puzzle to show how logical thinking can be used when solving a problem. The puzzle can be solved without knowing any specific maths, so anyone can attempt it, but it will probably look very hard to start with.

Before you start working on it though, let me recommend that first you try to solve it entirely in your mind, that is, with no pen and paper (and definitely no computer!). 

The Puzzle

Here is the puzzle, which I heard at a New Year’s party from a friend Marcin:

Mrs. and Mr. Taylor hosted a party and invited four other couples. After the party, everyone gathered in the hallway to say their goodbyes with handshakes. No one shook hands with themselves (of course!) or their partner, and no one shook hands with the same person more than once. Each person kept track of how many people they had shaken hands with. At one point, Mr. Taylor shouted “STOP” and asked everyone to say how many people they had shaken hands with. He received nine different answers. 

How many people did Mrs Taylor shake hands with?

I will give you some hints to help solving the puzzle, but first try to solve it on you own, and see how far you get. Maybe you will be solve the puzzle on your own? 

Why did I recommend solving the puzzle without pen and paper? Because, our goal is to use logical and critical thinking instead of finding a solution in a “brute force” manner, that is, blindly listing all the possibilities and checking each of them to find a solution to the puzzle. As an example of a brute force way of solving a problem, take a crossword puzzle where you have all but one of the letters of a word. You have no idea what the clue is about, so instead you just try the 26 possible letters for the missing one and see which make a word and then check which that do fit the clue! 

Notice that the setting of our puzzle is finite: there are 10 people shaking hands, so the number of ways they shake hands is also finite if bigger than say checking 26 different letters of the crossword problem. That means you could potentially list all the possible ways people might shake hands to solve the puzzle. This is, however, not what we are aiming for. We would like to solve the puzzle by analysing the structure of the problem instead of performing brute force computation. 

Also, it is important to realise that often mathematicians solve puzzles (or prove theorems) about situations in which the number of possibilities is infinite so the brute force approach of listing them all is not possible at all. There are also many situations where the brute force approach is applicable in theory, but in practice it would require considering too many cases: so many that even the most powerful computers would not be able to provide us with an answer in our lifetimes. 

Handshake
Image by Robert Owen-Wahl from Pixabay

For our puzzle, you may be tempted to list all possible handshake situations between 10 people. Before you do start listing them, let’s check how much time you would need for that.  You have to consider every pair that can be formed from 10 people. A mathematician refers to that as “10 choose 2”, the answer to which is that there are 45 possible pairs among 10 people (the first person pairs with 9 others, the next has 8 others to pair with having been paired with the first already, and so on and 9+8+….+1 = 45). However, 45 is not the number that we are looking for. Each of these pairs can either shake hands or not, and we need to consider all those different possibilities. There are 245 such handshake combinations. How big is this number? The number 210 is 1024, so it is approximately 1000. Hence 240=(210)4 (which is clearly smaller than our 245) is approximately 10004 = 1,000,000,000,000 that is, a trillion. Listing a trillion combinations should sound scary to you. Indeed, if you can be quick enough to write each of the trillion combinations in one second, you will spend 31 688 years. Let’s not try this!

Of course, we can look more closely at the description of the puzzle to decrease the number of combinations. For example, we know that nobody shakes hands with their partner, which will already massively reduce the number. However, let’s try to solve the puzzle without using any external memory aids or computational power. Only our minds.

Can you solve it? A key trick that mathematicians and computer scientists use is to break down problems into simpler problems first (decomposition). You may not be able to solve this puzzle straight away, so instead think about what facts you can deduce about the situation instead.

If you need help, start by considering Hint 1 below. If you are still stuck, maybe Hint 2 will help? Answer these questions and you will be a long way to solving the puzzle.

Hints

  1. Mr. Taylor received nine different answers. What are these answers?
  2. Knowing the numbers above, can you work out who is a partner of whom?

No luck in solving the puzzle? Try to spend some more time before giving up!  Then read on. If you managed to solve it you can compare your way of thinking with the full solution below.

Solution

First we will answer Hint 1. We can show that the answers received by Mr. Taylor are 0, 1, 2, 3, 4, 5, 6, 7, and 8. There are 5 couples, meaning that there are 10 people at the party (Mr. and Mrs. Taylor + 4 other couples). Each person can shake hands with at least 0 people and at most 8 other people (since there are 10 people, and they cannot shake hands with themselves or their partner). Since Mr. Taylor received nine different answers from the other 9 people, they need to be 0, 1, 2, 3, 4, 5, 6, 7, and 8. This is an important observation which we will use in the second part of the solution.

Next, we will answer Hint 2. Let’s call P0 the person who answered 0, P1 the person who answered 1, …, P8 the person who answered 8. The person with the highest (or the lowest) number of handshakes is a good one to look at first.

  • Who is the partner of P8? P8 did not shake hands with themselves and with P0 (as P0 did not shake hands with anybody). So P8 had to shake hands with all the other 8 people. Since no one shakes hands with their partner, it follows that P0 is the partner of P8!
  • Who is the partner of P7? They did not shake hands with themselves, with P0 and with P1, because we already know that P1 shook hands with P8, and they shook hands with only one person. So the partner of P7 can be either P8, P0, or P1. Since P8 and P0 are partners, P7 needs to be the partner of P1.
  • Following through with this analysis for P6 and P5, we can show that the following are partners: P8 and P0, P7 and P1, P6 and P2, P5 and P3. The only person among P0, … , P8 who is left without a partner is P4. So P4 needs to be Mrs. Taylor, the partner of Mr. Taylor, the one person left who didn’t give a number. 

Consequently, we have also showed that Mr Taylor shook hands with 4 people. 

Observe that the analysis above does not only provide us an answer to the puzzle, but it also allows us to uniquely determine the handshake setting as presented in the picture below (called a graph by Computer Scientists). Here, people are nodes (circles) and handshakes are represented as edges (lines) in the graph. Red edges correspond to handshakes with P8, blue edges are handshakes with P7, green with P6 and yellow with P5. Partners are located next to each other, for example, Mr. Taylor is a partner with P4.

Image by CS4FN

Large Language Models

Although this article is about logical thinking, and not about tools to solve logic puzzles, it is interesting to see if current AI models are capable of solving the puzzle. As puzzles go it is relatively easy and occurs on the Internet in different settings and languages, so large language models (LLMs) trained on the Internet should be good at solving it. Let’s test them!

I asked ChatGPT-4o and Gemini 1.5 Flash to solve the puzzle. To my surprise, both of them did struggle. They had problems with understanding some parts of the problem formulation and made mathematical mistakes. 

  • ChatGPT seems to wrongly assume that Mr. Taylor answered his own question about the number of handshakes, and so, that each of 10 people announced a different number of handshakes. As follows from our solution of the puzzle, there exists exactly one graph representing the handshake situation. In this graph, the number of handshakes of Mr. and Mrs. Taylor is the same, namely 4. Hence, the additional assumption made by ChatGPT (that each of 10 people had a different number of handshakes) makes the situation described in the puzzle impossible. Interestingly, ChatGPT was able to solve such an impossible puzzle providing a correct answer… Does it mean that ChatGPT has solved the puzzle?
  • Gemini, in contrast, states that the puzzle cannot be solved without more information such as the order of arrivals. This is clearly wrong. We know how to solve the puzzle and the order of arrivals is actually completely irrelevant to the puzzle! 

This small experiment uses basic LLMs and does not aim to draw any conclusions about their capabilities. I am quite certain that one can find an LLM that can solve this simple puzzle without mistakes. However, this experiment aims to emphasise the need for checking AI solutions yourself. To do that you need to gain the skills of doing proof yourself!

In what follows I provide answers obtained from AI models and highlight as bold parts which are wrong assumptions or reasoning.

Solution by ChatGPT:

Key Observations:

  1. There are 10 people in total at the party (5 couples: Mr. and Mrs. Taylor and 4 other couples).
  2. No one shakes hands with their own partner.
  3. No one shakes hands with themselves or the same person more than once.
  4. The handshake answers must be unique and range from 0 to 9 (since there are 10 people, including Mr. and Mrs. Taylor).

Solution:

  • Since there are 10 people total, the number of handshakes any one person could have ranges from 0 to 9.
  • If everyone gives a unique answer, it means:
    • One person shook hands with 0 people.
    • Another shook hands with 1 person.
    • Another with 2, and so on, up to 9.

Steps:

  1. The person who shook hands with 9 people: This person shook hands with everyone else, meaning their partner (who doesn’t shake hands with them) must have shaken hands with 0 people.
  2. The person who shook hands with 8 people: This person shook hands with everyone except their partner and the person who shook hands with 0.
  3. By continuing this pattern, we see that for every unique count of handshakes k, the person with k handshakes corresponds to a partner with 9−k handshakes.

Mrs. Taylor’s Handshakes:

  • Mr. Taylor shouted “STOP” after collecting answers from all 10 people. Since there are 9 different handshake counts, one of those counts must belong to Mrs. Taylor.
  • Let’s assume Mr. Taylor is among the group and is the one with the maximum or minimum handshakes.
  • The pairing pattern ensures Mrs. Taylor’s number of handshakes must fall within the range, but based on symmetry of couples logic !

The key is to match couples symmetrically:

If Mr. Taylor gets answers (0, 1, 2,…

Let’s refine the solution:

  • The possible handshake counts are 0,1,2,…,9, ensuring each number is unique.
  • The pairing works such that if one person shakes k hands, their partner shakes 9-k hands.

This logic means:

  • The person who shook 9 hands paired with the person who shook 0.
  • The person who shook 8 hands paired with the person who shook 1, and so on.

Mrs. Taylor’s Count:

If there are nine unique handshake counts (from 0 to 9), Mrs. Taylor must have shaken 4 hands because her partner, Mr. Taylor, who controls the setup, must fall at the midpoint to allow symmetrical pairing logic.

Solution by Gemini:

Certainly, let’s solve the handshake puzzle!

Understanding the Problem:

  • We have 10 people at the party (Mr. and Mrs. Taylor, plus 4 other couples).
  • No one shakes hands with themselves or their partner.
  • No one shakes hands with the same person more than once.
  • Each person keeps track of how many handshakes they’ve done.
  • Mr. Taylor asks everyone how many handshakes they’ve done, and gets 9 different answers.
  • We need to figure out how many handshakes Mrs. Taylor did.

Let’s Analyze:

The key to solving this is to consider the possible range of handshakes each person could have.

  • Lowest Possible Handshakes: If someone is the first to arrive and doesn’t shake hands with anyone else, they’ll have 0 handshakes.
  • Highest Possible Handshakes: The maximum number of handshakes depends on the order of arrivals and who shakes hands with whom. In the most efficient scenario, everyone could shake hands with everyone else except their partner. This would lead to a maximum of 8 handshakes for each person.

Now, let’s consider the 9 different answers:

Since there are 9 different answers, and the minimum is 0, the maximum number of handshakes someone could have is 8.

Let’s think about Mrs. Taylor:

  • She can’t have 0 handshakes because she would have to shake hands with someone eventually.
  • She can’t have 8 handshakes because Mr. Taylor would have to have the same number (since they are the only couple).

Therefore, Mrs. Taylor must have shaken hands with a number between 1 and 7.

Unfortunately, without more information about the order of arrivals and who shook hands with whom, we can’t pinpoint the exact number of handshakes Mrs. Taylor did.

Let me know if you’d like to explore a specific scenario with a particular order of arrivals and handshakes to determine Mrs. Taylor’s exact number!

More on …

Related Magazines …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by UKRI, through grant EP/W033615/1.

Tanaka Atsuko: an electric dress

Wearable computing is now increasingly common whether wearing smart watches or clothes that light up. The pioneer of the latter was Japanese artist, Tanaka Atsuko, with her 1950s art work, Electric Dress. It was anything but light though, weighing 50-60kg, clothing her head to foot in a mixture of fluorescent and normal light bulbs.

Light reflecting from strip bulbs in a light bulb
Image by wal_172619 from Pixabay

She was a member of the influential Gutai (meaning concrete as opposed to abstract) Art Association and Zero Society of Japanese artists who pioneered highly experimental performance and conceptual art, that often included the artist’s actual body. The Electric Dress was an example of this, and she experimented with combining art and electronics in other work too.

Atsuko had studied dress-making as well as art, and did dress making as a hobby, so fashion was perhaps a likely way for her to express her artistic ideas, but Electric Dress was much more than just fashion as a medium for art. She had the idea of the dress when surrounded by the fluorescent lights in Osaka city centre. She set about designing and making the dress and ultimately walked around the gallery wearing it when it was exhibited at the 2nd Gutai Art Exhibition in Tokyo. Once on it flashed the lights randomly, bathing her in multicoloured light. Wearing it was potentially dangerous. It was incredibly hot and the light was dazzling. There was also a risk of electrocution if anything went wrong! She is quoted as saying after wearing it: “I had the fleeting thought: Is this how a death-row inmate would feel?”

It wasn’t the first time, electric lights had been worn, since as early as 1884 you could hire women, wearing lights on their heads powered by batteries hidden in their clothes, to light up a cocktail party, for example. However, Tanaka Atsuko’s was certainly the most extreme and influential version of a light dress, and shows how art and artists can inspire new ideas in technology. Up to then, what constituted wearable computing was more about watch like gadgets than adding electronics or computing to clothes.

Now, of course, with LEDs, and conductive thread that can be sewn into clothes and special micro-controllers, an electric dress is both much easier to make, and with programming skill you can program the lights in all sorts of creative ways. One example is a dress created for a BBC educational special of Strictly Come Dancing promoting the BBC micro:bit and showing what it was capable of with creativity. Worn by professional dancer, Karen Hauer, in a special dance to show it off, the micro:bit’s accelerometer was used to control the way the LEDs covering the dress in place of sequins, lit up in patterns. The faster she spun while dancing the more furious the patterns of the lights flashing.

Now you can easily buy kits to create your own computer-controlled clothes with online guides to get you started, so if interested in fashion and computer science why not start experimenting. Unlike Tanaka Atsuko you won’t have to put your life at risk for your art and wearable computing, overlapping with soft robotics is now a major research area, so it could be the start of a great research career.

by Paul Curzon, Queen Mary University of London

More on …

Related Magazines …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by UKRI, through grant EP/W033615/1.

Electric Dreams and Solid Light at the Tate Modern

Two crossing lines of light (after McCall)
Image by CS4FN (after McCall)

Two current exhibitions at the Tate Modern in London that those interesting in technology and art may want to see are “Electric Dreams: Art and Technology before the Internet”, and Anthony McCall’s truly wonderful “Solid Light”. Both run for the next few months in 2025.

Electric Dreams covers artists use of machines to create art over the second half of the 20th century, covering a wide range of styles and ideas often involving light and motion in thought-provoking ways. The exhibition ranges from the early wearable art of Atsuko Tanaka – a 1956 Electric Dress that coated the wearer in lights (before the age of LEDs so it was a weighty 60 kg) through the first computer choreography of dance; Hirosho Karano’s program that painted like Mondrian; the Art of Harold Cohen’s program Aaron, the first AI artist creating physical art, to Rebecca Allen’s early use of motion capture in art from 1982 and beyond.

While there you should visit Anthony McCall’s Solid Light exhibition. Using just 35 mm film projected in dark smoky rooms he creates an amazing immersive experience that is fun for toddlers and adults alike. It consists of changing sculptures made of slowly moving, curved walls of light that the viewer walks, around, in and through. Sit and watch or interact yourself and become part of the art. It is playful, awe-inspiring and thought-provoking all at once. Exactly what I think the best art should be.

If you want a first experience of an art gallery for a three-year old then you would struggle to do better than a visit to the Tate Modern. Start with Solid Light, followed by visiting the room in Electric Dreams containing Carlos Cruz-Diez’s work where you play with large white balloons in a space full of continuously moving lines of light.

If you thought that machines were replacing artists then think again. The best artists may be using technology, but they go way beyond anything technology itself can do alone and I imagine will be for a long time to come. Combine Computer Science or Electronic Engineering with Creative, Media Art skills, and perhaps you could be one of the future pioneer artists using the new technology of the future in exciting ways.

– Paul Curzon, Queen Mary University of London

More on …

Related Magazines …

Our Books …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

EPSRC supports this blog through research grant EP/W033615/1. 

QMUL CS4FN EPSRC logos

My first signs

Alexander Graham Bell was inspired by the deafness of his mother to develop new technologies to help. Lila Harrar, then a computer science student at Queen Mary, University of London was also inspired by a deaf person to do something to make a difference. Her chance came when she had to think of something to do for her undergraduate project.

Sign language relief sculpture on a stone wall: "Life is beautiful, be happy and love each other", by Czech sculptor Zuzana Čížková on Holečkova Street in Prague-Smíchov, by a school for the deaf
Sign language relief sculpture on a stone wall: “Life is beautiful, be happy and love each other”, by Czech sculptor Zuzana Čížková on Holečkova Street in Prague–Smíchov, by a school for the deaf
Image (cropped) ŠJů, Wikimedia Commons, CC BY-SA 3.0 https://creativecommons.org/licenses/by-sa/3.0, via Wikimedia Commons

Her inspiration came from working with a deaf colleague in a part-time job on the shop floor at Harrods. The colleague often struggled to communicate to customers so Lila decided to do something to encourage hearing as well as deaf people to learn Sign Language. She developed an interactive tutor program that teaches both deaf and non-deaf users Sign Language. Her software included games and quizzes along with the learning sections- and she caught the attention of the company Microbooks. They were so impressed that they decided to commercialise it. As Lila discovered you need both creativity and logical thinking skills to do well at Computer Science – with both, together with a bit of business savvy, perhaps you could become the country’s next great innovator.

– Peter W. McOwan and Paul Curzon, Queen Mary University of London

More on …

Magazines …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

EPSRC supports this blog through research grant EP/W033615/1. 

QMUL CS4FN EPSRC logos

Join the crowd with swarm intelligence

A shoal of fish crammed into a cylindrical tank.
Image by Paul Sloane from Pixabay

Next time you are in a large crowd, look around you: all those people moving together, and mostly not bumping into each other. How does it happen? Flocks of birds and schools of fish are also examples of this ‘swarm intelligence’. Computer Scientists have been inspired by this behaviour to come up with new solutions to really difficult problems.

Swarming behaviour requires the individuals (birds, fish or people) to have a set of rules about how to interact with the individuals nearest to them. These so-called ‘local’ rules are all that’s needed to give rise to the overall or ‘global’ behaviour of the swarm. We adjust our individual behaviour according to our current state but also the current state of those around us. If I want to turn left then I do it slowly so that others in the crowd can be aware of it and also start to turn. I know what I am doing and I know what they are doing. This is how information makes its way from the edges of the crowd to the centre and vice versa.

A swarm is born

The way a crowd or swarm interacts can be explained with simple maths. This maths is a way of approximating the complex psychological behaviour of all the individuals on the basis of local and global rules. Back in 1995 James Kennedy, a research psychologist, and Computer Scientist Russ Eberhart, having been inspired by the study of bird flocking behaviour by biologist Frank Heppner, realised that this swarm intelligence could be used to solve difficult computer problems. The result was a technique called Particle Swarm Optimisation (PSO).

Travel broadens the mind

An optimisation problem is one where you have a range of options to choose from and you want to know the best solution. One of the classic problems is called ‘The travelling salesperson’ problem. You work for a company and have to deliver packages to say 12 towns. You look at the map. There are many different routes to take, but which is the one that will let you visit all 12 towns using the least petrol? Here the choices are the order in which you visit the towns, and the constraint is that you want to do the least driving. You could have a guess, select the towns in a random order and work out how far you’d have to travel to visit them in this order. You then try another route through all 12 and see if it takes less mileage, and so on. Phew! It could take a long time to work out all the possible routes for 12 towns to see which was best. Now imagine your company grows and you have to deliver to 120 towns or 1200 towns. You would spend all your time with the maps trying to come up with the cheapest solutions. There must be a better way? Well actually simple as this problem seems it’s an example of a set of computational problems known as NP-Complete problems and it’s not easy to solve! You need some guidance to help you through and that’s where swarm optimisation come in. It’s an example of a so-called metaheuristic algorithm: a sort of ‘general rule of thumb’ to help solve these types of problem. It won’t always work unless you have infinite time but it’s better than just trying random solutions. So how does swarm optimisation work here?

State space: the final frontier

First we need to turn the problem into something called a state space. You probably use state spaces all the time but just don’t know it. Think about yourself. What are the characteristic you would use to tell people about your current state: age, height, weight and so on. You can identify yourself by a list of say 3 numbers – one for age, one for height, one for weight. It’s not everything about you of course but it does define your state to some extent. Your numbers will be different to other people’s numbers, if you take all the numbers for your friends you would have a state space. It would be a 3-dimensional space with axes: age, height and weight, and each person would be a point in that space at some coordinate (X, Y, Z).

So state spaces are just a way of representing the possible variations in some problem. With the 12 towns problem, however, you couldn’t draw this space: it would be 12 dimensional! It would have one axis for each town, with the position on the axis an indication of where in the route it was. Every point in that space would be a different route through the 12 towns, so each point in the space would have coordinates (x1, x2, x3, … x11, x12). For each point there would also be a mileage associated with the route, and the task is to find the coordinate point (route) with the lowest mileage.

Where no particle has swarmed before

Enter swarm optimisation. We create a set of ‘particles’ that will be like birds or fish, and will fly and swarm through our state space. Each particle starts with a random starting location in the state space and calculates the mileages involved for the coordinates (route) they are at. The particles remember (store) this coordinate and also the value of the mileage at that position. Each particle therefore has it’s own known ‘local’ best value (where the lowest mileage was) but can compare this with other neighbouring particles to see if they have found any even better solutions. The particles then move onwards randomly in a direction that tends to move them towards their own local best and the best value found by their neighbours. The particles ‘fly’ around the state space in a swarm homing in on even better solutions until they all converge on the best they can find: the answer.

It may be that somewhere in a part of the space where no particle has been there is an even better solution, perhaps even the best solution possible. Our swarm will have missed it! That’s why this algorithm is a heuristic, a best guess to a tough problem. We can always add some more particles at the start to fill more of the state space and reduce the chance of missing a good solution, but we cant ever be 100% sure.

Swarm optimisation has been applied to a whole range of tough problems in computing, electronic engineering, medicinal chemistry and economics. All it needs is for you to create an appropriate state space for your problem and let the particles fly and swarm to a good solution.

It’s yet another example of clever computing based on behaviours found in the natural world. So next time you’re in a crowd, look around and appreciate all that collective interacting swarm intelligence…but make sure you remember to watch where you are stepping.

by Peter W. McOwan, Queen Mary University of London. From the archive.

More on …

Related Magazines …

cs4fn issue 4 cover
A hoverfly on a leaf

Our Books …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

Nemisindo: breaking the sound barrier

Womens feet walking on a path
Image by ashokorg0 from Pixabay

Games are becoming ever more realistic. Now, thanks to the work of Joshua Reiss’s research team and their spinout company, Nemisindo, it’s not just the graphics that are amazing, the sound effects can be too.

There has been a massive focus over the years in improving the graphics in games. We’ve come along way from Pong and its square ball and rectangular paddles. Year after year, decades after decade, new algorithms, new chips and new techniques have been invented that combined with the capabilities of ever faster computers, have meant that we now have games with realistic, real-time graphics immersing us in the action as we play. And yet games are a multimedia experience and realistic sounds matter too if the worlds are to be truly immersive. For decades film crews have included whole teams of Foley editors whose job is to create realistic everyday sounds (check out the credits next time you watch a film!). Whether the sound is of someone walking on a wooden floor in bare feet, walking on a crunchy path,opening thick, plush curtains, or an armoured knight clanging their way down a bare, black cliff, lots of effort goes into getting the sound just right.

Game sound effects are currently often based on choosing sounds from a sound library, but games, unlike films, are increasingly open. Just about anything can happen and make a unique noise while doing so. The chances of the sound library having all the right sounds get slimmer and slimmer.

Suppose a knight character in a game drops a shield. What should it sound like? Well, it depends on whether it is a wooden shield or a metal one. Did it land on its edge or fall horizontally, and was it curved so it rang like a bell? Is the floor mud or did it hit a stone path? Did it bounce or roll? Is the knight in an echoey hall, on a vast plain or clambering down those clanging cliffs…

All of this is virtually impossible to get exactly right if you’re relying on a library of sound samples. Instead of providing pre-recorded sounds as sound libraries do, the software of Josh and team’s company Nemisindo (which is the Zulu word for ‘sound effects’), create new sounds from scratch exactly when they are needed and in real time as a game is played. This approach is called “procedural audio technology”. It allows the action in the game itself to determine the sounds precisely as the sounds are programmed based on setting options for sounds linked to different action scenarios, rather than selecting a specific sound. Aside from the flexibility it gives, this way of doing sound effects gives big advantages in terms of memory too: because sounds are created on the fly, large libraries of sounds no longer need to be stored with the program. 

Nemisindo’s new software provides generated procedural sounds for the Unreal game engine allowing anyone building games using the engine to program a variety of action scenarios with realistic sounds tuned to the situation in their game as it happens…

In future, if that Knight steps off the stone path just as she drops her shield the sound generated will take the surface it actually lands on into account…

Procedural sound is the future of sound effects so just as games are now stunning visually, expect them in future to become ever more stunning to listen to too. As they do the whole experience will become ever more immersive… and what works for games works for other virtual environments too. All kinds of virtual worlds just became a lot more realistic. Getting the sound exactly right is no longer a barrier to a perfect experience.

Nemisindo has support from Innovate UK.

– Paul Curzon, Queen Mary University of London

More on …

Magazines …

Our Books …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

The logic piano

Piano keys
Image by Elisa from Pixabay

Victorian, William Stanley Jevons was born in Liverpool in 1835. He was famous in his day as an economist and his smash hit book ‘The Coal Question’ drew the nation’s attention to the reduction in Britain’s coal supplies. He was the first economist to raise the issue of the ecological impact of economics. Jevons had other strings to his bow though and one of the strangest for the time if also incredibly forward thinking was his 1869 “logic piano”: a device that looked a little like a piano but that “played” logic.

Jevons was fascinated with logic and reasoning. He believed you could start with one thing (a premise) and from this work through a chain of reasoning to the conclusion. He thought that this could be done for everything. This was based on a principle he espoused of “the substitution of similars”: essentially reasoning based on the idea that “Whatever is true of a thing is true of its like”,  For example, If Pharaohs are gods and Rameses is a Pharaoh (so is one of the things “like” a Pharaoh) then you can conclude Rameses is a god. He built on, and combined the ideas of, the Ancient Greeks with the then new ideas of George Boole, that we now call Boolean logic.

Boolean logic is based on a system of algebra using only the values of true and false (or 1 and 0), with operations corresponding to logical operations such as AND and OR that turn true/false values into new true/false values. This is the logic upon which computers are founded. A key idea was that you can abstract away from actual statements about truth in the real world and just replace them with variables that can stand for anything. Boole had laboriously shown using his logic how new abstract facts could be deduced from existing ones. Jevons realised that when reasoning was thought of like this, it became a mechanical process…and that meant a machine could do it.

His contemporary, Charles Babbage had been working on the idea of building mechanical “computers” but Babbage’s fundamental idea was that machines could do calculation. Jevon’s idea was slightly different and more fundamental: that machines could do logical reasoning, deducing new facts from existing ones. This was an idea that eventually came to fruition in the 20th century with the development of theorem provers where computers were programmed to do complex logical reasoning, even working on building up the whole of mathematics by proving ever more theorems from a few starting facts.

So, (with the help of an unknown craftsperson), Jevons set about designing and building his wooden Logic Piano. The idea was that you could put in the premises, the basic facts, by playing the keys of the “piano”. It would then mechanically apply his reasoning rules to discover all conclusions that could be deduced, altering its conclusion with each new fact added, The keys moved rods and levers that made logical facts appear on (or disappear from) the “display” of the machine – essentially facts on the rods appeared in slots cut into the back of the piano.

The kind of logical problem his machine worked with are Syllogisms (see Superhero Syllogisms). They were invented by the Ancient Greeks who were very good at logic. A syllogism is just a common pattern that combines facts where you figure out a conclusion only using the facts supplied, slotted into a template. For example, if we know facts 1 and 2 in the following template (where you can swap in anything for A, B and C) then we can create a new fact as shown.

FACT 1 ALL A B FACT 2 C is a A NEW FACT C B
Image by Paul Curzon

So let’s replace A with the word superheroes, B with fight crime and C with my favourite superhero, Ghost Girl. If we put them in to the template above we get a new “fact” deduced from two existing ones:

FACT 1 ALL super heroes fight crime FACT 2 Ghost girl is a super hero NEW FACT Ghost girl fights crime
Image by Paul Curzon
A set of 4 vertical rods with A B A ~B ~A B ~A ~B
Image by Paul Curzon

In the piano, a set of rods acted as truth tables, each one giving a true or false values for each variable. So imagine a piano that could deal with two variables A and B. Each of A and B can have two different values true and false, so there are four possibilities (so four rods):

  • (A, B);
  • (A, NOT B);
  • (NOT A, B);
  • (NOT A, NOT B)

where we write A to mean the assertion A is true and NOT A (or ~A in the picture) to mean A is false. Each rod represents a possible state of the world.

Let’s look at a simple example. Suppose A stands for the statement “Paul is a programmer” and B stands for “Safia is a programmer”, then the possibilities (if we know no specific facts) are

  • (Paul is a programmer, Safia is a programmer) : (A, B)
  • (Paul is a programmer, Safia is NOT a programmer) : (A, NOT B)
  • (Paul is NOT a programmer, Safia is a programmer) : (NOT A, B)
  • (Paul is NOT a programmer, Safia is NOT a programmer) : (NOT A, NOT B)
A set of 4 rods with bars that can hide the text if they are moved A B A ~B ~A B ~A ~B
Image by Paul Curzon

Each rod in Jevon’s piano had one of the possibilities on, so each rod represented a possible state of the world being reasoned about. At the start all the rods were visible, showing that nothing specific was yet known.

The point is that these represent all possible states of the world about Paul and Safia and whether they are programmers or not. If we know nothing more then all we can say is that all the pairs of facts are a possibility: all are possible states of the world.

The piano worked by essentially leaving displayed or hiding each rod’s state as new facts were keyed in. (See the video at the end which includes a detailed explanation by expert David E Dunning on the detail of how it did this step by step). Initially all the possibilities are displayed as above. If we add a new fact that we have discovered or wish to assume, say that “Safia IS a programmer” (in terms of the piano, press the B key corresponding to the fact B is true), then doing so removes all states of the world where Safia is NOT a programmer. The piano, therefore, hides all the rods that include the assertion representing “Safia is NOT a programmer” (all those with (NOT B) on them) . We are left with two alternatives:

second and fourth rod moved so hidden leaving A B ~A B
Image by Paul Curzon
  • (Paul is a programmer, Safia is a programmer) : (A, B)
  • (Paul is NOT a programmer, Safia is a programmer) : (NOT A, B)

The mechanics of the machine meant that those facts would remain a possibilities (reading down the rods) but pushing the keys for that assertion would have moved the other rods, so hide their state. In doing so, the piano has deduced from the fact B that the possible conclusions are A AND B is true or NOT A AND B is true.

With three variables instead of two the machine would be able to deal with more complex situations – there are then 8 possibilities so 8 rods representing the 8 different states. .

A set of 8 rods with A B C A B ~C A ~B C A ~B ~C ~A B C ~A B ~C ~A ~B C ~A ~B ~C
Image by Paul Curzon

Let A represent superheroes, (so NOT A represents those people who are not superheroes), B represents those people who fight crime and C with a person being Ghost Girl. Suppose we are considering some, at the moment, random person we know nothing about. The possibilities about them are:

  • (Is a superhero, does fight crime, is Ghost Girl) : (A, B, C)
  • (Is a superhero, does fight crime, is NOT Ghost Girl) : (A, B, NOT C)
  • (Is a superhero, does NOT fights crime, is Ghost Girl) : (A, NOT B, C)
  • (Is a superhero, does NOT fight crime, is NOT Ghost Girl) : (A, NOT B, NOT C)
  • (Is NOT a superhero, does fight crime, is Ghost Girl) : (NOT A, B, C)
  • (Is NOT a superhero, does fight crime, is NOT Ghost Girl) : (NOT A, B, NOT C)
  • (Is NOT a superhero, does NOT fights crime, is Ghost Girl) : (NOT A, NOT B, C)
  • (Is NOT a superhero, does NOT fight crime, is NOT Ghost Girl) : (NOT A, NOT B, NOT C)

If we put the fact about them into the piano that ALL superheroes fight crime (ALL A are B) then we remove all rods where A is true but B is different so false (a superhero who doesn’t fight crime) as in this world, that is impossible.

3rd and 4th rods hidden so leaving A B C A B ~C ~A B C ~A B ~C ~A ~B C ~A ~B ~C
Image by Paul Curzon
  • (Is a superhero, does fight crime, is Ghost Girl) : (A, B, C)
  • (Is a superhero, does fight crime, is NOT Ghost Girl) : (A, B, NOT C)
  • (Is NOT a superhero, does fight crime, is Ghost Girl) : (NOT A, B, C)
  • (Is NOT a superhero, does fight crime, is NOT Ghost Girl) : (NOT A, B, NOT C)
  • (Is NOT a superhero, does NOT fights crime, is Ghost Girl) : (NOT A, NOT B, C)
  • (Is NOT a superhero, does NOT fight crime, is NOT Ghost Girl) : (NOT A, NOT B, NOT C)

Then we add the fact that Ghost Girl is a superhero (C is a A) so remove all those rods where Ghost Girl is not a superhero (ie NOT A, C):

3rd 4th and 5th rods hidden so leaving A B C A B ~C ~A B ~C ~A ~B C ~A ~B ~C
Image by Paul Curzon
  • (Is a superhero, does fight crime, is Ghost Girl) : (A, B, C)
  • (Is a superhero, does fight crime, is NOT Ghost Girl) : (A, B, NOT C)
  • (Is NOT a superhero, does fight crime, is NOT Ghost Girl) : (NOT A, B, NOT C)
  • (Is NOT a superhero, does NOT fight crime, is NOT Ghost Girl) : (NOT A, NOT B, NOT C)

We have deduced (the first possible state) that if the person we are interested in is Ghost girl then she is a superhero. We are also left with other possibilities too. If the person we are considering is not actually Ghost Girl then they may or may not fight crime and may or may not be a superhero!

If we add in an additional fact that the person we are thinking of IS actually Ghost Girl then we remove those extra rods so possibilities and get

All but first rod hidden so leaving A B C
Image by Paul Curzon
  • (Is a superhero, does fight crime, is Ghost Girl) : (A, B, C)

Ghost Girl is a superhero who does fight crime! We knew she was Ghost Girl and was a superhero but using the piano we have now deduced that she does fight crime. The machine has deduced the syllogism we gave at the start.

IF ALL superheroes fight crime AND
   Ghost girl is a superhero
THEN
   Ghost girl fights crime.

The actual piano dealt with 4 variables (A, B, C, D) so had 16 rods representing the 16 different combinations. It also included keys to indicate the end of a conjecture, a key for IS A, and more to allow specific assertions to be input. The mechanism then hid rods automatically based on the facts entered. To use it, you did as we did: create a table of what A, B, C and D stand for (this is done outside the machine), enter the facts you want to reason about, and it then displayed all the possible states that remained in terms of A, B, C and D. Then, by seeing what each of the variables stood for in the table, you could convert that answer back into a deduced fact about the real world that you were interested in.

Amazingly, (after a first failed attempt) it did work. It is similar in idea to modern day theorem provers which are used to verify properties of safety-critical computer designs that must npot have bugs. Of course, being small and woody, the logic piano couldn’t solve every thing but then it turns out that was always an impossible dream. Even modern computers (and human mathematicians) have fundamental limits in what they can do (which is another story). The logic piano was a rather amazing, if woody, start to the area of automated theorem proving, though.

– Paul Curzon, Queen Mary University of London

Make a paper logic piano

Here is a kit to make a paper or card logic piano of your own (actually more like Jonons’ logic abacus the piano was a mechanised version of):

More on …

Watch…

  • A Purely Mechanical Form
    • A Talk by David E Dunning at the Imagining AI conference about William Stanley Jevons and the logic piano including at the end a more detailed explanation of how pressing keys actually caused rods to by hidden in a series of steps. See also his article about it for the Computer History Museum.

Magazines …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos