Category Archives: how computers compute

Adding by subtracting

Previous post in topic
First post in topic
Table of contents

Adding by subtracting

There won’t be posts after this one on this thing for a couple of weeks. I must navigate the dangerous, relative infested waters of the holidays.

I need to be able to show that the way we program our machine can be made to run any program, at least in principle. On the other hand, I’d very much like to switch gear, and get to talking about gear soon.

Here’s one more post on using subleq. I think that will do for now.
Continue reading Adding by subtracting

An alphabet you know

Previous post in topic
Nex post in topic
First post in topic
Table of contents

It’s Monday morning. I’m sitting at my desk, using my fingers to hit keys in more or less the right order. I’m using 26 letters to construct words and sentences in order to convey my meaning. Well, 26 letters, and the spellcheck.

An alphabet is a collection of symbols that can be combined to form words. The words can then be combined to create phrases, sentences, paragraphs and pages. It’s a flexible design that allows comparatively few symbols to be used to capture and share a language, a considerable improvement on other writing systems that use a different symbol for each word. Still, if you want a machine to react to what you’re writing, 26 letters aren’t enough, or, if you squint at it another way, 26 letters are far too many.

If you look at the two first paragraphs of this section, or any of the rest of this, you’ll notice that the letters a through z aren’t the only symbols I’m using. I’ve got periods and camas, and the occasional apostrophe. For a machine to be able to follow a language, it needs every last symbol you’re going to use to be a part of its alphabet. That includes an empty space—the symbol used to separate symbols into groups. In fact, even lower-case letters, (a, b, c,) are distinct from uppercase letters, (A, B, C,) which doubles the number of letters, to 46, plus all the other symbols I just mentioned, plus all the others that I didn’t.
The English alphabet started as a sort of shorthand way of writing. The Egyptians needed a way to write instructions for their workers. They came up with a phonetic system that was much quicker to learn and easier to use than their hieroglyphics. Later, the Phoenicians picked it up. Then, they passed it along to the Greeks.

The Greek language didn’t use every sound that the Phoenicians or Egyptians did. They took the symbols for sounds they didn’t use, and changed them into vowels. Combining vowels with the Phoenician consonants, they could represent every sound used in their language with fewer symbols, and it gave them a way to try and approximate sounds from other languages. Later still, the romans added a couple of other letters to cover sounds they used that the Greeks did not. Still later, the Roman alphabet turned into the beginning of the English one, along with several others.

Alphabets, like the languages they represent, change over time. At any given moment, someone somewhere could draw some new character and toss it into the mix. Even if your basic alphabet doesn’t change, you and your folk might get into something like engineering, or mathematics, or logic, and suddenly there’s a mess of folk, inventing new symbols left and right. If you need to include every symbol you’ll use in the machine’s alphabet, and new symbols may be added, your poor confused computing contraption will need an alphabet that includes all possible symbols.

Let’s see… That’s 26 lowercase, 26 uppercase, all the numbers, all the punctuation marks, spaces, indents… and every other possible symbol. I think that’s infinite.

There is an easy way to represent all possible symbols.

Take the symbols, letters and so forth, and map them to numbers. A simple version is to take the letters of the English alphabet, and number them, 1 through 26.

A=1, b=2, c=3… z=26.
So, “8 5 12 12 15” is the same as “hello”

we need spaces between the numbers to let you read them, but what if we want there to be a space between one word and the next? we’ll need a number to represent a space, say 27.

“8 5 12 12 15 27 23 15 18 12 4” means “hello world”

We’ve got quotation marks, which could be mapped to 28.

28 8 5 12 12 15 27 23 15 18 12 4 28 means “hello world”

Whenever we want or need a symbol that hasn’t been included, we can use the next number. Which number is mapped to which symbol doesn’t matter, so long as it’s consistent. To keep things simple, one can avoid fractions and the like. Using only whole numbers, all possible numbers can be written with an 11-symbol alphabet—0, 1, 2, 3, 4, 5, 6, 7, 8, 9, and a space. The number of whole numbers is infinite, so we can use 11 symbols to represent an infinite number of different symbols.

In typical computer design, your system represents all the letters and such you see, and various and sundry commands with numbers. If you want the computer to add two numbers, for example, it will send those numbers to a couple of specific spots in the machine, and another number that means, “Add those for me,” to another specific spot. Then, it can fetch the answer from yet another spot. To be sure the right number goes to the right place at the right time, the places where numbers can be sent have addresses, which are also numbers.

The simplest possible alphabet consists of only two symbols. If you have one symbol represent a zero, and use the other to represent a one, you can represent all possible numbers with just two symbols. Because of the way computers store numbers, you don’t even need a special character to represent a space.

It’s easier to design for a two-symbol alphabet, but the simplest alphabet isn’t always the simplest to follow. We’ll be using integers—positive and negative whole numbers. Keep in mind that our contraption will see these as zeros and ones, but we’ll get to how that two-symbol alphabet, called binary, actually works in later sections.

Before we start to design our contraption, let’s take some time to figure out how it will be programmed—how we can tell it what to do. Because, if we don’t give it a program to run, it will sit there, fires stoked, billows of steam drifting picturesquely through the air, and do nothing.

Previous post in topic
Nex post in topic
First post in topic
Table of contents

Turing machines

Next post in topic
Previous post in topic
First post in topic

There was the butcher, the baker, and the candlestick maker. Good for them, all fine an honorable professions, but there was another job you could have back in the day. You could be the computer.

