I do not mean that the machine has no states. That would be a silly assertion. I'll explain why I say stateless later.
For what I'm calling a stateless machine, the output from a given input is always the same, within the analysis of the machine.
For example, when I build a machine involving a lever and a fulcrum and a rock, if the lever is set right, when I push the one end of the lever down, the rock raises a bit. Then, when I let the lever up, the rock drops back down. (I'm not yet analyzing what happens when the rock slides off, we have to do these things in small steps.)
The inputs, then, are lever down and lever up. The outputs are rock up and rock down. Really simple, right?
The same could go for your (toggle) light switch in the wall and the light in your ceiling. Again, we aren't discussing at this point what happens when there's no electricity, or when the light burns out, or when the switch itself breaks for some reason. Toggle up, and the light goes on, down and it goes off.
Note that pushing the switch or lever down always results in the same output, whatever the output was before. Same with pushing the switch or lever up. This is what makes the machine stateless. (We can analyze the machine as having states as well, but we want to look at the stateless analysis first.
One more example might be a push button attached to an indicator lamp (or doorbell). Push the button down and the lamp lights (or the doorbell rings), release it and the light goes out (or the doorbell goes silent). (Vice versa would also be a stateless machine, but lets focus on one thing at a time.)
Putting this all together:
Now, if we add lots of levers and rocks, or lots of switches and lights and/or doorbells, as long as every one of them is like this, where a specific input always gives a specific output, no matter how many we add to the overall machine, the machine is still a stateless machine.
It may look complicated to have twenty or two hundred thousand such machines together in a single conglomeration, but the overall machine is still in the stateless class, as long as each input results in the same output.
If you say, well, wait, it sounds like maybe we are talking about two different kinds of complexity here, you're right.
Specifically, the number of elements is a measure of something we sometimes call complexity. It would be more accurate to call it a measure of the number of parts, and hopefully we'll come back to that.
The other complexity, well, we have to give some more examples before we can really name it.
However, as long as we are talking about multiple inputs and multiple outputs, we can talk about a few more stateless machines, to help understand what stateless machines are.
The set of inputs and outputs don't have to be the same in number. For example, you might have three input buttons and one output lamp, and the more buttons you push the brighter the output lamp shines:
Instead of brightness, you could have color:
This is still stateless. There is a complexity of in the number of combinations in the processing, but outputs are still not being fed back to inputs, and the output is still not dependent on timing or previous states.
Note that the buttons, instead of A, B, and C, might be labeled meaningfully, as "0", "1", and "2", or "Red", "Green", and "Blue". Or they might be labelled obscurely, as "Purple", "Pink", and "People Eater". The labels may affect our perception of the machine. They may make it more or less simple to understand. They may make it appear more or less complex. But the labels on either input or output do not effect the internal structure of the machine, or its underlying complexity.
The above tables and descriptions can be translated into mathematical formulae. For instance, the last table can be written (using ~ as not)
off = ~A ∧ ~B ∧ ~C
blue = ~A ∧ ~B ∧ C
green = ~A ∧ B ∧ ~C
red = A ∧ ~B ∧ ~C
cyan = ~A ∧ B ∧ C
magenta = A ∧ ~B ∧ C
yellow = A ∧ B ∧ ~C
white = A ∧ B ∧ C
Here's one typical way of doing this in C programming language source code, which is another kind of formula. This is not the only way to do it, but many would probably say it's the most obvious and the most readable.
/* Assuming that the button inputs are individual bits at the same port address,
** button A on the lowest bit, B on the next bit, and C on the next:
*/
#define INPUT_A 1
#define INPUT_B 2
#define INPUT_C 4
#define BUTTON_PORT ( (char *) 0xFFF1 )
/* Assuming that the output is a three filament lamp
** with colored lenses arranged for proximity combination,
** with the filaments on individual bits at the same port address,
** blue filament on the lowest bit, green on the next, and red on the next:
*/
#define OUTPUT_OFF 0
#define OUTPUT_BLUE 1
#define OUTPUT_GREEN 2
#define OUTPUT_RED 4
#define OUTPUT_CYAN ( OUTPUT_GREEN | OUTPUT_BLUE )
#define OUTPUT_MAGENTA ( OUTPUT_RED | OUTPUT_BLUE )
#define OUTPUT_YELLOW ( OUTPUT_RED | OUTPUT_GREEN )
#define OUTPUT_WHITE ( OUTPUT_RED | OUTPUT_GREEN | OUTPUT_BLUE )
#define LAMP_PORT ( (char *) 0xFFF3 )
int buttons_to_colors( int buttons )
{
switch( buttons )
{
case INPUT_C : return OUTPUT_BLUE;
case INPUT_B : return OUTPUT_GREEN;
case INPUT_A : return OUTPUT_RED;
case INPUT_B | INPUT_C : return OUTPUT_CYAN;
case INPUT_A | INPUT_C : return OUTPUT_MAGENTA;
case INPUT_A | INPUT_B : return OUTPUT_YELLOW;
case INPUT_A | INPUT_B | INPUT_C : OUTPUT_WHITE;
case 0 : return OUTPUT_OFF;
}
}
int set_colors_by_buttons( void )
{
char * button_address = BUTTON_PORT;
char * lamp_address = LAMP_PORT;
/* Assuming hardware de-bouncing. */
* lamp_address = (char) buttons_to_colors( * button_address );
}
Here are some other mathematical machines that you might be more familiar with, expressed as formulae:
y = x
y2 = x2 +3x - 6
f(x) = ax2 + bx + c
x: x < 0, f(x) = -x
x: 0 ≤ x < 2π, f(x) = sin(x)
x: 2π ≤ x, f(x) = x2 - 3x + 1
f1(x) = a1x2 + b1xy + c1y2 + d1
f2(x) = a2x2 + b2xy + c2y2 + d2
f3(x) = a3x2 + b3xy + c3y2 + d3
3x2 - 2x + 6xy + 5y - 4y2 + 7 = 0
and so forth. Many of the mathematical formulae that we, in our current education system context, tend to think of when we think of mathematical formulae, belong in this stateless class of machines. (Hmm. If you are not an engineer or physicist, you may not remember having ever seen a stateful equation, but let's not get lost in that yet.)
The points that characterize this level of complexity are as follows:
Timing is not involved. When a button is pushed, the output changes more or less directly.
Output is only dependent on the inputs. No output is dependent on any other output.
Output is only dependent on the current inputs, independent of whatever the output may have been before.
Now, these are idealized descriptions of machines, which is another thing I want to point out here but leave for discussion later, when we have tools to discuss the differences between ideal and real machines.
(Only idealized?)
Let me repeat that:
These are mathematical models of machines, not real machines.
Well, okay, I have referred to a few real machines above, the lever and rock, the pushbutton and toggle switches, etc. But my descriptions are not real machines. (No brainer, there, okay.) Nor are the tables showing the functions. (Of course not, but some people start seeing a little fuzz around the edges.) Nor are any mathematical descriptions. (I'm treading on toes now, but bear with me.)
The formulae above, I hope this is still obvious, are not real machines in the sense that the switches and levers are. Maybe real in some sense, but not in the sense that physical objects can be real machines.
Just idealized models of machines.
I could hack together some graphics and javascript, erm, ecmascript, and make fancy visual models that you could play with, buttons and levers and output lights and an icon (picture) of a rock that rises and falls. I could generate parameterized graphs of the above mathematical functions and relations, and charts of input and output values, and these still would not be real machines.
I could implement these machines in program source code and the source code would not be the real machines. I could write out pseudo-code or high-level descriptions of the machines and there would still be no real machines in existence (yet).
Nor would the compiled object code be real machines. And it doesn't matter whether the code is stored in magnetic domains on rotating disks or in semiconductor constructs or holes in punched cards. In fact, it doesn't matter whether the code is stored in cams, gears, ratchets and intricate combinations of levers and pulleys.
(If you happen to "own" a patent on some bit of software, you may be feeling more than a little irritated that I am saying that the patent you own is not a patent on a real machine, but bear with me, please. I'm not trying to sucker-punch anyone here, so I want to make it clear where I'm going.)
Source code, object code, it doesn't matter. Something in a real machine has to interpret the code before real things happen. Program code is formulae.
Sure, the program code becomes part of the real machine, but it is not, in and of itself, a real machine. (I will explain this in better detail later, after I have laid appropriate groundwork.)
The actual machines will differ from the models, descriptions, source code, formulae, etc. Real machines will have bugs and hidden features, and will most of all tend to get old and fall apart. Such things are usually analyzed separately (if not forgotten or ignored), to bring the complexity of the analysis down to a level that the engineer can comprehend.
Okay, okay, it is not particularly surprising that the design of a machine differs from the implementations. But we must make a difference between designs and real machines, or there would never have been a purpose in the patent office refusing to patent perpetual motion machines. (If I have to explain that, then I apparently haven't yet laid out enough of my tools to do so. Again, bear with me here.)
It's easier to deal with machines if you know how you think they are supposed to behave. Then you can talk rationally about how the real behavior differs from the model. But that's design and implementation, not modeling.
For an example, consider a very simple single-transistor amplifier. It's output is dependent on three inputs, the input signal, the control signal (which determines how much to amplify the input signal) and the selection of the amplifier device. And the output is only dependent on those three inputs, never on the previous output. (Unless you have feedback control to reduce noise and such, but that wouldn't be simple.)
There are mathematical formulas that describe the relationship of input to output. Both the physical machines and the formulae are stateless. (Within the design specifications.)
Waaaaaaaait, you say. Selection of the device? Only a few special purpose amps allow that. That's not simple.
True. Setting those special purpose amps aside, we are talking about two separate machines here. One is the implemented machine. The selection of device is already done and can be ignored. Analyze it with two inputs, and you're probably done.
The other is the machine of the design -- the machine as it is designed. The design specifies a function, and any amp that fits that function can be substituted. And the substitution counts as an input.
These are two separate machines. Both have formulaic descriptions which are themselves models of machines, and therefore, in a mathematical sense, machines.
The implemented machine is an instance of the abstract machine of the design. The formulae of the implemented machine are (collectively) an instance of the machine of the design.
Perhaps you have seen an old cartoon, in one of the various forms in which it has been expressed, showing a child's swing as it goes through the processes of engineering and design typical in a large corporation. The swing as ordered by the customer (the lead engineer's child, perhaps?) is often depicted by an old tire hanging by a rope from a sturdy limb of a sturdy tree. The various incarnations of the design reflect the various permutations that the company being parodied push designs through, maybe with safety "features", maybe with ecological "features", maybe with special "engineering features" that essentially turn the function upside down or attempt to shave a few pennies off the cost. Something to think about and entertain yourself with for a moment.
For now, permit me to set this aside aside for a moment. Let's talk about adding states to the model and see if that might help us understand each other.