Lambda the Ultimate

The HandS book has all the issues you mention and then some. These issues are good things. It is tempting to make a list, but I don't want to spend that much time. "SP-partitions" are closed subset in contemporary math, or also "admissible" and there are even more closely related concepts, but each is a little different and adds something new. Co-algebra didn't exist in 1965 but you can read it between the lines, especially if you know a little contemporary model theory. This helps complete the book in a way that HandS never did.

One of the most interesting topics is "pair algebra" not covered anywhere else as far as I know. Pair algebras are Galois connections but stand on there own as an original innovation.

Of course the main theme, of several in the book, is parallel and serial decomposition. The HandS procedure is practical and what the book is known for.

There also seems to be a rough vision of the not yet existent field of Computer Science, but perhaps I am reading something into the book that is probably not intended.

cf Maler, On the Krohn-Rhodes Cascaded Decomposition Theorem for a presentation of some of these ideas in post-2009 vocabulary. From the archaeological discussion in this paper and in the same author's draft On the Cascaded Decomposition of Automata... it seems that even in the late 80's/early 90's engaging with the 1965 vocabulary had proven a substantial hurdle.

The Krohn-Rhodes theory is certainly difficult. But KR is quite different from HandS. KR is steeped in automata theory and semi-groups, HandS is common Universal Algebra with only a few vocabulary issues. It is easy to read in the year 2014. Both suffer from a lack of attention.

Edit: This is a nice book on the math associated with contemporary automata theory

I'd certainly like to read a review. The title sounds like something that'd make me pick it up off the library shelf. And any book which is good enough to get somebody lamenting its unpopularity and write a review about it is probably worth reading a review of.

By a structure theory for sequential machines, we mean an organized
body of techniques and results which deal with the problems of how sequential
machines can be realized from sets of smaller component machines, how
these component machines have to be interconnected, and how "information"
flows in and between these machines when they operate. The importance of
machine structure theory lies in the fact that it provides a direct link between
algebraic relationships and physical realizations of machines. Many structure
results describe the organization of physical devices (or component machines)
from which a given machine can be synthesized. Stated differently, the
structure theory describes the patterns of possible realizations of a machine
from smaller units. It should be stressed, however, that although many
structure theory results describe possible physical realizations of machines,
the theory itself is independent of the particular physical components or
technology used in the realization. More specifically, this theory is concerned
with logical or functional dependence in machines and studies the information
flow of the machine independently of how the information is represented
and how the logical functions are to be implemented.

The mathematical foundations of this structure theory rest on an algebraization
of the concept of "information" in a machine and supply the algebraic
formalism necessary to study problems about the flow of this information
in machines as they operate. The formal techniques and results are
very closely related to modern algebra. Many of its results show considerable
similarity with results in universal algebra, and some can be directly derived
from such considerations. Nevertheless, the engineering motivation demands
that this theory go its own way and raises many problems which require
new mathematical techniques to be invented that have no counterpart in
the development of algebra. Thus, this theory has a characteristic flavor and
mathematical identity of its own. It has, we believe, an abstract beauty
combined with the challenge and excitement of physical interpretation and
application. It falls squarely in the interdisciplinary area of applied algebra
which is becoming a part of engineering mathematics.

Based on the discussion we have been having I am going to go out on a limb and say what I think the problem is. It is an unusual argument so think about it before you jump to a conclusion.

In 1965 the world changed in such a fundamental way that HandS could no longer communicate the essential nature of their book. Above I have quoted the second and third paragraphs of the preface to "Algebraic Structure Theory of Sequential Machines". Because I was educated before 1965 and because I have actually studied Cybernetics I think I know what is being said, but I am willing to bet that you don't. It is not because you are dumb, it is because there has been a drastic change in the meaning of key words. These meaning changes were extensive, but in the above quote it is mainly the word machine (used 11 times) and the word information and the words analog, computer, and state not used but implicated. "

"Machine" and the other words have lost their sense. I am talking about the sense meaning that they derive from their use in Cybernetics. The facts seem to support this argument. After 1965 HandS is thought to be about "finite state machines" in the new sense of these words. But what about the old sense?

