Method and system for process expression and resolution including a generally and inherently concurrent computer language

Abstract

A method and system for process expression and resolution is described. A first language structure comprising a possibility expression having at least one definition which is inherently and generally concurrent is provided. Further, a second language structure comprising an actuality expression including a fully formed input data name to be resolved is provided. Furthermore, a third language structure comprising an active expression initially having at least one invocation, the invocation comprising an association with a particular definition and the fully formed input data name of the actuality expression is provided. Subsequently, the process of resolving invocations begins in the active expression with fully formed input data names in relation to their associated definition to produce at least one or both of the following: (1) an invocation with a fully formed input data name and (2) a result data name.

Claims

What is claimed is:

1. A method of process expression and resolution, comprising the steps of:

(a) providing a first language structure comprising a possibility expression having at least one definition which is inherently and generally concurrent;

(b) providing a second language structure comprising an actuality expression including a fully formed input data name to be resolved;

(c) providing a third language structure comprising an active expression initially having at least one invocation, the invocation comprising an association with a particular definition and the fully formed input data name of the actuality expression; and

(d) resolving invocations in the active expression with fully formed input data names in relation to their associated definition to produce at least one or both of the following: (1) an invocation with a fully formed input data name and (2) a result data name.

2. The method of claim 1 wherein the first, the second and the third language structures are derived from a set of production rules selected from the group consisting essentially of: a set of metasymbols, a set of terminals and a set of nonterminals.

3. The method of claim 2 wherein the set of metasymbols comprise metasymbols selected from the group consisting essentially of:

(a) = term to structure equivalence;

(b) .vertline. OR;

(c) * zero or more (post superscript);

(d) + one or more (post superscript);

(e) *+ zero or one (post superscript); and

(f) - followed by.

4. The method of claim 2 wherein the set of terminals comprise a set of syntax symbols and a set of at least two value symbols disjoint from the set of syntax symbols.

5. The method of claim 4 wherein the set of syntax symbols comprise syntax symbols selected from the group consisting essentially of: `(`, `)`, `[`, `]`, `{`, `}`, `<`, `>`, `,`, `;`, `*`, `@`, `!`, ` `, `/`, `?`, and `#`.

6. The method of claim 2 wherein the set of nonterminals comprise nonterminals selected from the group consisting essentially of:

phrase, clause, redefinition, resultant, invocation, delayedinvoc, invocname, resultlist, resultlink, actualist, actual, resultref, definition, nonreplicable, body, formalist, namelist, object, objectstruct, formalref, defname, formalname, linkname, and narrative.

7. The method of claim 2 wherein each production rule comprises either (1) a nonterminal followed by a term to structure equivalence (=) followed by a terminal or a nonterminal, (2) a nonterminal followed by a term to structure equivalence (=) followed by a plurality of terminals delimited by metasymbols, (3) a nonterminal followed by a term to structure equivalence (=) followed by a plurality of nonterminals delimited by metasymbols, or (4) a nonterminal followed by a term to structure equivalence (=) followed by at least one terminal and at least one nonterminal delimited by metasymbols.

8. The method of claim 7 wherein:

(a) the set of metasymbols comprise metasymbols selected from the group consisting essentially of:

(i)= term to structure equivalence;

(ii) .vertline. OR;

(iii) * zero or more (post superscript);

(iv) + one or more (post superscript);

(v) *+ zero or one (post superscript); and

(vi) - followed by;

(b) the set of terminals comprise:

(i) a set of syntax symbols comprising syntax symbols selected from the group consisting essentially of: `(`, `)`, `[`, `]`, `{`, `}`, `<`, `>`, `,`, `;`, `*`, `@`, `!`, ` `, `/`, `?`, and `#`; and

(ii) a set of at least two value symbols disjoint from the set of syntax symbols; and

(c) the set of nonterminals comprise nonterminals selected from the group consisting essentially of:

value, phrase, clause, redefinition, resultant, invocation, delayedinvoc, invocname, resultlist, resultlink, actualist, actual, resultref, definition, nonreplicable, body, formalist, namelist, object, objectstruct, formalref, defname, formalname, linkname, and narrative.

9. The method claim 8 wherein the first, the second and the third language structures are derived from a set of production rules selected from the group consisting essentially of:

(a) value=at least two value symbols

(b) phrase=clause .vertline. phrase; clause .vertline. phrase?clause

(c) clause=redefinition*-resultant *-invocation*+-object*

(d) redefinition=invocname@(phrase)

(e) resultant=linkname<phrase>

(f) invocation=invocname (actualist-resultlist)

(g) delayedinvoc=invocname#(actualist-resultlist)

(h) invocname=invocation.vertline.defname-formalref* .vertline.defname*+-formalref+

(i) resultlist=resultlink*

(j) resultlink=<linkname>

(k) actualist=actual.vertline.actualist,actual

(l) actual=invocation*+-object*-resultref*+

(m) resultref=$linkname

(n) definition=defname [(formalist-resultlist)body]

(o) nonreplicable=defname@[(formalist-resultlist)body]

(p) body=phrase.vertline.phrase;definition+

(q) formalist=namelist.vertline.namelist,!.vertline.!, namelist

(r) namelist=formalname.vertline.namelist, formalname

(s) object=value* .vertline.value*-formalref+.vertline.objectstruct

(t) objectstruct={object}.vertline.{phrase}.vertline.{objectstruct*}

(u) formalref=*formalname.vertline.*!

(v) defname=value+

(w) formalname=value+

(x) linkname=value+

(y) narrative= any character string /.

10. The method of claim 1 wherein the step of resolving comprises simultaneously resolving multiple invocations in the active expression until all of the invocations have been resolved and a fully formed result data name is left in the active expression.

11. A process expression and resolution system, comprising:

(a) first language structure comprising a possibility expression having at least one definition which is inherently and generally concurrent;

(b) second language structure comprising an actuality expression including a fully formed input data name to be resolved;

(c) third language structure comprising an active expression initially having at least one invocation, the invocation comprising an association with a particular definition and the fully formed input data name of the actuality expression; and

(d) resolution means for resolving invocations in the active expression with fully formed input data names in relation to their associated definition to produce at least one or both of the following: (1) an invocation with a fully formed input data name and (2) a result data name.

12. The process expression and resolution system of claim 11 wherein the first, the second and the third language structures are derived from a set of production rules selected from the group consisting essentially of: a set of metasymbols, a set of terminals and a set of nonterminals.

13. The process expression and resolution system of claim 12 wherein the set of metasymbols comprise metasymbols selected from the group consisting essentially of:

(a)= term to structure equivalence;

(b) .vertline. OR;

(c) * zero or more (post superscript);

(d) + one or more (post superscript);

(e) *+ zero or one (post superscript); and

(f) - followed by.

14. The process expression and resolution system of claim 12 wherein the set of terminals comprise a set of syntax symbols and a set of at least two value symbols disjoint from the set of syntax symbols.

15. The process expression and resolution system of claim 14 wherein the set of syntax symbols comprise syntax symbols selected from the group consisting essentially of: `(`, `)`, `[`, `]`, `{`, `}`, `<`, `>`, `,`, `;`, `*`, `@`, `!`, ` `, `/`, `?`, and `#`.

