Category Archives: computing

Choo-Choo Charlie was a [Software] Engineer

railyard

When I was a kid in Pennsylvania, we lived for many years right next to a railroad track, which ran behind my back yard. The trains on that particular track were infrequent, but we'd go down to the tracks and then wave and shout at the engineer in the caboose. He'd toot his horn. Trains, rails, and rail yards, where trains are stored and come together, are information flows--that is how a computer scientist sees them: information moving around, being processed, being controlled. That is how we see everything--admittedly somewhat of an unusual way of seeing. There are numerous information controls and structures such queues when train cars move through stations, and stacks when a train reaches a terminus at the rail yard, and the locomotive may need to be attached to the other end. A "stack" is a mental concept. Stacks implemented in written software are ways of reifying the stack concept using typography--seeing it with the naked eye. Trains at rail yards are another way of seeing stacks. The train's behavior is not a visualization of a stack. It is a stack. As much as anything else is one. Then, there are the track switches, merging, selection, sorting - just about everything you need to make a data flow computer. If we can observe trains as information then we can use this as a metaphor to recreate data flow in the image of trains. The trains, or slight simplifications of them, become models for computation--creative automata.

 

Complexity: What is it?

fractal

What is a complex system? The word "system" is less controversial and clearer to most since a system is composed of elements such as states, events, transforms (and other functions), input, and output. However, "complexity" is...complicated! In casual conversation, if we say that a system is complex then it is seems hard to understand. When you think of complexity, consider two spaces: the problem space where you formulate a model, and the solution space, which reflects simulation--where you execute that model on a computer. The fractal behavior in the Mandelbrot Set seems complex but that is only in  solution space. The equation where this set is defined is very short and simple and not complex at all (well, it is formulated in the complex plane, sigh, but that is another meaning of complex). In contrast to the equation that spawns the Mandelbrot Set, we find the vast world of software. Talk about complex. Yet, the complexity lies in the problem space (defining the algorithms and writing the computer programs). There are many definitions of complexity, including Halstead's definition for software (a function of the number of operands and operators in the software). Complexity can be interesting and curious for science, and to be avoided in other cases as when we seek to engineer safe, quality products.

 

Two Words

basalt

 

Creative Automata. The two words that make up this blog's name and the research lab at the University of Texas at Dallas. I tend to name things that have the potential to be confusing, and ambiguous. The idea is that the ambiguity and tensions that exist in names can give rise to reflection on how words can shape our thoughts. So, as for the word "creative," this word was chosen to emphasize the importance of the process of creation on representation. If I represent computer code, data, or a mathematical formula with hexagonal columns of basalt as elements, it is because I choose to do so as part of my creative output -- not because I believe that this representational mapping might become a universal "visualization" for the masses, or for expedited communication. Think of this as a puzzle, a form of entertainment. There is much to be learned from the creative act in learning. As for the second word "automata," the goal is to take the best features from two connotations of this word: 1) make it so that any machine in the systems-sense can be viewed as an automaton (a view from the theory of automata), and 2) make it so that automata can be both imaginary and physical (a view from mixing the two-millennia old history of automata with the modern mathematical theory). Automata should be a broadly conceived notion.

Lukyanov's Water Computers

watercomputer

The wonderful thing about computing with water is our familiarity with this ubiquitous substance. Water is everywhere that we are. As I look outside my house window at the ice melting, I see melted water drops and then a spreading of water. I can also see water and trapped air bubbles underneath the ice as it melts on the road surface. Familiarity with water stems from our drinking it, bathing in it, and watching it flow in rivers and streams. Water can also be used, via analogy, for performing computations. Water is a natural integrator - turn the tap (the derivative), and capture the tap water into a container (the integrated derivative). Vladimir Lukyanov designed and built several water integrators in Russia and the USSR, and extended them to solve partial differential equations (PDEs). The above image is from Science and Life: a two-dimensional hydraulic integrator. The machines can be found in the Polytechnic Museum in Moscow.

Paper Computer

Cosmographia2

 

Volvelles are primitive paper computers and they were found in books in astronomy. Volvelles were printed as part of a book and served as interactive devices long before the world wide web and browser. The one pictured above is from Petrus Apianus' Cosmographia published in 1524. Volvelles were also called "Apian Wheels." The purpose of these devices was to compute something such as the time of sunrise or sunset at a specific latitude. This computation is a form of simulation--of the motion of the sun or moon. How can one simulate anything with paper? Think of the volvelle as a radial look up function table. Suppose you wanted to create something to determine y=sin(x). The volvelle creator will pre-compute sines for different values of x in making the device. Then as the user/reader, you rotate the disc to x and read off y. If you have ever used a circular slide rule, this works on a similar principle where the scale is logarithmic.

Product of Strings

string2

I was in New York City last week and stopped by the new Museum of Math (MoMath at 11 East 26th Street in Manhattan -- not too far from the Empire State Building). A worth while visit, and many excellent exhibits. One exhibit is called "String Product," pictured above from the New York Times Alice in Math Wonderland article announcing the museum's grand opening back in December 2012. String Product is an analog computer that calculates products, such as a times b, where a is on one circle of the sculpture, and b is on another circle with a string connecting a to b. At the center of the structure, from bottom to top, numbers are listed in order, and the ab product can be found by noting where the string crosses the center. The strings are chords of the structure, known as a paraboloid. A subsequent Times page provides additional information on the museum, and includes a description of how the string product functions.

 