Computing in the Cybernetic sense can be described as the "analog method". A computer can be any "machine" in the Cybernetic sense. That is any determinate thing at all when it is used as an analogy for some other thing. Keep in mind that such analogies are key to the whole Cybernetic point of view. An electric circuit can be a computer for solving differential equations and thus a simulator for an F101-B. A slide rule with logarithmic scales can multiply numbers, and on and on. Even a human acting routinely with an effective method is a machine or a computer when acting in this capacity.

Hopefully now if you reread the above paragraphs you will understand the meaning of the book. When HandS say "the theory itself is independent of the particular physical components or technology used in the realization" they mean literally anything can serve as the computer. This includes software on a register machine.

OK, Now it is your turn. Does this make any sense at all? Am I as crazy as I actually feel right now?

I believe that I do, but if you tell me that the main words within them have non-standard meanings then I really have no way of substantiating that belief. I'll start with "machine" as it does seem to be quite central. In a modern definition there is no distinction between hardware and software. It is true that informally people use the term "machine" to refer physical hardware, but in a modern theoretical sense it simply means "a well defined method of computation with mechanical steps". This could relate to software (and often does) quite as easily as hardware. Turing Machines, FSMs and other definitions are not uniquely realisable as either hardware, or software. Indeed the term "mechanical" is in there specifically to make sure that they can be realised in either way. From your 3rd to last paragraph it sounds as if this is the same understanding of "machine" that you call the cybernetic view, does this seem to be correct?

"Information" might be more tricky. I can't offer a general definition for information. This is not because there is not one that is common, I assume that there probably is, but I am unfamiliar with it. Definitions of machines have cropped up constantly in CS from the undergraduate level onwards. But oddly enough, definitions of information have not, and I'm found that they tend to be implicit and unstated in many fields. I would summarise my understanding of information as "data that can be separated into discrete values, with a bijection between those values and bit-strings". I honestly couldn't estimate how common that definition would be. For a start it would certainly wouldn't apply to many fields that use analog values.

The two paragraphs are an interesting taster. Would it be correct to say that the book contains a formalism for expressing information flow between different machines, and derives sound operations that can be performed upon them?

Would it be correct to say that the book contains a formalism for expressing information flow between different machines, and derives sound operations that can be performed upon them?

Yes, but for me it is bigger and more significant.

but if you tell me that the main words within them have non-standard meanings then I really have no way of substantiating that belief

Do my extended comments help any?
Edit: Perhaps these are fairly big claims. Too much to come from only one person. I would much rather collaborate with others. Something this important will only matters when it comes from the group. Language is a cultural phenomenon. Individuals don't matter.

There is a lot of water under the bridge since HandS, we have all moved on. The future is surely a new work already under construction. Where it goes is anyone's guess. The only thing I know for sure is that understanding helps and discussion is always good.

Sorry about the delay, I missed one of your points.

Indeed the term "mechanical" is in there specifically to make sure that they can be realised in either way. From your 3rd to last paragraph it sounds as if this is the same understanding of "machine" that you call the cybernetic view, does this seem to be correct?

Yes, and I am glad to hear you express it that way. But a distinction can be, and often is made between hardware/software, or analog/digital, because we have the evidence of it.

Let me make an attempt at a blunt reply, in the hope of making my point very clearly -- but of course with no disrespect intended.

I think you are over-interpreting the situation. Sure, the wording is different, and we youngster certainly will have difficulties appreciating the fine details of considerations if they are strongly tied to the scientific context of 1965. But then, reading complicated texts on matters we don't understand as deeply as their authors is what we do all day.

When I read your first comment, I'm curious. "Pair algebra", maybe it's nice. But then maybe I don't have time to go try to find a non-paywalled copy of an old text some enthusiastic dude claims is interesting, which may or may not be relevant to my interest, while I have many other interesting things to do otherwise. More prose on the meaning of "machine" and "state" is not going to help me decide whether I want to have a look, and the default answer is "... probably you have something else to do".

I think that's why people have asked for a review, and I second that request. I think you've said more than enough about Cybernetics in an abstract fluffy way, and we're ready for a detailed summary of what is in the book, which part you found most interesting, and why.

What you're saying makes perfect sense to me -- well, I think so, anyway.

Let me take out the pre-1965 vocabulary for a spin and see how I do. Let me know if I run off the road.