Just like butcher or baker or candlestick maker, a computer was a job title, the person who did whatever calculation you needed to have calculated. This might be to survey property, work out your taxes, figure out how much flower the baker should order, how much extra business the candlestick maker could expect in an average winter, or how much money the butcher could expect to lose when some religious observance kept customers from eating or ordering any meats.

Computers often used things to help them calculate. This could be as simple as marks on a stick, or small stones moved from one bowl to another, or it could be some sort of calculating device. In many cases, such as with the abacus, the arrangement was simple, but there were special rules and procedures to follow, such as one row of beads representing ones, and another being fives, and another being tens. It was part of the computer’s training—learn the device, and the way to use it, and then figure out how to use what you’d learned to give the butcher, the baker, and the candlestick maker the numbers they needed.

As with any other profession, some computers were better and more reliable than others. They could, and did, make mistakes in their calculating, and the skills to catch the mistakes or correct them before they could cause problems weren’t widespread. If, instead of working for one of the honorable townsfolk, your customer was, oh say, the king, this could become especially ticklish.

Running a kingdom takes lots of number crunching. You have to gather taxes, assess land, build castles, lay roads, store food, maintain the army, and that was all in peace time. If you went to war, things got much more complicated.

Good numbers, and your weapons hit, your troops had accurate maps, your forces could arrive when and where they were needed with enough supplies to let them win the day. Bad numbers and you couldn’t hit anything, the troops stumbled randomly across the countryside, you could miss the battle, lose the war, and your soldiers might find they’d been sent too many candlesticks and not enough meat.

Over the years, a number of mechanical calculating machines were designed and built. These machines often took quite a bit of calculating to figure out how they could calculate, and a good deal of time and money to build them. They were often built to solve a particular problem quickly, but even when everything worked, you still needed the computer to use them. If you’ve ever used a calculator, you know how easy it is to hit the wrong buttons, or even the right buttons in the wrong order. So, errors persisted in causing problems. To make matters worse, sometimes the calculator would depend on large tables of numbers, worked out by computers and then built into the machine. If there was a mistake in those tables, it got built right in. Then, after all that time and effort building the calculator for, say, aiming your guns, when you needed to do something different, like keep track of supplies, you’d be forced to design and build an entirely different calculator.

What if, instead of building some calculator for a computer to use, you could build a computer? Could some machine be designed and built that could do any calculation, and which could, if given very specific instructions, push its own buttons in the right order. You’d only need one kind of machine, and the number of errors could, at least in principle, be lowered to nearly zero.

Enter the Turing machine.

The Turing machine is an abstract model of a computing machine, described by Alan Turing in 1936. It has a tape, divided into cells or slots. In each slot there can be a symbol, or the slot can be blank. The symbols are part of a predefined alphabet that can be used to write commands or instructions. The machine has a head that can read a symbol, or write one. Lastly, the tape can be moved in either direction. The machine will read a symbol and then, depending upon what’s been read, it will write a different symbol, or move in one direction or another, according to a table of rules. The machine can store some of the symbols internally, and it changes from one state to another according to what symbols are encountered and the rule table.

When I first read about Turing machines, I was less than satisfied. The explanations I was reading seemed like they did a lot of hand waving. Somehow, this set of internal states and this alphabet and either move read or write was supposedly enough to make this thing do everything a computer can do. But how? How does reading writing and moving turn into Mine Sweeper, or the table of rules and internal states become email, text messaging, YouTube and Twitter?

Let’s find out!

A computer used to be a job, and before we try and make a machine do the computing, it will be our job. We’ll use an alphabet you’re already familiar with, and one simple procedure that can be repeated over and over again, to obtain any result we need.

Our alphabet has only eleven symbols—the numerals, 0 through 9, and a minus sign.

Next post in topic
Previous post in topic
First post in topic

A table of lacking contents

Next post in topic
Previous post in topic

This is my table of lacking contents. Some of it will become links, some of it may be changed renamed or moved about, but here’s where we’re going.

Table of contents:

We said hello… more or less

Table of contents

Turing machines.

An alphabet you know

The prime, and only, directive.

Adding by subtracting

What the machine needs to do.

A bit of binary

An optimistic gear design

A counting machine with half full gears

Turning the counter into an adder

Of subtraction and distraction

Loops, and multiplying by subtracting

If else and dealing with negatives

Steam, valves, cogs and cams

The cam tape

The counting machine with steam and pistons and valves

Going the other direction

Stopping in the right place

Division with subtraction

Dealing with negatives

Zero, the deadly devisor

The halting problem

Step by step

Binary and negative numbers

Going in the right direction

Moving data

Subtraction with steam

Writing to the tape

Picking the right direction

Starting over

Hello world

Special addresses

Doing it all with subtraction

Copying buffers

A special address with steam

A faster, and bigger, design

Next post in topic
Previous post in topic

Water or steam? to build my computing machine?

Next post in topic

A “steampunk computer,” is apparently a style of home or work station. I kind of want one, but… When I think “steampunk” I think actual steam. Or tech on that level, hugely complex, and able to magickly work somehow, instead of falling apart, seizing up and exploding.

I think I can build one.

Whirring, clunking, banging and hissing—let’s skip all that newfangled electricity, and design a mechanical computer.

I’m not doing this in the garage; I’m doing this in your head. Things in the garage have an unfortunate tendency to fall apart, seize up and explode.

I’d like to walk through how a computer computes. Partly because I’ve always wanted to read something like this, and partly because I won’t really have it figured out until I’ve walked through it.

If you can add and subtract, you have all the math you’ll need.

Next post in topic