16. The process expression and resolution system of claim 12 wherein the set of nonterminals comprise nonterminals selected from the group consisting essentially of:

phrase, clause, redefinition, resultant, invocation, delayedinvoc, invocname, resultlist, resultlink, actualist, actual, resultref, definition, nonreplicable, body, formalist, namelist, object, objectstruct, formalref, defname, formalname, linkname, and narrative.

17. The process expression and resolution system of claim 12 wherein each production rule comprises either (1) a nonterminal followed by a term to structure equivalence (=) followed by a terminal or a nonterminal, (2) a nonterminal followed by a term to structure equivalence (=) followed by a plurality of terminals delimited by metasymbols, (3) a nonterminal followed by a term to structure equivalence (=) followed by a plurality of nonterminals delimited by metasymbols, or (4) a nonterminal followed by a term to structure equivalence (=) followed by at least one terminal and at least one nonterminal delimited by metasymbols.

18. The process expression and resolution system of claim 17 wherein:

(a) the set of metasymbols comprise metasymbols selected from the group consisting essentially of:

(i)= term to structure equivalence;

(ii) .vertline. OR;

(iii) * zero or more (post superscript);

(iv) + one or more (post superscript);

(v) *+ zero or one (post superscript); and

(vi) - followed by;

(b) the set of terminals comprise:

(i) a set of syntax symbols comprising syntax symbols selected from the group consisting essentially of: `(`, `)`, `[`, `]`, `{`, `}`, `<`, `>`, `,`, `;`, `*`, `@`, `!`, ` `, `/`, `?`, and `#`; and

(ii) a set of at least two value symbols disjoint from the set of syntax symbols; and

(c) the set of nonterminals comprise nonterminals selected from the group consisting essentially of:

value, phrase, clause, redefinition, resultant, invocation, delayedinvoc, invocname, resultlist, resultlink, actualist, actual, resultref, definition, nonreplicable, body, formalist, namelist, object, objectstruct, formalref, defname, formalname, linkname, and narrative.

19. The process expression and resolution system of claim 18 wherein the first, the second and the third language structures are derived from a set of production rules selected from the group consisting essentially of:

(a) value=at least two value symbols

(b) phrase=clause.vertline.phrase;clause.vertline.phrase?clause

(c) clause=redefinition*-resultant*-invocation*+-object*

(d) redefinition=invocname@(phrase)

(e) resultant=linkname<phrase>

(f) invocation=invocname(actualist-resultlist)

(g) delayedinvoc=invocname#(actualist-resultlist)

(h) invocname=invocation.vertline.defname-formalref* .vertline.defname*+-formalref+

(i) resultlist=result link*

(j) resultlink=<linkname>

(k) actualist=actual.vertline.actualist,actual

(l) actual=invocation*+-object *-resultref*+

(m) resultref=$linkname

(n) definition=defname[(formalist-resultlist)body]

(o) nonreplicable=defname@[(formalist-resultlist)body]

(p) body=phrase.vertline.phrase;definition+

(q) formalist=namelist.vertline.namelist,!.vertline.!,namelist

(r) namelist=formalname.vertline.namelist,formalname

(s) object=value*.vertline.value*-formalref+.vertline.objectstruct

(t) objectstruct={object}.vertline.{phrase}.vertline.{objectstruct*}

(u) formalref=*formalname.vertline.*!

(v) defname=value+

(w) formalname=value+

(x) linkname=value+

(y) narrative= any character string /.

20. The process expression and resolution system of claim 11 wherein the resolution means comprises means for simultaneously resolving multiple invocations in the active expression until all of the invocations have been resolved and a fully formed result data name is left in the active expression.

Description

FIELD OF THE INVENTION

The present invention relates to a process expression and resolution system and more particularly, to a computer language which is generally and inherently concurrent thereby enabling concurrent processing within a computer system.

BACKGROUND OF THE INVENTION

The last several years of the computer age have been years of dramatic technological progress. Computers have permeated the fabric of society and become indispensable to commerce and government. They have rapidly become more powerful while at the same time becoming smaller and cheaper. Computer system technology has evolved through four generations. Innumerable programming languages have been implemented and the discipline of programming has gone through at least one revolution.

During this era of dramatic technical progress one aspect of computing has progressed imperceptibly if at all. The theoretical understanding of computers and computing remains pretty much as it existed 45 years ago and it has had very little influence on the general progress of other aspects of computing. Almost all of this progress is due to improved technology, direct experience and native inventiveness.

"The theory of computer science" is largely a collection of mathematical models and conceptual viewpoints, most of which existed before the first digital computer was built. These different models such as, automata theory, the Turing machine and formal languages all ask questions about issues of computability and revolve around the notion of the algorithm. The questions of computability address the foundations of mathematics itself and deal with the limits of what can be computed with various symbol manipulation rule systems embodied in computational devices such as machines and languages. To understand "the theory of computer science" it is necessary to understand the notion of the algorithm.