Consider an old school "automatic door" such as on some grocery stores.

In front the door, on the ground, there is a "machine" that computes the downward force being exerted on a rubber mat in front of the door. There is a real world thing here -- an actual physical object or objects exerting force on the mat. The machine comprises some kind of sensor and some circuitry that "compute" (let's say) a voltage level that varies linearly with the amount of force on the pad, within nominal operating conditions.

This machine is a very simple "computer" using the "analog method" in the sense that the variations in voltage level on the output of the machine vary analogously to the force on the pad.

Perhaps there is another machine that physically projects a light beam across the plane of the door and computes voltage level analogous to the degree of opacity of whatever is near the threshold of the door.

Another pair of machines might be simple switches that translate the door's being fully closed, or fully open, into an open or closed circuit.

Some machine is a control circuit that aims to implement the designer's "logic" for how the door should operate.

Although the specific example of this door might be too simple to really show anything off, HaandS is a book that expresses an algebraic theory of how machines in this sense can be combined, such as into a complete "automatic door".

Digital circuits (in the modern sense) are (in the old sense) doing analog (old sense) computations of a sort where the information content is discrete and the physical realization is typically binary line levels.

At the level of combining digital machines through the lens of HaanDS, the partition between software and hardware within a component machine of some combination is unimportant.

Given a physical assembly of machines, there may be more than one partition of it into component machines that are combined in the HaanDS sense. The multiple partition possibilities are not constrained to be hierarchical or commensurate. The essential feature of any particular assembly and an analytic partition of that assembly is that the components compute using the analog method meaning that each component machine can be regarded as containing a state, meaning it is "at" some particular point in a space of analogues that it computes over -- and that information passes between these components.

Questions:

Is the above on the right track?

In what sense is the book using the word "sequential"?

Is the book using "information" in a Shannon sense (encompassing both discrete and continuous information, concepts like bandwidth, etc.)?

In "overview" terms: what are some typical interesting / useful theorems in this framework?

How did you arrive at your archeology of knowledge here? (Not many people look at things in those terms.)

Thanks for the help. It really is about as straight forward as you say. But of course this is only one example and the range of application depends only on one's ability to associate state with things. This is a big class of applications because the mathematical properties of state are inherent in space and time. In terms of HandS they represent information. Chapters 3, 4, 5, and 6 of the book are devoted to explaining this information relation in a unique way using their pair algebra innovation.

The essential feature of any particular assembly and an analytic partition of that assembly is that the components compute using the analog method meaning that each component machine can be regarded as containing a state, meaning it is "at" some particular point in a space of analogues that it computes over -- and that information passes between these components.

This is a nice idea because it lets us cross the 1965 line into the true world of state and information. From my point of view it isn't necessary because the HandS method and Cybernetics work fine without this artifact. The ASM methods could also be used up to a point.

In what sense is the book using the word "sequential"?

Is the book using "information" in a Shannon sense (encompassing both discrete and continuous information, concepts like bandwidth, etc.)?

In "overview" terms: what are some typical interesting / useful theorems in this framework?

How did you arrive at your archeology of knowledge here? (Not many people look at things in those terms.)

The most basic and well known are the serial and parallel decompositions theorems. There are quite a few. The book is thick with theorems. There are many pair algebra theorems stated something like this: "how much can we find out about the next state if we know only ... " and "how much do we have to know about the present state to compute ... about the next state." They leave no stone unturned. The last chapter deals with Krohn, Rhodes decompositions, but in a rather heuristic manner. There are theorems for various cases.

Could you please provide a little more motivation for why this particular vocabulary might serve better than its category-theoretical equivalents? For instance, making a snap judgement on the basis of a short introduction to and application of partition pairs, I don't immediately see anything that would not be better addressed, both for calculation and for communication, in the language of Galois connections⁰.

Another citation of H&S I ran across was in Conant and Ashby's 1970 "Every Good Regulator of a system must be a model of that system", but again it seems like it takes them 8 pages to conclude what is presented in 3 lines in Lawvere and Schanuel, as part of the introductory machinery leading up to the intended discussion of idempotents:

The idea comes from remembering¹ that whenever we met two finite sets A, B and a section-retraction pair, A -s-> B -r-> A with rs = 1_A, we saw that A was at most as big as B.

Finally, are Krohn-Rhodes decompositions as useful in practice as they are in theory? I was disappointed with them, ascribing their subsequent obscurity to the rather infelicitous property that if one attempts² a K-R decomposition of anything beyond a toy system, the number of states in the decomposition rapidly becomes much greater than that of the original system. In short, an early discovery of the Turing tarpit³ via ravioli code.

(The rôle of logic in software is easily motivated in modern language: when we look at a sequential process, what happens in between the transitions? Just as one can imagine an arbitrary (even infinite) number of identities stuck in between the non-identity members of a group (which are normally elided upon presentation), one can imagine any number of ineffective idempotent operations occurring in between the transitions⁴ (which we also normally elide), and hence we wish to talk about the the "states" in between observed transitions, we quickly discover that the language of idempotent algebras is very often Boolean)

<sub>0. As a homeostatic organism acting in an environment which makes distinctions between a variety of dialects, it usually behooves me to prefer the prestige dialect.
1. To be fair, it takes them 5 pages, pp.49-54 of "Conceptual Mathematics" to introduce the idea, but these once five pages cover the duality between section and retraction, touch on idempotents as the traces of section-retraction pairs, and discuss their composability.
2. Preferring to learn from the experience of others, rather than my own, I have not attempted this myself. If this result is not correct, it would be very interesting to see a counterexample!
3. Q. "Where are we?" A. "You're in a balloon!"
4. This is as widely applicable as "systems theory"; Murray Gell-Mann was (still is? My experience is decades removed...) just as preoccupied with the appropriate level of "chunking" in physics as we are in software, and Aristotle also often shows a meta-concern about treating subjects at the appropriate level of detail.</sub>

i hope there's room for many different ways of saying the same thing in life. like, i don't want categorical stuff to burn every single book from the cybernetic field. but then of course i also do want to know about the categorical stuff since it sounds like it is better in many ways. why can't we all get along? what i think we need more often is not that we gotta get rid of things, but people need to blog about the connections among things. we need people to show the cyberneticists and the category nerds that with the Dirty Hungaian Phrasebook we can figure out a little bit more what the "elephant" thing is we're all talking about.

Far from suggesting that abstract nonsense should burn away the cybernetic stuff (what would be the equivalent of Fahrenheit 451? Oersted 1100?), consider what I wrote above as a plea for someone (Hank?) from the cybernetics side to give an example or two where that language is better, so I can overcome the activation energy required to order a 13 Franc⁰ used copy of H&S. At this point, I am skeptical: for instance, in much the same way that Galileo's Two New Sciences is worth skimming (but today I would reach for different, non-geometric, tools to solve the same problems), I found Ashby interesting to skim (but today would think that examining something like Reflections on Trusting Trust¹ should provide more novelty ("variety") to anyone with a typical CS background, and furthermore the homeostatic implementation described in the latter is interesting precisely because it had made provision for operating, not just in a noisy, but in a downright "hostile"² environment) But again, the point of explaining where my bar for "interesting" is set is the hope that I might pleasantly surprised in having this skepticism turn out to be unfounded.

<sub>0. I am no stranger to peaceful coexistence of languages; living at a triple of point of cultures, I wind up using 3-5 natural languages daily. At the time, when I first moved here, I was consciously thinking of it as a Kauffman'ish "long-jump adaptation", and, sure enough, now that I have read Ashby I can see many of the ideas which informed Kauffman already present in the late 1940s, including that particular one, as "ultrastability".
1. note the publishing date! I find it difficult to believe that was entirely coincidental ... if perhaps more topical for us, now?
2. returning again to the 1950's, Shannon's outguessing machine is interesting because it is paradoxical: most people who find it difficult to beat this machine with nondeterministic "intelligent" play can easily beat it with a fully deterministic "dumb" strategy. How?</sub>

I am trying to figure out what the problem is here. You seem like a hard working person with no time to waste and you are frustrated with someone who wants to study feedback using decomposition, information, and pair algebra. Fair enough. But if you thought there was nothing going on here you could just ignore it, so I am thinking that you do suspect that something is going on. You seem to know the Cybernetic literature, and probably think it ended with "The Good Regulator Theorem". My simple answer is that there is at least one more important step that got lost in the chaos of the 1960's. The HandS book especially chapters 3, 4, 5, and 6.

Another point and my motivation for posting this is another discussion on Ltu about concurrency. This is only the most recent but the one that prompted me to mention HandS. I felt that what I was trying to say was not clear without discussing the contents of the book. I then began to worry about the age of the book and the conflicted nature of the contents, so here I we are trying to deal with that. In a forum like this it can't be avoided except by staying quiet.

In dealing with an old book there is an obvious need to suggest how to relate to contemporary methods. I see a model theory route, and a category theory route. But we must realize that the book is more than this. Judging from the preface the book is intended for a Cybernetic reader. That reader was probably lost by the time the book was published except for the subset of sequential circuit designers later to become FSM designers. Thus we can understand it's relative obscurity. The issue here is the philosophy of the book which I see as a Computer Science of Cybernetics. My conclusion is that "contemporary" issues like concurrency coupled with the fact that we don't even have a viable information theory without Cybernetics, unless you are ready for inconsistency robustness, means that we must take this seriously.

This would all be a lot easier if the book were on line. All it takes is for the right person to push the right button.

I don't immediately see anything that would not be better addressed, both for calculation and for communication, in the language of Galois connections0.

This is a nicely written paper which may answer your question.
Also, It might help if you could see how it is used in the book.
The last chapter is entitled "Senigroups and Machines" I thought Krohn-Rhodes was more descriptive because it is a generic for the whole field. The proof used in the book is due to Zeiger. Zeiger's proof uses methods developed by HandS in chapter 5, called "Set Systems" another information related concept. The simplicity of decompositions is discussed throughout the book. Good decompositions may have more states than the machine being decomposed.

Thank you. That is indeed an example which piques my interest. Do you see how (§3.3 Hoare Triples) he illustrates that, once one takes seriously the idea of automaton as algebraic object, the rôle of logic is almost forced⁰?

If you find the time to present any commentary on³ or review of⁴ a particularly interesting/useful theorem from H&S, highlighting where they go beyond either model or category theory, I would be grateful, and it seems likely a few other LTU'ers would be as well.

<sub>0. both at the point level, as predicates on states, and at the arrow level, where Hoare¹ Triples can be interpreted as an unusual syntax for the usual Kleene-algebraic semantics. (cf Backhouse on Conway Factors)
1. Floyd may have been unfashionable at the time because he worked in the language of flowcharts; anyone who has generated machine code will recognize that the basic problem remains the same, whether it be expressed in flowcharts or mutually recursive equations². Are you suggesting that H&S anticipated Floyd, and were unfashionable due to having been mistakenly pigeon-holed?
2. for which I find Hope was, in some ways, an improvement upon its successors...
3. Prentice Hall owns the particular cave-wall-silhouette by which H&S communicated; they don't own the abstract idea which was communicated. There is a legal pair algebra here, between encoding and signal, in which you have many rights in all jurisdictions of which I am aware.
4. In particular, if you are in a signatory to the Berne Convention, there has for many years been a real concept of fair use/fair dealing which can be put in fictional language: in playing the Glass Bead Game, it is a legal move to incorporate others' beads as murrine as long as the millefiori pattern of the resulting bead is one's own. (according to my reading of Hesse, these moves are, in fact, the point of a Glasperlenspiel)</sub>

A review would be interesting but first we need to clear un a few more definitional problems. My motivation is to grapple with the changes that are taking place in 1965. There are four big words that help to explain this change. If we get that much, many of the ensuing problems and issues since then make more sense. The words are machine which divides into software and hardware. The word "digital" goes from an obscure word meaning "digit" to an expression like "digital age". The word "analog" gains the new meaning of anything non digital. This brings us to the two central problems "state" and "information". These words are irreparably broken by the loss of the sense meaning of machine. Information and state interest me the most, and state is the key to information, Together they are the main theme of HandS.

Before 1965 state makes sense as the mathematical description of the machine, but when machine is divided, state looses its significance and becomes merely descriptive of the new hardware machine. At this point "information looses its body" because it has no definition in the new software paradigm. Information is defined by state and the old machine concept which is no longer viable. Of course Cybernetics is another casualty because it defines both state and machine in its own way. HandS may be the best definition of this embodied information.

The consequences of all this are far reaching. Before 1965 state has a central role in software. programs literally are state machines. Look at an old book on Dynamic Programming such as Bellman and Kalaba for instance. State and functionalism are central. But in 1965 functions loose their state and are no longer mathematically viable. Functional recursion violates Cantor's Theorem, This necessitates Dana Scott's Denotational semantics. At the same time Dynamic Programming goes from a general programming method to being an optimization method. In HandS there is a mathematics very similar to denotational semantics but using the word "state".

Another issue of interest to me is the opposition of hardware and software. The new paradigm creates a scale with hardware at one end and software at the other. There is always a tension between the two representations. C and Lisp for example. This issue may simply be an artifact of the new paradigm.

An issue that I don't understand very well is the role of Logic in the software paradigm. In Cybernetics it doesn't have the significance.

If you quote short sections of the book and add your own commentary, I'd enjoy this, and it seems covered by fair use as long as what you say has about as much substance as quoted parts. You won't interfere with demand for the whole work when the vast majority of it is not quoted. It seems like helpful advertising, so I hardly think anyone would complain about copyright. If nothing seems to be about programming languages, we can brainstorm a little about how some issue plays out in a PL context. We can ask quesions like, "Does programming devices involve anything more complex then sending them signals and modeling their expected behavior?"

My motivation is to grapple with the changes that are taking place in 1965.

What do you want to happen? That's the part of motivation I understand, but I don't get that from a desire to grapple with period changes. Understanding things is a good way to come up with new descriptions and models, which can be better at proposing more interesting problems to solve than ones hogging our attention at first. I guess you want to see through to a better layer for asking questions, but I'm not sure what you hope for yet. Is the role of state what you find most engaging in the book? (Your English is superb, but you want role instead of roll there.)

I was educated in the 70's and 80's, including a big autodidact part concurrent with high school and college, in which I read about cybernetics in the public library without getting a clear idea what authors thought they meant by that. The computer science degree I finished in 1990 doesn't shed much light on the early ideas. I guess discrete math, formal languages, and theory of finite automata mostly displaced earlier focus in modern curricula. (Discrete math was a blast. I often give an impression I don't like math, but I do, at least when it comes to arithmetic through calculus. I had sporadically eidetic memory when young, so memorizing stuff and working out consequences was easy. But I don't seem creative at real math beyond basic application.) Is there something you think was lost, that is not preserved by discrete math parts of a CS curriculum today? The word "digital" seems dominated by discrete for practical engineering purposes.

I like your willingness to tune definitions of terms in pursuit of clarity and insight when analyzing what might have been lost since the 60's. Rather than absolute meanings, words mean things relative to a context, such as a corpus of concepts that folks want to talk about, typically making distinctions in opposition to other ideas making sense in the same context. If you change context enough, old distinctions lose significance and word definitions need fixing to avoid dangling reference to missing parts from an original context. (Apologies, that was hard to say.) To re-tread what state means, you might want to outline the scope involved. If you wanted to go broadly outside software and hardware and include what people and systems are doing, you might need to go into configuration spaces to identify how much can be referenced by state in a model you imagine.

Programmers often refer to state as whatever is modeled by their programming language, or hardware configuration as far as it can be observed in software. Sometimes state is characterized as data in contrast to the behavior of code, even though code is also data when you process it as bit-strings. I like Andrew Moss's characterization of information as

"data that can be separated into discrete values, with a bijection between those values and bit-strings"

because that fits a model often assumed in software by professional programmers. But every word has a cluster of meanings that vary by context. A Shannon sense includes what you can infer from a signal even when fuzzy, like side channels we can observe despite not having been designed. Vibration patterns of a hard disk can tell you something about what it is doing, and can even be used to send Morse code if you try hard. A random non-technical coffee shop customer might define information as something that can be known, like contents of a report written by an army intelligence officer.

You might be interested in Karl Popper's three worlds ontology from Objective Knowledge (1972), because it has potential to put "information" in more places, including cultural products output by human minds, which he calls the third world. (First world: material things; second world: mental processes; third word: artifacts in the material world put there as a result of mental processes that affect both the material world and mental processes.) Early enthusiasts in cybernetics may have focused on what Popper called the third world. But unless you keep what you want to happen in mind, reading about philosophy can waste your time if it distracts you from solving problems you deem relevant.

Here I'll stop general comments and switch to online links to papers related to the book by Stearns and Hartmanis, in case this helps put that material in context, or helps give you ideas for further comment. [Edit: typos.]

[1] Harmanis, J. and R. E. Stearns, Algebraic Structure Theory of Sequential Machines, Englewood Cliffs, N.J.: Prentice-Hall, 1966.

That's [1] in http://www.pld.ttu.ee/~kruus/Web-Based%20System%20for_EUROCON_v5%20_1_3.pdf: Web-Based System for Sequential Machines Decomposition by Devadze, Fomina, Kruss, and Sudnitson (2003), which seems primarily about finite state machine (FSM) decomposition. The second paragraph references [1] above as follows:

Various techniques have been developed to enhance the capability and efficiency of decomposition, and they fall broadly into two categories: those based on the algebraic theory [1] and those based on the factorization or on the identification in the state transition graph of subroutines.

Searching further on Google, the following pdf appears in The International Workshop on Discrete-Event System Design, DESDes'01, with author names hard for me to parse because nationality uses an alphabet with slashes through L's. http://web.cecs.pdx.edu/~mperkows/PerkowskiGoogle/III-1.pdf is Functional Decomposition — the Value and Implication for Modern Digital Designing by Rawski, Luba, Jachna, and Rzechowski (2001), with reference [6] to Stearns and Hartmanis in the first paragraph:

Decomposition has become an important activity in the analysis and design of digital systems. It is fundamental to many fields of modern engineering and science [3], [6], [9], [16]. Functional decomposition relies on breaking down a complex system into a network of smaller and relatively independent co-operating sub-systems, in such a way that the original system's behavior is preserved, i.e. function F is decomposed to subfuction G and H in the form described by formula F = H(A, G(B)).

Huh, that quote from "relies on..." to "...preserved" reall doesn't to me narrow it down to just functional decomposition. That just sounds like sane decomposition, however it might be done (e.g. vs. object oriented).

I think Bertrand Meyer (tried to) eviscerate or puncture and deflate functional decomposition, and crow that object oriented decomposition is better. But of course I'm sure the jury will forever be out, hung, on that. :-)

I just quoted paragraphs containing the citations for Harmanis and Stearns. Both mention decomposition, but two data points aren't much. The issue of decomposition doesn't grab my attention. I haven't read Bertrand Meyer and have no comment on anything he's said. My intro to Lisp, Smalltalk, and C++ began in the late 80's, after several years of C. My interest in C++ was due to namespace and locality features, but not much else folks attribute to object oriented approaches in general. Many software philosophies seem like religions with zealots broadcasting noise that drowns out signal, until labels like OO draw random non sequiturs from passersby. Does your comment relate to the H&S book?

What do you want to happen?

What I would really like to see is the book "Algebraic Structure Theory of Sequential Machines" posted on line so people can see it for themselves. Personally I am interested in the book in the context of Cybernetics. Chapters 3, 4, 5, and 6 explain the pair algebra and apply it to the study of component machines and information. Chapter six "Feedback and Errors" explains the popular cybernetic idea of feedback in a unique way using information flows and the pair algebra. You must see it to believe it.

I will try to answer some of your other questions if I can add anything.

function F is decomposed to subfuction G and H in the form described by formula F = H(A, G(B)).

Note that this decomposition is a "dyadic hook" in J, where it would be expressed F = A (H G) B. The advantage of this notation is that it is a little less noisy than the compositional variant, F = (H • (1 × G))(A,B); the disadvantage is that there is no space between points of the syntactic constellation: any sequence of functions means something, so fat-fingered typos tend to produce something executable instead of a readily diagnosable syntax error.

A comment about the University of Tallinn notes. I am grateful and impressed with the hard work they are doing with the HandS theory. I remember looking at these notes a few years ago. My impression is that they have made tremendous progress in making much of the book contemporary and up to date. One wonders if they might have some connection to Hartmanis himself, since Hartmanis is native of Latvia a neighbor of Estonia. If so perhaps they could post the entire book?

I meant for this to be a response to Andrew Moss above.