Marquand's Logic

Marquand

Most of our critical thinking can be attributed to logical argument. An old and well-established logical rule is the syllogism: (1) All humans are mortal, (2) All Greeks are humans, (1) and (2) conclude via syllogism that (3) All Greeks are mortal. This form (AAA), with A indicating "All," is referred to as Barbara, a mnemonic. In the 1883 text Studies in Logic (John Hopkins University) edited by C.S Peirce, Allan Marquand designed a machine to produce syllogisms with the design illustrated in the above diagram. Marquand's paper was entitled "A Machine for Producing Syllogistic Variations." The design is interesting and appears to serve as a mechanical aid to combinatorics. The hand crank is attached to d. There are "sectors" for each of the d,e, and f wheels causing friction against a, b, and c. Variations are achieved by wheels d, e, and f having diameters of powers of 2: 1, 2, and 4 inches respectively. Mechanical counters are similar except that finger protrusions are used on identically sized wheels to create combinations.

Information ≠ Data

chip-8
What is the connection between automata and data? Think of data as the material that flows through the machine. The data may be unstructured or structured but in either case, data can be "serialized." Popular approaches to serialization are XML and JSON. In XML, for instance, you can create a stream of characters that contains arbitrary structure (tree, graph). This stream enters the automaton, is processed by it, and leaves the machine changed or transformed in some way. Sometimes, we think of "information" as being equivalent to "data," but this is not so since information, as with the serial encoding of XML, can encode any structure from data and formula to model and program. In the old days of writing code, we used to write a computer program and the data it accessed with hexadecimal characters (0 through F): programming in bits. A cursory glance would not indicate which bits were data and which were code. The only computer I could afford after getting a bachelors degree was the Cosmac VIP sold by RCA, and I programmed using code similar to the image in a language called CHIP-8. We are now in the age of Big Data, but without automata to process that data, we are left without code, models, machines, automata, and a way forward.

Computing's Split Personality

splitpersonality

What has two personalities and sits on your desk? A computer. To do in your spare time: search for the word "automata" in an image-based search. You'll probably see some crafty wooden machines and then a few odd looking diagrams with circles and letters. This is the split-personality surfacing. Prior to 1950 the word automaton, and the word computer, either meant a human being (who computed) or an analog machine. This is not strictly true because, for example, Babbage's 19th century engine designs were digital; however, up to World War II, analog computing was in wide use making digital computers relative newcomers. In the above image, on the left we have a deterministic finite state machine represented as a diagram. On the right, one of Cabaret Mechanical Theatre's inventions (Pirate Panic). Pirate Panic is driven by an analog computer, and like most analog computers, it solves a formula resulting in a continuum of states. Thankfully, the formula is most entertainingly realized with a Pirate and an Octopus. So, will the real automaton come forward? Both are valid automata and the divergence of types could be covered adequately only in a book. The short story is that the mathematical theory of automata proceeded in one direction, and the analog variety lives on in disciplines that rely on "signals and systems" which interestingly enough, means some computer music interfaces and languages in addition to the Pirate.

Censorship Machine

censorssmall

 

Machines can take on many forms, including this one which is flat and would be formally described by a network of activity nodes and arcs among them. The above example is a machine (or automaton) that is defined by flow, as are all automata. The automaton models the censorship process in Iran beginning with the Supreme Leader and then cascading down to the enforcers. This machine is constructed by The Annenberg School for Communication at the University of Pennsylvania. There is a complete description of the process, with the above figure at its original resolution at their web site. Nodes are points of control and arcs probably carry both control and data flow. Curiously, there is very little feedback in this architecture (only at the very end). There is also an interesting correlation between the abstract semantics of machines and Iran's censorship process: power flows from top to bottom (both literally and figuratively). Machines of this sort are a bit different than those in some of the other posts because they are often called models--specifically simulation models. To be more precise, this is a simulation model of the censorship process.

Classic Turing Machine with Tape Erasure

turingFull560

Alan Turing designed a mathematical structure to capture the essence of computation with the fewest number of elements, but so that universal computation would be possible. The result is usually referred to as the Turing Machine, and the study if this particular automaton along with many others forms the basis of automata theory taken by every computer science student. The subject is taught either in that theory class, or also sometimes in the broader area of discrete mathematics. If you are seeking to know computational thinking and the core conceptual basis for computer science, this is where you will find it.

The above physical model is by Mike Davey and is a beautiful piece of machinery. Turing Machines, in their core capability are amazingly simple devices: think of a machine having a read/write memory (you can store stuff in memory and then retrieve it later), a register (which stores the "state" of the machine), and a program that is composed of instructions to move around memory. The tape metaphor represents a linear motion along a tape (that is infinite in length). Make sure to play the video on Davey's site for a good explanation of the device and its operation. I found the erasing mechanism simple and yet elegant. Some model Turing machines use replacement of a physical artifact rather than erasure as with some Lego-based models where a small object is used to denote a bit and then "read" using an sensor capable of distinguishing between black and white objects.