The notion of the algorithm is fundamental to mathematics. To understand the significance of the notion to mathematics it is necessary to understand the history of its development. The term itself derives from the name of ninth century Persian mathematician named Mohammed ibn Musa al-Khowarizmi. In about 825 A.D., he wrote a small book describing how to calculate with a new ten symbol, positional value number system developed in India. The book described simple procedures for carrying out addition, subtraction, multiplication and division in the new system. Around 1120 A.D., this small book was translated into Latin under the title Liber Algorismi de numero Indorum (The Book of al-Khowarizmi on the Hindu number system). This translation of the book was widely distributed in Europe and it introduced the Hindu-Arabic number system to Europe. By the mid thirteenth century, al-Khowarizmi had been forgotten but the term algorism (Latin for al-Kowarizmi's book) had come generally to refer to computation in the new number system. At this time, an algorism was any book related to the subject. The algorisms were the four arithmetic operations. An algorist was a person who calculated in the new number system as opposed to an abacist who used an abacus. By 1500 A.D., the algorists had prevailed and the abacists had largely disappeared.

These algorisms were strictly mechanical procedures to manipulate symbols. They could be carried out by any person by mechanically following simple rules, even though the person had no understanding of the theory of operation, the person needed no cleverness to determine a correct answer. Computing with Roman numerals on the other hand required considerable skill and ingenuity. At this time, other examples of mechanical formulation existed such as Euclid's method to find the greatest common denominator of two numbers. The use of simple mechanical computation fascinated the medieval mathematicians. They wondered if it was possible that the whole of mathematics or even all of human knowledge could be mechanically formulated and calculated with simple rules of symbol manipulation.

Leibniz failed in an attempt to complete just such a formulation in the 1660s with his calculus ratiocinator or characteristica universalis. The object of Leibniz was to "enable the truths of any science, when formulated in the universal language, to be computed by arithmetical operations". Insight, ingenuity and imagination would no longer have been required in mathematics. After Leibniz's failure the idea lay fallow for two hundred years.

When the dream of formalizing thought with mechanical procedures in symbols reemerged with the symbolic logic of George Boole in 1854, it had stiff competition to overcome in the form of Euclidian geometry. Euclidian geometry, with its axioms and rules of reasoning from the simple to the complex was the established model of intellectual thought in the western world. In the 1680's, after the discovery of analytical geometry and having made new discoveries with his own invention of fluxional calculus, Newton was careful to cast all the mathematical demonstrations in his presentation of these new discoveries in classical Greek geometry. At the time, a symbolic analytical presentation would neither have been understood nor accepted.

Late into the nineteenth century symbolic computation was distrusted and discounted. Geometry, dealing with relationships among points, lines and surfaces, was intuitive, obvious and clear whereas algebra dealt with arbitrary symbols related by arbitrary rules that did not relate to any specific reality. The attitude is exemplified by a nineteenth century astronomer who remarked that he had not the "smallest confidence in any result which is essentially obtained by the use of imaginary symbols".

Toward the end of the nineteenth century Euclidian geometry lost its philosophical preeminence and symbolic computation emerged as the model of intellectual thought. The fall of geometry was precipitated by Bolyai, Gauss, Lobachevski and Riemann with the development of non Euclidian geometries which were internally consistent and therefore just as valid a mathematical system as Euclidian geometry. The rise of symbolic computation was nurtured by Boole, Peirce, Schroder, Peano and Frege who were trying to establish acceptable foundations for symbolic logic. These two streams of endeavor culminated in Hilbert's rigorization of Euclidian geometry in terms of algebra in Grundlagen der Geometrie (Foundations of Geometry) published in 1899 which emphasized the undefined nature of the axioms. "One must be able to say at all times-instead of points, straight lines and planes- tables, chairs and beer mugs". Euclidian geometry was after all just one of many possible axiomatic symbolic computation systems.

As the twentieth century dawned, symbolic computation had been established as the arena of mathematical theorizing and axiomatic systems provided the rules of the game. The mathematicians were hot on the trail of settling the game once and for all. They seemed to be on the verge of fulfilling Leibniz's dream of the universal symbolic language that would proffer absolute certainty and truth.

This quest was led by David Hilbert, who outlined a program to settle once and for all the foundational issues of mathematics. The program focused on the resolution of three questions.

1. Was mathematics complete in the sense that every statement could be proved or disproved?

2. Was mathematics consistent in the sense that no statement could be proved both true and false?

3. Was mathematics decidable in the sense that there existed a definite method to determine the truth or falsity of any mathematical statement?

This definite method of decidability was the modern incarnation of Leibniz's arithmetical operations of his universal symbolic language.

Hilbert firmly believed that the answer to all three questions was `yes`, and the program was simply one of tidying up loose ends. Hilbert was convinced that an unsolvable mathematical problem did not exist, "every mathematical problem must necessarily be susceptible to an exact statement, either in the form of an actual answer to the question asked , or by the proof of the impossibility of its solution".

In 1931, Kurt Godel demonstrated that any axiom system expressive enough to contain arithmetic could not be both complete (there existed statements that could not be proved either true or false) and consistent (free of contradictions) in the terms of the axiom system. This result was the death knell for Hilbert's program. The answers to the first two questions were no. There remained the question of decidability. The entscheidungsproblem as Hilbert termed it. After Godel proved that unsolvable problems (unprovable theorems) could exist in an axiom system, the decidability problem became a search for a definite method to determine if a given problem was solvable or unsolvable in a given axiom system.

The decidability problem appealed directly to the notion of a definite method which was also referred to as an effective procedure or a mechanical procedure. This notion had always been fundamental to mathematics but had been intuitively accepted and had not been a subject of investigation itself. In essence, a person should know an effective procedure when that person sees one. But, to demonstrate something about the nature of effective procedures there must be a precise characterization of what constitutes an effective procedure.

Hilbert made it clear what constituted an acceptable mathematical solution in his 1900 paper posing 23 problems which he considered important to the future of mathematics.

"that it shall be possible to establish the correctness of a solution by means of a finite number of steps based upon a finite number of hypotheses which are implied in the statement of the problem and which must always be exactly formulated"--David Hilbert.

Satisfactorily characterizing this notion of effective or mechanical procedure became an important foundational issue in mathematics and several mathematicians applied themselves to the problem. Among them were Herbrand and Godel, Post, Turing, Church and Markov. Each had a totally different characterization of effective computability which were all shown later to be logically equivalent. In 1936, both Church with his lambda calculus and Turing with his machine proved that no effective procedure existed to determine the provability or unprovability of a given mathematical problem. Therefore, the answer to Hilbert's third question was also `no` Leibniz's calculus ratiocinator with its arithmetical resolution of all questions was not possible. Thus, ingenuity, insight and imagination cannot be done away with in mathematics after all.

Questions of effective computability have continued to be a fundamental concern of mathematicians. Through the 1940s and 1950s A. A. Markov tried to consolidate all the work of the other mathematicians on effective computability by introducing the term algorithm with its modern meaning as a name for his own theory of effectively computable functions. In the translated first sentence of his 1954 book Teoriya Algorifmov (Theory of Algorithms) he states:

"In mathematics, "algorithm" is commonly understood to be an exact prescription, defining a computational process, leading from various initial data to the desired result"--A. A. Markov.

The term algorithm was not, apparently, a commonly used mathematical term in America or Europe before Markov, a Russian, introduced it. None of the other investigators, Herbrand and Godel, Post, Turing or Church used the term. The term however caught on very quickly in the computing community. In 1958 a new programming language was named ALGOL (ALGOrithmic Language). In 1960 a new department of the Communications of the ACM (Association for computing machinery) was introduced called "Algorithms".

Historically, the notion of the algorithm was developed to investigate the foundations of mathematics and has evolved in relation to the needs of mathematicians. The algorithm in mathematics is a limiting definition of what constitutes an acceptable solution to a mathematical problem. It is the foundational notion of what mathematics is all about and Turing's machine emerged as the preferred definition of the algorithm for mathematicians.

When the computer emerged in 1945, its birth was attended by two professional groups; electrical engineers and mathematicians. It was inevitable that the theoretical aspects of this newly emerging phenomena would be established by the mathematicians. One of these mathematicians, John Von Neumann, was a student of Hilbert's and a significant contributor to his program to resolve the foundations of mathematics.

The computer did mathematical computation, it computed one step at a time and each step was precisely defined. Mathematics already had an established theory of computability and a machine model of computation (the Turing machine) that proceeded one precisely defined step at a time. The notion of the algorithm was quite naturally adopted by those theorizing about computers as a fundamental paradigm. This activity eventually came to be called "the theory of computer science."

Many attempts have been made to define computer science. These definitions view computer science as a heterogeneous group of disciplines related to the creation, use and study of computers. A typical definition simply offers a list of included topics such as: computability, complexity, algorithm theory, automata theory, programming, high level languages, machine languages, architecture, circuit design, switching theory, system organization, numerical mathematics, artificial intelligence, other applications, etc. One definition attributed to H. Zemanek is relatively concise and suggests that computer science consists of four distinct theoretical domains. He said that computer science is:

1. A theory of programming, with emphasis not mainly on the problems of distinguishing the computable from the noncomputable, but rather on a practical theory of algorithms concerned with the construction of economical and efficient programs;

2. A theory of process and processor organization, which takes into account the finite dimensions of existing memories, the availability of storage hierarchies of varying access speeds and costs, and the desire for a reduction in computation and program production time;

3. A theory of description for processes and computational structures in terms acceptable to the processor; and

4. A theory of computer applications which would include all features common to most numeric and nonnumeric applications.

The most recent and comprehensive survey of the attempts to define computer science is an article in the Annals of the History of Computing.

Computer science appears to consist of a quite disparate group of disciplines. There is the theorist concerned with formalized machines, the hardware engineer concerned with logic circuits, the software engineer concerned with symbolic expressions, the architect concerned with dynamic interpreting structures, the systems programmer concerned with interacting processes and the user concerned with his own unique problem. This fragmented face of computer science seems to be a generally accepted inevitability.

Can an underlying commonality of concern be discovered among these several disciplines and possibly, a conceptual focus for computer science? Item (1) in the above list is concerned with programming, which is the rendering of symbolic process expression. Item (2) is concerned with processor organizations, which is an expression of a process to interpret symbolically expressed processes. Item (3) is directly concerned with symbolic process expressions. Item (4) is concerned with process expression in general. All of the disciplines that are included under the heading of computer science in any list are concerned in one way or another with the creation, expression, or actualization of process expressions. A logic circuit is an expression of a process that can happen all by itself. An architecture is an expression of a continuously acting process to interpret symbolically expressed processes. A program is a symbolic expression of a process. A programming language is an environment within which to create symbolic expressions. A compiler is an expression of a process that translates between symbolic expressions in different languages. An operating system is an expression of a process that manages the interpretation of other process expressions.

Computer science can be viewed as primarily concerned with questions about the expression of processes and the actualization of those expressions. What are the all the possible ways a process can be expressed? Are some expressions superior in any sense to other expressions? What are all the possible ways of actualizing an expression. Are there common conceptual elements underlying all expressions? What is the best programming language? How can the best program be formulated? How can the best architecture be built? What is the best implementation environment? These are the questions that occupy computer scientists and they all revolve around the nature of process expression.

Mathematicians, on the other hand, are primarily interested in exploring the behavior of specific processes or classes of process. They bypass general problems of expression by appealing to a very formal and minimalized model of expression; the algorithm as characterized by the Turing machine. They are only interested in whether an expression is possible and whether it conforms to certain specific properties. They are not interested in all the possible ways of rendering an expression of the process and actualizing it. This, however, is precisely what computer scientists are interested in.

Mathematics is primarily concerned with the nature of the behavior of process regardless of how that process is expressed. Computer science is primarily concerned with the nature of the expression of processes regardless of what particular process might be expressed. This core concern with the nature of expression itself is the unique conceptual focus that distinguishes computer science from the other sciences and from mathematics. Computer science is the science of expression.

One published definition of computer science comes near the mark.

"computer science itself becomes no more (and no less) than the discipline of constructing appropriate descriptive languages"--Harold Abelson, Geraly Jay Sussmann, and Julie Sussmann.

The notion of the algorithm has become firmly established as a fundamental conceptual paradigm of "the theory of computer science."

"The notion of the algorithm is basic to all computer programming . . . "--Donald E. Knuth.

" . . . the basic concept of problem solving on the computer--the algorithm"--M.S. Carberry, H. M. Khalil, J. F. Leathrum and L. S. Levy.

" . . . the notion of the algorithm is essential to computer programming"--Kurt Maly and Allen R. Flanson.

"One of the concepts most central to computer science is that of an algorithm"--Zenon W. Pylyshyn.

Introductory texts on computer science often begin with a chapter on the notion of the algorithm. The following generally covers the etymology of the word and a definition of the notion which consists of a belabored list of properties which an expression must satisfy to qualify as an algorithm. An issue conspicuously absent from these introductory chapters is how the notion contributes to the resolution of significant problems of computer science. In the remaining chapters of these texts, there is typically no further appeal to the notion of the algorithm and rarely even a usage of the word itself. The notion is never or very rarely appealed to in texts on logic design, architecture, operating systems, programming, software engineering, programming languages, compilers, data structures and data base systems.

Is the notion of the algorithm really a fundamental concept of computer science? Is it just pretentious but harmless window dressing or has the notion actually been detrimental to the growth and development of computer science? Does "the theory of computer science" have anything to do with computer science?

Computer science texts typically define the notion of the algorithm by simply presenting a list of qualifying properties for an algorithm. In particular, an algorithm:

1. Must be a step by step sequence of operations

2. Each operation must be precisely defined

3. It must terminate in a finite number of steps

4. It must effectively yield a correct solution

5. It must be deterministic in that given the same input it will always yield the same solution

These properties are substantially similar to what Hilbert proposed in 1900 and it is easy to see how this list of restrictive characteristics serves to define what is acceptable as a mathematical solution, but what is its significance in computer science?

The notion of the algorithm demarcates all expressions into algorithm and non-algorithm but, what purpose does it serve to know that one program is an acceptable mathematical solution and another is not? Is the expression of one fundamentally different from the expression of the other? Is one interpreted differently from the other? Is a different machine required for one than the other? Do operations ordered in strict sequence somehow work better than operations ordered with concurrency? Are algorithms first class citizens in some sense and non-algorithms second class citizens? Most existing programs are considered "unacceptable" mathematical solutions.

Important types of programs in computer science do not qualify as algorithms. An operating system is not supposed to terminate nor does it yield a singular solution.

It cannot be deterministic because it must relate to uncontrolled inputs from the outside world. Any program utilizing random input to carry out its process such as a monte carlo simulation or fuzzy logic simulation is not an algorithm. Many programs and computers utilize concurrency where many operations are carried out simultaneously. Are these not algorithms? If a formerly sequential program qualifying as an algorithm is parallelized by a vectorizing compiler, is it no longer an algorithm? No program with a bug can be an algorithm and it is an accepted truism that no significant program can be demonstrated to be bug free.

Does determining whether a given expression is an acceptable mathematical solution or not, help to identify the expression that is most readable, most efficient, fastest or easiest to interpret? Does such a distinction aid in building better computer systems or in writing better programs?

These difficulties with the notion of the algorithm have not gone unnoticed. The following observations about algorithms are quotations from various sources.

" . . . there is an extension of the notion of algorithm (called nondeterministic algorithms)"--M. S. Carberry, H. M. Khalil, J. F. Leathrum and L. S. Levy.

"Any computer program is at least a semi-algorithm and any program that always halts is an algorithm"--R. R. Karthage.

"There is another word for algorithm which obeys all of the above properties except termination and that is computational procedure"--Ellis Horowitz and Sartaj Sahni.

"An algorithm A is a probabilistically good algorithm if the algorithm "almost always" generates either an exact solution or a solution with a value that is "exceedingly close" to the value of the optimal solution"--Benjamin W. Wah and C. V. Ramamoorthy.

"The procedure becomes an algorithm if the Turing machine always halts"--Kurt Maly and Allen R. Hanson.

"By admitting probabilistic procedures in algorithms . . . "--F. S. Beckman.

" . . . if, after executing some step, the control logic shifts to another step of the algorithm as dictated by a random device (for example, coin tossing), we call the algorithm random algorithm"--E. V. Krishnamurthy.

"An algorithm which is based on such convergence tests is called an infinite algorithm"--E. V. Krishnamurthy.

"Algorithms that are not direct are called indirect"--John K. Rice and John R. Rice.

"We drop the requirement that the algorithm stop and consider infinite algorithms"--John K. Rice and John R. Rice.

These people have sensed an inappropriate discrimination or simply an incompleteness and proposed a remedy. Programs that do not terminate, are not deterministic and do not give specific solutions are now "included." They are no longer simply non-algorithmic they have positive labels, but what has been achieved by this labeling? Do these new labels provide any useful conceptual discrimination? A non-algorithm by any other name is still just an expression that, however useful it might be in other contexts, is unacceptable as a mathematical solution.

Computer science does not have the same view points as mathematics. Computer science is not in pursuit of solely mathematical solutions, it is in pursuit of a general understanding of process expression. Algorithm, non-algorithm is simply not the kind of conceptual discrimination that is useful in computer science. The notion of the algorithm has not discouraged anyone from creating nondeterministic, nonterminating, incorrect or otherwise unacceptable expressions nor has it aided anyone in creating better programs or computers.

The problem is that the notion of the algorithm taken out of its mathematical context has been used for duties it was never intended to fulfill. The notion of a sequence of operations was considered by the mathematicians as an adequate and simple rendering of process expression and for their purposes indeed it was adequate. It was never intended to be a paradigm of process expression in general. Unfortunately, this is the role it came to serve in computer science.

So how does the notion of the algorithm fare purely as a model of process expression? The definition of the algorithm states that a process expression should be a strict one with a time sequence of precisely defined operations. It does not suggest what an operation is or how one should be precisely defined. It is, however, in this precise definition of the operation that the basic questions of expression must be addressed. How is the input data and output data characterized? Just how does the input data turn into output data? How does the data of one operation relate to the data of another operation? The notion of the algorithm addresses none of these issues. It just states that operations must be precisely defined. This unsupported imperative is at once an admission of expressional incompleteness and a refusal to be complete.

In whatever manner operations manage to get defined the notion of the algorithm specifies that they should be arranged in strict sequence. The only formal relationship between operations that the notion of the algorithm admits is that of sequential order. Is this notion of arranging operations in sequence fundamental or necessary in any sense?

The notion of a sequence of precisely defined operations is more familiarly known as the sequential process model. The sequential process is the informal version of the algorithm without the operational strictures of termination, effectiveness and determination. Sequentiality is generally considered a necessary theoretical primitive of process expression. Concurrency, for instance, is viewed as a secondary property derived from sequentiality. Several of the following quotes convey the general attitude on concurrency.

"It (a concurrent program) consists of several sequential processes whose execution sequences are interleaved."--Ben-Ari M. Ben-Ari.

"We will build concurrent programs out of sequential processes that are executed simultaneously."--Per Brinch Hansen.

"(sequential) Processes are called concurrent if their execution overlap in time."--Per Brinch Hansen.

" . . . parallel composition of communicating sequential processes is a fundamental program structuring method."--C. A. R. Hoare.

There is much that is sequential in dealing with computers, but is this sequentiality conceptually fundamental or just an artifact of the way we happen to currently be building computers and thinking about mathematics?

In actuality, single event sequentiality is derived from continuously functioning concurrent elements. Computers are built from logic circuits which in turn are built of networks of continuously and concurrently operating logic gates. There is nothing sequential about a combinational logic circuit. Many circuits operate concurrently to carry out one sequential operation of a computer. The most primitive operations of any process expression must occur concurrently. Consider the construction of a logic circuit in which the logic gates operate strictly one at time sequentially. The logic gates cannot sequentialize themselves so a sequential controller must be postulated. But this controller itself must also be constructed in terms of strictly sequential operational units which will in turn need a sequence controller. The most primitive operations of any process must be expressed in concurrently proceeding relationships. They cannot be expressed strictly sequentially.

The notion of the algorithm fails on all counts to be a viable model of process expression. Termination, determination and effectiveness are not necessary properties of process expression. There can be nonterminating, nondeterministic and incorrect expressions of useful and valid processes. "Precisely defined operation" is not a sufficient characterization of an expressional unit of process. The strictly sequential composition of expressional units is neither expressionally necessary nor sufficient.

When computer science was born, it borrowed substance from a particularly appropriate branch of mathematics, computability, which was founded as a discipline of pure mathematics at the beginning of the century and which studied mechanical computation using state machines, Turing machines and formal languages before the computer even existed. For the mathematicians, a sequence of operations was the simplest canonical form of expression that allowed the comparisons that they were interested in. They could directly compare computations by comparing the number of operations and the forms of the operations themselves. They were perfectly aware of the possibility of concurrent operations and purposely factored such irrelevant complications out of their expressions. The mathematicians did not need anything beyond the sequential process model of expression.

The mathematicians, with their rigorous formality were the certified theorists among a community of mostly engineers. The algorithmic sequential process model was available, it was adequate, it had authority and it had no competition. The model of computation for mathematics became the very firmly established model of expression for what was quite reasonably considered to be the foundational efforts in the theory of computers. This discipline of mathematics came to be called "the theory of computer science" while retaining all the flavor of pure mathematics and the notion of the algorithm came to be accepted as a fundamental paradigm of computer science.

The computer builders and users on the other hand were developing a sense that the computer might actually be conceptually intractable. It was pointed out early on that a computer and any program for it were arbitrary human artifacts. Since a human could build the computer and program it any way he chose the endeavor could not possibly be subject to any inherent limitations in the same sense that nature is subject to its laws or that mathematics is subject to its rules. Continuing experience further suggested that computing did indeed exhibit intractable degrees of freedom of expression. Given this perception the only approach to understanding so intractable a subject seemed to be experience and experiment and the only approach to managing it to be imposed rationale and convention. A comprehensive theory of process expression may not in fact be possible and the mathematicians were probably doing about as much as could be done even though it wasn't very useful.

As the field of computers grew, each area of computing developed its own isolated set of concepts and conventions and largely ignored "the theory of computer science". These areas attempt to interface with each other. For instance, architectures are designed to facilitate operating system functions. Compilers are optimize to specific architectures. Languages and architectures accommodate specific applications. But, there has not emerged from these local efforts a unified theory that pretends to be comprehensive and that can challenge the mathematical models for the title "The Theory of Computer Science".

Even though the mathematical theories have had little practical influence, the territory is still generally considered to be mathematical in nature and the mathematical perspective as well as the mathematical approach have permeated the disciplines of practical computing. However, the mathematical perspective is the wrong point of view. It is asking the wrong questions. The mathematical point of view is concerned with the behavior of classes of processes, the mapping of the domain to the range, the limits of behavior and anomalies of behavior? A mathematician is not greatly concerned with how a process is expressed. It may be expressed in any convenient language and executed on any convenient machine.

The computer scientist on the other hand is concerned about questions of expression. He wants to know, in general, how to define the optimal programming language, the best architecture to interpret programs in that language and how best to write those programs. He is not greatly concerned with what processes might be programmed on the computer and even less concerned about how any particular process might behave in terms of its domain and range.

A computer scientist is concerned about all of the possible ways to express a process regardless of what process is expressed. In contrast, a mathematician is concerned with the behavior of a specific class of processes regardless of how that process is expressed. Mathematicians and computer scientists are pursuing fundamentally different questions. The mathematicians tools are not as appropriate, as once supposed, to solve the questions of the computer scientist. The primary questions of computer science are not of computational possibilities but of expressional possibilities. Computer science does not need a theory of computation rather, it needs a theory of expression.

One pioneer of "computer science" elegantly summarizes the situation:

"In particular, in theoretical computer science we have been guilty of behaving too much like pure mathematicians; The mathematicians' compass has not always guided us well in exploring computer science. Time and again, we have valued the difficulty of proofs over the insights the proved results give us about computing; we have been hypnotized by mathematical elegance and pursued abstraction for its own sake. Frequently we have practiced "intellectual counter punching" by staying with small, previously defined (and possibly irrelevant) problems instead of searching for new formulations and development of theories more directly related to computing. . . . I believe that as we explore information processing further, there will be startling surprises and that our current ideas about computing will have to be modified substantially."--Juris Harmanis.

The following description attempts to formulate a comprehensive theory of computer science that can compete directly with the established mathematical theory of computer science. In particular, an exploration of process from the point of view of its expression is attempted. In addition, the description details some of the fundamental principles of expression and explains how these principles produce the enormous diversity of process expression in the physical and abstract world. By putting forth the proper questions from the proper perspective, it can be shown that computers are not as artifactual and intractable as once thought but simply one manifestation of a fundamental natural phenomenon.

SUMMARY OF THE INVENTION

A method and system for process expression and resolution is described. A first language structure comprising a possibility expression having at least one definition which is inherently and generally concurrent is provided. Further, a second language structure comprising an actuality expression including a fully formed input data name to be resolved is provided. Furthermore, a third language structure comprising an active expression initially having at least one invocation, the invocation comprising an association with a particular definition and the fully formed input data name of the actuality expression is provided. Subsequently, the process of resolving invocations begins in the active expression with fully formed input data names in relation to their associated definition to produce at least one or both of the following: (1) an invocation with a fully formed input data name and (2) a result data name.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a diagram showing high level description of the preferred embodiment process expression and resolution system.

FIG. 2 shows a network of association relationships with no cycles.

FIG. 3 illustrates a variable association rule as a bag that isolates variables and also keeps them together.

FIG. 4 illustrates the precedence of occurrence relationships among interactions for the example process.

FIG. 5 shows a rigid structure of interacting variables that might be expected to express the example process.

FIG. 6 illustrates the relationships between input variables and the result asserting variable.

FIG. 7 illustrates the difficulty directionality of interaction between directly associated variables.

FIG. 8 illustrates how many isolation variables must be between any two variables that assert the same value set.

FIG. 9 illustrates how variables can be arranged in a standard association unit called an interaction locus that isolates identical input and result value sets.

FIG. 10 shows one way to graphically represent an interaction locus.

FIG. 11 shows how several interaction loci can be directly associated to render a larger process expression.

FIG. 12 shows that the standard graphic form of representing logic circuits is identical to the more general form developed from the theory.

FIG. 13 is a directly associated expression with interaction loci which still cannot determine its own completion.

FIG. 14 is a configuration of interaction loci that will work with a NULL value added to the value sets of the interaction loci.

FIG. 15 illustrates an example process in which six distinctions can interact in nine possible ways to produce one of nine possible results.

FIG. 16 illustrates an arbitrary assignment of encodings.

FIG. 17 illustrates an example rotate locus.

FIG. 18 illustrates a configuration of rotation loci to convert a given input name to a standard recognition name .

FIG. 19 shows a set of transform rules.

FIG. 20 illustrates an example expression.

FIG. 21 is the input section of an expression that will recognize all of the possible input names of the process.

FIG. 22 shows a transform set which implements the task of asserting a particular value if enabled by a TRUE value and asserting a default result value if not enabled.

FIG. 23 shows a prioritized collection of asserted values.

FIG. 24 is the complete expression that will transform each possible four variable-four value input name to a specific four variable-four value result name.

FIG. 25 shows how the input name recognition stage can be optimized.

FIG. 26 shows how the result collection and assertion stage can be optimized.

FIG. 27 shows the complete optimized expression to recognize four variable-four value input names and assert four variable-four value result names.

FIG. 28 illustrates interaction loci as Boolean logic functions.

FIG. 29 illustrates a half adder circuit and corresponding truth table.

FIG. 30 illustrates a transform set which will unambiguously recognize three input names that are rotation neighbors.

FIG. 31 illustrates a locus which will generate the appropriate result values directly.

FIG. 32 illustrates how the expression of the example process can be expressed if custom interaction loci are allowed.

FIG. 33 illustrates how the expression can be further optimized by reassigning the coding of the input names.

FIG. 34 illustrates the expression of the example process if six values are available.

FIG. 35 illustrates the expression of the example process if nine values are available.

FIG. 36 shows that the expression becomes a pure variable expression if fifteen values are available.

FIG. 37 illustrates an expression with fewer values available.

FIG. 38 shows the transform table for the example expression if only two values are available.

FIG. 39 shows the example process as a standard logic circuit.

FIG. 40 shows transform value sets with the NULL convention added.

FIG. 41 shows the two value NULL convention expression of the simpler example process of FIG. 12.

FIG. 42 shows the basic example process expressed as two value NULL convention logic.

FIG. 43 illustrates the general form for a generally configurable process.

FIG. 44 shows a variable structure and transform rule set to implement a memory element.

FIG. 45 shows a variable structure and transform rule set to implement a selector element.

FIG. 46 illustrates the composite name form for a generally configurable processor.

FIG. 47 illustrates a selector element structure.

FIG. 48 shows a variable structure and transform rule set to implement a distributor element.

FIG. 49 illustrates a distributor element structure.

FIG. 50 illustrates the portion of a generally configurable process expression that configures association relationships for each interaction.

FIG. 51 shows the structure of the boundary element.

FIG. 52 shows a variable structure and transform rule set to implement a NULL-VALID detector element.

FIG. 53 shows how a NULL-VALID detector can be cascaded to accommodate any size name.

FIG. 54 shows how boundary elements communicate to synchronize value flow.

FIG. 55 is the transform table for the protocol section of the boundary element.

FIG. 56 shows the value change timing relationships among the variables of the boundary element.

FIG. 57 illustrates how name resolving expressions are inserted between boundary elements to form larger expressions.

FIG. 58 illustrates how boundary elements can be pipelined.

FIG. 59 shows a fan in configuration of boundary elements.

FIG. 60 shows a fan out configuration of boundary elements.

FIG. 61 shows the complete generally configurable process expression.

FIG. 62 is the example binary logic circuit shown in FIG. 39.

FIG. 63 shows the transform set for the complete example process.

FIG. 64 is an example process expression to be mapped into the generally configurable process.

FIG. 65 shows the sequence thread of interactions for the generally configurable process to perform one at a time.

FIG. 66 illustrates a process from the viewpoint of the generally configurable process and the viewpoint of the arbitrary process.

FIG. 67 illustrates a preferred embodiment apparatus for interpreting character strings.

FIG. 68 shows an example process expression as a binary logic full adder circuit.

DETAILED DESCRIPTION

1 A Model of Process Representation

The following section of this detailed description introduces a model of process expression that focuses on the nature of process itself. The model will lay a foundation for exploring the fundamental questions of process expression. Some of the concepts explored include: what are the possible forms of process expression, what are the relationships among these various forms, and what are the limits of process expression.

For the purpose of this detailed description, process shall be defined in very general terms, and then, the invocation model of process expression shall be introduced. A series of examples present two domains of expression within the invocation model and illustrate some fundamental principles of process expression.

1.1 Process

Process is characterized as the actual occurrence of interactions among distinctions from among a set of possible interactions resulting in a new set of distinctions and a new set of possible interactions. Each distinction is an interacting element different and distinct from all other interacting elements. Each possible interaction is determined by a unique combination of distinctions. An actual combination of distinctions determines which possible interaction actually occurs. Each interaction results in a new set of distinctions with new interaction possibilities.

When a combination is formed each distinction in the combination must be present at the place of combination and it must differentiate itself as a unique distinction in relation to the other distinctions at the place of combination. So each distinction must express a property of place as well as a second differentiating property.

Process is a confluence of possibility and actuality. All of the details of each possible interaction, what combinations of distinctions can form and what new distinctions result from each combination, must be expressed in detail before occurrence, but which possible interaction will actually occur cannot be expressed until the time of occurrence when a combination of distinctions is actually formed. The possibility of process and the actuality of process are inherently separate aspects of process and can be considered to be expressed separately as a possibility expression and as an actuality expression.

The possibility expression is an inherently incomplete specification of a process. It must defer as an open question which of the possible interactions will occur. The actuality expression provides the answer to this question and by combining with a possibility expression completes the specification of a particular occurrence of a process. The form of the possibility and actuality expressions must correspond in the sense that the answer of the actuality expression must fulfill the question of the possibility expression. The combination of distinctions of the actuality expression must be one of the possible combinations expressed by the possibility expression.

Process expression is essentially a matter of differentiation and association. The possibility expression must differentiate each distinction in relation to the other distinctions and then associate distinctions to express each possible interacting combination and the new distinctions resulting from each interaction. The actuality expression actually associates distinctions in an interacting combination.

The possibility expression of physics is the natural laws and the existence of matter. Exactly which matter will get together when and where is the realm of the actuality expression. The laws of chemistry is the possibility expression and the interpenetrating flux of chemicals is the actuality expression. Cellular machinery and DNA is the possibility expression and nutrients, hormones and intercellular transmitters is the actuality expression. A computer and program is the possibility expression and data is the actuality expression.

1.2 The Invocation Model

The invocation model consists of variables, values, variable association rules and value transform rules. A variables expresses the place of a distinction. Every variable constantly asserts a value. The value is the second differentiating property of a distinction. A variable asserting its value expresses a unique distinction of the process. Variable association rules specify which variables are interactively associated with each other. Value transform rules specify which values are interactively associated with each other and what values will result from the interaction.

1.2.1 Variable Association Rules

The variable association rules specify which variables can interact. If two or more variables are associated then those variables are interactively proximate. If variables are not associated by any association rule then they are not proximate and cannot interact.

The association rules differentiate the variables by specifying exactly how each variable is interactively proximate with one or more other variables. Each variable has a place in the process universe and each is differentiated by its place of association in relation to the other variables. If an association rule states that all variables are or may be in interactive proximity then each variable has no particular place in relation to the other variables and there is no way to differentiate one variable from another. If an association rule states that no variables are associated then it doesn't matter whether variables can be differentiated, they cannot interact and are not expressionally significant.

1.2.2 Value Transform Rules

The value transform rules specify what values can interact. A value transform rule specifies a combination of values as the name of the rule and a set of result values. The combination of values that forms the name of a value transform rule specifies that the combination of values is interactively proximate and will interact. If a combination of values does not form the name of any value transform rule then that combination of values is not proximate and they will not interact. The result values of the rule specify the values that will result from the interaction.

Similarly to variables, values receive their differentiation and place in the interaction universe from the value transform rules. Only values that appear in value transform rule names are interactively proximate and then only in the combinations specified by the names. Values appearing both in value transform rule names and also as result values in other value transform rules form relationships among value transform rules that forge the structure of the value interaction universe and establish each value's place in it. A value is differentiated by its place in relation to all the other values in the process universe as specified by the set of value transform rules for the process.

1.2.3 Primitive Process Interaction

Associated variables (the variables are interactively proximate) asserting their values form a combination of distinctions. If the combination of asserted values forms the name of a value transform rule (the values are interactively proximate) then an interaction will occur. If two variables are in interactive proximity but their values are not in interactive proximity (the values do not form a value transform rule name) no interaction will occur. Conversely values can be interactively proximate but if their asserting variables are not interactively proximate no interaction will occur.

Like the sorcerer invoking his demons by name to perform his magical transformations a combination of distinctions forms the name of a transform rule name, the rule is invoked and the transformation occurs. Hence the invocation model.

1.2.4 Interaction Composition

The next stage of process expression beyond a single interaction among several possible interactions is the expression of a progression of dependent interactions each interaction being at a place in relation to all other interactions with each place of interaction having a set of possible interactions. The dependency relationships among the places of interaction are expressed as name formation dependency relationships. The name formed for one place of interaction depends on the result distinctions of one or more other places of interaction. The dependency relationship can be expressed as direct association relationship between the formable name at one place of interaction and the result distinctions from other places of interaction. It is still not possible to predetermine which distinctions will be asserted and which transform name will be formed at each place of interaction but it can be predetermined where the distinctions forming the transform name for each place of interaction will come from within the expression.

These dependency relationships form a network of association relationships of result distinctions to transform name forming combinations of distinctions among the places of interaction. It is this network of association relationships that provides each place of interaction with its place in relation to all the other places of interaction.

FIG. 2 shows a network of association relationships with no cycles. Although any configuration of association relationships is possible this discussion will consider only directed association networks with no cycles.

Each individual place of interaction is expressed by its own possibility expression (e.g.,120,122,124 and 126) consisting of a set of value transform rules. These individual possibility expressions are combined into a larger composite possibility expression through the name formation dependency relationships. For example, possibility expressions 120 and 126 combine to form possibility expression 122. Most of the interactions receive their transform name distinctions from specified local places in the structure of associations. A few name forming distinctions, however, are not associated to any local places and they must come from someplace external to the structure of association relationships. These unassociated name values taken collectively are called the input name and are the composite actuality expression 128 for the composite possibility expression. A composite actuality expression 128 will also be referred to as the input name 128 for the composite possibility expression. The result values of the composite possibility expression will be referred to as the result name 130.

The composite possibility expression, including for example 120, 122, 124 and 126 is a complete stand alone specification of possibilities dependent only on its composite actuality expression. It is a larger self contained unit of expression (a possibility expression and an actuality expression) than the interaction.

These name formation dependency relationships among places of interaction can be expressed within the invocation model either in terms of value transform rules or in terms of variable association rules. This means that the model possesses two quite different but complementary domains of expression.

1.3 Two Domains of Expression

The value transform rules and the variable association rules provide the model with two domains of differentiation and interactive association. A process can be expressed almost exclusively in terms of differentiation and interactive association of values by value transform rules or almost exclusively in terms of differentiation and interactive association of variables by variable association rules. Between these two extremes there is a large intermediate landscape of cooperative expression with gradations of expression from each domain.

1.3.1 Pure Value Expression

At one extreme is the pure value expression for which all differentiation and interactive association is expressed in terms of values and is specified by value transform rules. Each distinction is a unique value and possesses a unique place in value space in relation to all other values. All interactive association is expressed by correspondence among combinations of these unique values, i.e., every value transform rule name in the process expression is unique. There is no differentiation in terms of variable association rules. Variables are all simultaneously associated or they associate indiscriminately. There is no way from the point of view of the variables to discriminate one interaction from another.

A natural example of this form of expression is a chemical reaction. The molecules are variables. The composition of each molecule determines its interaction possibilities and is its value. A liquid or gas is natures version of the association rule that specifies that there is no differentiation of variables. The variables (molecules) will indiscriminately associate in the liquid or gas and there is no way to tell one variable from another except by the value it asserts. The molecules get together forming transform rule names and interact to form new molecular values.

1.3.2 Pure Variable Expression

At the other extreme is the pure variable expression for which all differentiation and interactive association is expressed in terms of variables and is specified by variable association rules. Each distinction is a unique variable and possesses a unique place in variable space by virtue of its association relationships with other variables. All interactive association is specified by specifically associated variables. There is no differentiation in terms of value transform rules. There is a set of values and a set of spanning value transform rules, i.e., there is a transform rule for every possible combination of values. This means that all values in the expression are constantly in interactive proximity. There is no way from the point of view of the values to discriminate one interaction from another.

A natural example of this form of expression is a network of neurons. The artificial computer is also primarily of this form.

Within the model there must always be a bit of each domain in every process expression. There must always be variables that associate and there must always be values that form transform names. Nevertheless the two ends of the territory will be referred to as pure value and as pure variable.

1.3.3 The Intermediate Expression Territory

Expression in the intermediate territory between pure value and pure variable is a cooperative endeavor between variable differentiation and value differentiation. A very simple example of this cooperative expression is the representation of numbers with different bases. Base two numbers have only two values and very simple value transform rules (logical truth tables) but have lots of digits (variables) that must be properly associated. Base ten numbers have ten values and larger, more complex value transform rules (traditional addition and multiplication tables) but have fewer digits (variables) to be associated. There can be gradations of intermediate expression ranging from mostly in terms of value differentiation and value transform rules to mostly in terms of variable differentiation and variable association rules as shown below in Table 1.

                  TABLE 1
    ______________________________________
     ##STR1##
    ______________________________________

                  TABLE 2
    ______________________________________
              AB[D] or    BA[D]
              CD[B] or    DC[B]
    ______________________________________

                  TABLE 3
    ______________________________________
               AB   [ C, D ]
               CC   [ D, E ]
               DD   [ G, F ]
               EF   [ F, G ]
               GG   [ X, Y ]
    ______________________________________

                  TABLE 4
    ______________________________________
    Possible values are
                      M,D,C,L,X,V,I
    Transform rules are
                      IIIII [ v ]
                      VV [ X ]
                      XXXXX [ L ]
                      LL [ C ]
                      CCCCC [ D ]
                      DD [ M ]
    ______________________________________

                  TABLE 5
    ______________________________________
           Possible values are
                       A,B,C,D,E
           Transform rules are
                       AA [ B ]
                       BB [ C ]
                       CC [ D ]
                       DD [ E ]
    ______________________________________

                  TABLE 6
    ______________________________________
    Possible values are:
             E0,E1,D0,D1,C0,C1,B0,B1,A0,A1
    Transform rules are:
             A0A0 [ B0,A0 ]
                       B0B0 [ C0,B0 ]
             A0A1 [ B0,A1 ]
                       B0B1 [ C0,B1 ]
             A1A0 [ B0,A1 ]
                       B1B0 [ C0,B1 ]
             A1A1 [ B1,A0 ]
                       B1B1 [ C1,B0 ]
             C0C0 [ D0,C0 ]
                       D0D0 [ E0,D0 ]
             C0C1 [ D0,C1 ]
                       D0D1 [ E0,D1 ]
             C1C0 [ D0,C1 ]
                       D1D0 [ E0,D1 ]
             C1C1 [ D1,C0 ]
                       D1D1 [ E1,D0 ]
                       E0E0 [ E0 ]
                       E0E1 [ E1 ]
                       E1E0 [ E1 ]
                       E1E1 [ E0 ]
    ______________________________________

                  TABLE 7
    ______________________________________
    Possible values are:
    Dx,Cx,Bx,Ax
    UDx,UCx
    TDx,TCx,TBx
    SDx,SCx,SBx
    RDx, RCx, DONE x = 0,1
    ______________________________________
    Transform rules are:
    precedence of
    occurrence     transform
    relationships  rule
    ______________________________________
           1          AxAx     [ SBy,Az ]
           1          BxBx     [ SCy,TBz ]
           2          SBxTBx   [ RCy,Bz ]
           1          CxCx     [ SDy,TCz ]
           3          SCxRCx   [ UCz ]
           4          TCxUCx   [ RDy,Cz ]
           1          DxDx     [ TDz ]
           5          RDxSDx   [ UDz ]
           6          TDxUDx   [ Dz, DONE ]
    ______________________________________
           for all rules
                   x     x     >>   y   z
                   0     0     >>   0   0
                   0     1     >>   0   1
                   1     0     >>   0   1
                   1     1     >>   1   0
    ______________________________________

    ______________________________________
    E0 D1 C1 B0 A1 + E0 D0 C1 B1 A1
    E1 D0 C1 B0 A0 DONE
    ______________________________________

                  TABLE 8
    ______________________________________
    Interaction stage
    ______________________________________
    1          2       3       4     5     6
    ______________________________________
    Ax      Ax      Ax      Ax    Ax    Ax    Ax
    Ax      SBx     Bx      Bx    Bx    Bx    Bx
    Bx      TBx     RCx
    Bx      SCx     SCx     UCx   Cx    Cx    Cx
    Cx      TCx     TCx     TCx   RDx
    Cx      SDx     SDx     SDx   SDx   UDx   Dx
    Dx      TDx     TDx     TDx   TDx   TDx   DONE
    Dx
    ______________________________________

                  TABLE 9
    ______________________________________
    Transform rules are:
    precedence of
    occurrence   transform
    relationships
                 rule
    ______________________________________
    1                AxAx     [ SBy,Az ]
    1                BxBx     [ SCy,TBz ]
    2                SBxTBx   [ RCy,Bz ]
    1                CxCx     [ SDy,TCz ]
    3                SCxRCx   [ UCz ]
    4                TCxUCx   [ RDy,Cz ]
    1                DxDx     [ TDz ]
    5                RDxSDx   [ UDz ]
    6                TDxUDx   [ Dz, DONE]
    ______________________________________

                  TABLE 10
    ______________________________________
    Variable       Variable Variables
    3              4        1,2,5
    ______________________________________
    00[X]          X[S]     S[0]
    01[Y]          Y[T]     T[1]
    10[Y]
    11[X]
    ______________________________________

                  TABLE 11
    ______________________________________
    ADD            CARRY    DONE
    ______________________________________
    00[0]          00[0]    00[1]
    01[1]          01[0]    01[1]
    10[1]          10[0]    10[1]
    11[0]          11[1]    11[1]
    ______________________________________

                  TABLE 12
    ______________________________________
    ADD         CARRY          DONE
    ______________________________________
    00[0]       00[0]          00[1]
    01[1]       01[0]          01[1]
    10[1]       10[0]          10[1]
    11[0]       11[1]          11[1]
    anyNULL[NULL]
                anyNULL[NULL]  anyNULL[NULL]
    ______________________________________