Month: November 2017

Ep 97: Von Neumann’s cellular automata

Ep 97: Von Neumann’s cellular automata

Von Neumann’s cellular automata

John Von Neumann began considering the idea of self-replicating systems and machines in the 1940/s. Originally, he considered actual robots, who could build other robots that could build other robots. He quickly became bogged down by the complexity of real world machinery, and the expense of providing enough parts for a robot to build a robot. Instead of using real world machinery, he created cellular automata, which was a grid that changed according to a set of rules—each cell changing according to the state of its neighboring cells. Using this abstract model, he was able to construct self-replicating systems, machines that could build copies of themselves.

Here’s a copy of a report put out by NASA in 1980, considering the advantages of using self-replicating machinery to automate the extraction of materials, and the production of useful products. It was my introduction to self-replication and cellular automata.

NASA’s Advanced Automation for Space Missions

Ep 96: Barricelli’s numeric organisms

Ep 96: Barricelli’s numeric organisms

Barricelli’s numeric organisms

Before Core Wars, or the computer game Darwin, just about as soon as a computer was built that could run the program, a rather obscure Italian scientist named Barricelli, did pioneering experiments in digital life. While his work remains largely unknown, it does demonstrate how people have been working on evolving computer code from the very earliest days of computers.

Here’s a link to the talk where I first heard of Barricelli.

George Dyson: The birth of the computer

Here’s a page that includes an implementation of his work, including source code.

Barricelli : Built with Processing and Processing.js

And here’s an article about Barricelli and his work.

Meet the Father of Digital Life

Ep 95: The dreaded local minimum

Ep 95: The dreaded local minimum

The dreaded local minimum

While talking about various and sundry methods of simulating natural processes like evolution in order to solve problems, the concept of a local minimum has cropped up from time to time. Today, we take a closer look at it, and some of the ways to escape.

Turing machines

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

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

Ep 94: Computer ants?

Ep 94: Computer ants?

Computer ants?

Evolution based approaches to generating solutions to complex problems, have some drawbacks. They tend to require a great deal of computing resources, such as processer time and data space. A different approach called “Ant Colony Optimization” requires much less time and number crunching for certain types of problems. The ants use cooperation rather than competition, and have been successful in applications from air traffic control, to real time internet data routing.

Here’s a link to a video that covers the algorithm in detail, including the equations used, and some of the experiments that were performed with real, living ants.

Ant Colony Optimization

Here are a couple other sites on ant colony optimization.

ACO: Tutorials and Courses

aco-metaheuristic.org

Ep 93: Tit for tat, thanks for that

Ep 93: Tit for tat, thanks for that

Tit for tat, thanks for that

In Darwin’s original theory, natural selection was considered to be driven by competition. This presents a problem. If it’s all about survival of the fittest, and out competing all others, why is there so much cooperation in nature? In the 1980/s, a tournament was held in which competitors sent in computer programs that would play something called “The Iterated Prisoners’ Dilemma.” The program that did the best most consistently, was one of the simplest: “Tit for Tat.” It was, and still is, an example of how things like symbiosis and cooperation could evolve.

Here are a couple of articles on “Tit for Tat,” and “The Prisoners’ Dilemma.”

Survival of the nicest?

The Prisoner’s Dilemma and the “Virtues” of Tit for Tat

Ep 92: Genetic Programming

Ep 92: Genetic Programming

Genetic Programming

Today we take a look at my favorite evolutionary approach to making computers solve problems. This one has, now and again, produced results that are competitive with what humans can do.

Here’s a link to a page about Genetic Programming, including some of the human competitive results.

genetic-programming.org

Here are a few tutorials on Genetic programming.

Tutorial – Genetic Programming

A Field Guide to Genetic Programming

Ep 91: The genetic algorithm

Ep 91: The genetic algorithm

The genetic algorithm

Your DNA has most of the information needed to make you you. The information is encoded through four different chemicals that act as a sort of alphabet, spelling out the language of life. In the 1960/s a similar approach was adopted to solve complex problems.

Here’s a tutorial on genetic algorithms and how to use them.

Genetic Algorithm Tutorial

Water or steam? to build my computing machine?

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