This site is supported by donations to The OEIS Foundation.
Theme One Program • Exposition
Author: Jon Awbrey
• Overview • Blog • Exposition • Logical Cacti • Appendices • Document History •
Contents
Introduction
Theme One is a program for building and transforming a particular species of graph-theoretic data structures, forms designed to support a variety of fundamental learning and reasoning tasks.
The program evolved over the course of an exploration into the integration of contrasting types of activities involved in learning and reasoning, especially the types of algorithms and data structures capable of supporting all sorts of inquiry processes, from everyday problem solving to scientific investigation. In its current state, Theme One integrates over a common data structure fundamental algorithms for one type of inductive learning and one type of deductive reasoning.
We begin by describing the class of graph-theoretic data structures used by the program, as determined by their local and global features. It will be the usual practice to shift around and view these graphs at many different levels of detail, from their abstract definition to their concrete implementation, and many points in between.
The main work of the Theme One program is achieved by building and transforming a single species of graph-theoretic data structures. In their abstract form these structures are closely related to the graphs called cacti and conifers in graph theory, so we'll generally refer to them under those names.
The Idea-Form Flag
The graph-theoretic data structures used by the program are built up from a basic data structure called an idea-form flag. That structure is defined as a pair of Pascal data types by means of the following specifications.
- An idea is a pointer to a form.
- A form is a record consisting of:
- A sign of type char;
- Four pointers, as, up, on, by, of type idea;
- A code of type numb, that is, an integer in [0, max integer].
Represented in terms of digraphs, or directed graphs, the combination of an idea pointer and a form record is most easily pictured as an arc, or directed edge, leading to a node labeled with the other data, in this case, a letter and a number.
At the roughest but quickest level of detail, an idea of a form can be drawn as follows.
When it is necessary to fill in more detail, the following schematic pattern can be used.
The idea-form type definition determines the local structure of the whole host of graphs used by the program, including a motley array of ephemeral buffers, temporary scratch lists, and other graph-theoretic data structures used for their transient utilities at specific points in the program.
I will put off discussing the more incidental graph structures until the points where they actually arise, focusing here on the particular varieties of cactoid graphs which constitute the main formal media of the program's operation.
Painted And Rooted Cacti
Figure 1 shows a typical example of a painted and rooted cactus.
The graph itself is a mathematical object and does not inhabit the page or other medium before our eyes, and it must not be confused with any picture or other representation of it, anymore than we'd want someone to confuse us with a picture of ourselves, but it's a fair enough picture, once we understand the conventions of representation involved.
Let be the set of nodes in a graph and let be a set of identifiers. We often find ourselves in situations where we have to consider many different ways of associating the nodes of with the identifiers in Various manners of associating nodes with identifiers have been given conventional names by different schools of graph theorists. I will give one way of describing a few of the most common patterns of association.
- A graph is painted if there is a relation between its node set and a set of identifiers, in which case the relation is called a painting and the identifiers are called paints.
- A graph is colored if there is a function from its node set to a set of identifiers, in which case the function is called a coloring and the identifiers are called colors.
- A graph is labeled if there is a one-to-one mapping between its node set and a set of identifiers, in which case the mapping is called a labeling and the identifiers are called labels.
- A graph is said to be rooted if it has a unique distinguished node, in which case the distinguished node is called the root of the graph. The graph in Figure 1 has a root node marked by the “at” sign or amphora symbol “@”.
The graph in Figure 1 has eight nodes plus the five paints in the set The painting of nodes is indicated by drawing the paints of each node next to the node they paint. Observe that some nodes may be painted with an empty set of paints.
The structure of a painted and rooted cactus can be encoded in the form of a character string called a painted and rooted cactus expression. For the remainder of this discussion the terms cactus and cactus expression will be used to mean the painted and rooted varieties. A cactus expression is formed on an alphabet consisting of the relevant set of identifiers, the paints, together with three punctuation marks: the left parenthesis, the comma, and the right parenthesis.
Coding Logical Graphs
Figure 2 shows a way to visualize the correspondence between cactus graphs and cactus strings, demonstrated on the cactus from Figure 1. By way of convenient terminology, the polygons of a cactus graph are called its lobes. An edge not part of a larger polygon is called a 2‑gon or a bi‑gon. A terminal bi‑gon is called a spike.
The correspondence between a cactus graph and a cactus string is obtained by an operation called traversing the graph in question.
- One traverses a cactus graph by beginning at the left hand side of the root node, reading off the list of paints one encounters at that point. Since the order of elements at any node is not significant, one may start the cactus string with that list of paints or save them for the end. We have done the latter in this case.
- One continues by climbing up the left hand side of the leftmost lobe, marking the ascent by means of a left parenthesis, traversing whatever cactus one happens to reach at the first node above the root, that done, proceeding from left to right along the top side of the lobe, marking each interlobal span by means of a comma, traversing each cactus in turn one meets along the way, on completing the last of them climbing down the right hand side of the lobe, marking the descent by means of a right parenthesis, and then traversing each cactus in turn, in left to right order, that is incident with the root node.
The string of letters, parentheses, and commas one obtains by this procedure is called the traversal string of the graph, in this case, a cactus string.
Parsing Logical Graphs
It is possible to write a program that parses cactus expressions into reasonable facsimiles of cactus graphs as pointer structures in computer memory, making edges correspond to addresses and nodes correspond to records. I did just that in the early forerunners of the present program, but it turned out to be a more robust strategy in the long run, despite the need for additional nodes at the outset, to implement a more articulate but more indirect parsing algorithm, one in which the punctuation marks are not just tacitly converted to addresses in passing, but instead recorded as nodes in roughly the same way as the ordinary identifiers, or paints.
Figure 3 illustrates the type of parsing paradigm used by the program, showing the pointer graph structure obtained by parsing the cactus expression in Figure 2. A traversal of this graph naturally reconstructs the cactus string that parses into it.
The pointer graph in Figure 3, namely, the parse graph of a cactus expression, is the sort of thing we'll probably not be able to resist calling a cactus graph, for all the looseness of that manner of speaking, but we should keep in mind its level of abstraction lies a step further in the direction of a concrete implementation than the last thing we called by that name. While we have them before our mind's eyes, there are several other distinctive features of cactus parse graphs we ought to notice before moving on.
In terms of idea-form structures, a cactus parse graph begins with a root idea pointing into a by‑cycle of forms, each of whose sign fields bears either a paint, in other words, a direct or indirect identifier reference, or an opening left parenthesis indicating a link to a subtended lobe of the cactus.
A lobe springs from a form whose sign field bears a left parenthesis. That stem form has an on idea pointing into a by‑cycle of forms, exactly one of which has a sign field bearing a right parenthesis. That last form has an on idea pointing back to the form bearing the initial left parenthesis.
In the case of a lobe, aside from the single form bearing the closing right parenthesis, the by‑cycle of a lobe may list any number of forms, each of whose sign fields bears either a comma, a paint, or an opening left parenthesis signifying a link to a more deeply subtended lobe.
Just to draw out one of the implications of this characterization and to stress the point of it, the root node can be painted and bear many lobes, but it cannot be segmented, that is, the by‑cycle corresponding to the root node can bear no commas.
Lexical, Literal, Logical
Theme One puts cactus graphs to work in three distinct but related ways, called lexical, literal, and logical applications. The three modes of operation employ three distinct but overlapping subsets of the broader species of cacti. Accordingly we find ourselves working with graphs, expressions, and files of lexical, literal, and logical types, depending on the task at hand.
The logical class of cacti is the broadest, encompassing the whole species described above, of which we have already seen a typical example in its several avatars as abstract graph, pointer data structure, and string of characters suitable for storage in a text file.
Being a logical cactus is not just a matter of syntactic form — it means being subject to meaningful interpretations as a sign of a logical proposition. To enter the logical arena cactus expressions must express something, a proposition true or false of something.
Branch Point
- Branch 1
- Before we can get to the logical, interpretive, semantic aspect of cactus graphs we have a bit more to do in the way of detailing their syntactic utilities. Those are the matters we turn to next. Go To Lexical Cacti.
- Branch 2
- Fully addressing the logical, interpretive, semantic aspect of cactus graphs normally requires a mind-boggling mass of preliminary work on the details of their syntactic structure. Practical, pragmatic, and especially computational considerations will eventually make that unavoidable. For the sake of the present discussion, however, let's put that on hold and fast forward to the logical substance. Go To Logical Cacti.
Lexical Cacti
Lexical Cacti 1
The Index section of Theme One embodies an algorithm that "learns" finite sequences of finite sequences of characters. In this context, from now on, I will use the word "sequence" to mean a finite sequence.
A set of sequences of sequences of whatever signs one happens to have in an alphabet !A! is called a "two-level formal language" over !A!. So I can say that the program's Index function "learns" a two-level formal language over a particular alphabet !A!, the characters of which you can probably guess, more or less.
It is usual to introduce a collection of notations that comes along with the language of formal language theory:
An "alphabet" !A! is a finite set.
The "kleene-star" !A!* of an alphabet !A! is the set of all finite sequences over !A!, that is, the set of all finite sequences that can be formed from the elements of !A!.
The "sur-plus" !A!^+ of an alphabet !A! is the set of all finite sequences over !A! of length greater than zero.
A "formal language" L over !A! is a subset of !A!*. Employing the symbol "c" for "subset of", L c !A!*.
A "two-level formal language" L over !A! is a subset L c !A!** that is specified by giving the first-level language L_1 c !A!* and the second-level language L = L_2 c L_1* c !A!**.
The elements of L_1 are called "words" or "distinguished strings". The elements of L_2 are called "phrases" or "distinguished strands".
We refer to L_1 as the "lexical" level and we refer to L_2 as the "literal" level of the two-level formal language in question.
For the rest of this discussion, pick an alphabet !A! that contains all of the usual alphanumerics, plus a finite number of other signs that may be found convenient, but excluding the blank, the comma, the left and right parentheses, and the period, as these latter marks are reserved to special purposes by the Theme One program. </pre>
Lexical Cacti 2
Lexical Cacti (cont.) Example 2. Two-Level Formal Language: am Consider a very small example of a 2-level formal language, whose only word is the character sequence <"a", "m">, and whose only phrase is the singleton sequence <"am">, where we observe the convention that "am" = <"a", "m">. Formally speaking, we have the following data: L_1 = {<"a", "m">} c !A!*. L_2 = {<"am">} = {<<"a", "m">>} c !A!**. Theme One stores its data about the lexical level of a 2-level formal language in the form of a "lexical cactus". As always, one may choose to view this information as an abstract graph, as a concrete pointer graph, or as a text file consisting of the characters that encode a traversal string for the graph. Example 2. Lexical Level: am Figure 4 shows the abstract lexical cactus for the lexical level L_1 = {<"a", "m">}. o | mo-o o |/ / ao-o |/ @ ( a ( m , ( ) ) , ( ) ) Figure 4. Abstract Lexical Cactus: am Figure 5 shows the concrete lexical cactus for the lexical level L_1 = {<"a", "m">}. o-----o o-------|--o | | o----o | | o->| )0 |--o | o----o | ^ o------o | / o-----o o-----o o-----------------------|-/-----|--o | o-------|--o | | o----o o----o o----o< o----o | | | o----o | | o->| m1 |->| ,1 |->| (0 |->| )0 |--o | o->| )0 |--o | o----o o----o o----o o----o | o----o | ^ o------------------------------o ^ o------o | / | / o-----o o---------------|-/--------------------------------------|-/-----|--o | | o----o o----o< o----o o----o< o----o | | o->| a1 |->| (1 |-------------->| ,0 |------------->| (0 |->| )0 |--o | o----o o----o o----o o----o o----o | ^ o----------------------------------------------------------------o | / o----o< | (1 | o----o ^ | @ (1 a1 (1 m1 ,1 (0 )0 )0 ,0 (0 )0 )0 Figure 5. Concrete Lexical Cactus: am
Lexical Cacti 3
Lexical Cacti (cont.) Theme One gets its information about a two-level formal language L from a data stream that consists of a sequence -- indefinitely long in principle but always finite in practice -- of characters from the alphabet !A!, interspersed with blanks that tell it when an accepted, distinguished, established, or "received" word or phrase has passed. For example, the picture of the data structure shown in Figure 5 depicts the state of the relevant portion of computer memory just after the Indexer, starting from scratch, has taken up the initial segment of a data stream that begins "a", "m", " ", " ". The first space tells it that a sequence of characters constituting a word has just passed, and the second space tells it that a sequence of words constituting a phrase has just passed. More Examples of Lexical Cacti At this point I think that it would be a good idea to look at a developmental series of lexical cacti, ordered according to their increasing complication, designed to illustrate various features of their typical organization. The lexical level of Example 2 ("am") has already pushed the limits of the present format as far as being able to delineate the concrete pointer structures, but it will be possible to squeeze in just a few more of the abstract cacti for the following set of examples. Example 3. Lexical Level: all bees buzz Figure 6 shows the abstract lexical cactus and two forms of lexical files for the character stream "all bees buzz ". all bees buzz o o | | so-o o zo-o o |/ / |/ / eo-o zo-o o |/ |/ / eo-----uo-o | / | / o | / | | / lo-o o | / |/ / | / lo-o | / o |/ |/ / ao----bo-o | / | / | / | / | / | / |/ @ ( a ( l ( l , ( ) ) , ( ) ) , b ( e ( e ( s , ( ) ) , ( ) ) , u ( z ( z , ( ) ) , ( ) ) , ( ) ) , ( ) ) (3 a1 (1 l1 (1 l1 ,1 (0 )0 )0 ,0 (0 )0 )0 ,0 b2 (2 e1 (1 e1 (1 s1 ,1 (0 )0 )0 ,0 (0 )0 )0 ,0 u1 (1 z1 (1 z1 ,1 (0 )0 )0 ,0 (0 )0 )0 ,0 (0 )0 )0 ,0 (0 )0 )0 Figure 6. Lexical Cactus: all bees buzz
Lexical Cacti 4
Lexical Cacti (cont.) Example 4. Lexical Level: all apes are bold Figure 7 shows the abstract lexical cactus and two forms of lexical files for the character stream "all apes are bold ". all apes are bold o | o so-o o o | |/ / | lo-o eo-o eo-o o |/ |/ |/ / o lo---po---ro-o | | / do-o o | / |/ / | / lo-o o | / |/ / | / oo-o o |/ |/ / ao------------bo-o | / | / | / | / | / | / | / |/ @ ( a ( l ( l , ( ) ) , p ( e ( s , ( ) ) , ( ) ) , r ( e , ( ) ) , ( ) ) , b ( o ( l ( d , ( ) ) , ( ) ) , ( ) ) , ( ) ) (4 a3 (3 l1 (1 l1 ,1 (0 )0 )0 ,0 p1 (1 e1 (1 s1 ,1 (0 )0 )0 ,0 (0 )0 )0 ,0 r1 (1 e1 ,1 (0 )0 )0 ,0 (0 )0 )0 ,0 b1 (1 o1 (1 l1 (1 d1 ,1 (0 )0 )0 ,0 (0 )0 )0 ,0 (0 )0 )0 ,0 (0 )0 )0 Figure 7. Lexical Cactus: all apes are bold At this point, all that we need to take away from the above examples of lexical cacti is the prefix-sharing pattern of the data structure, which apart from the cactus rather than tree forms would probably be called "radix coding". If one has noticed the extra "spikes" at the right hand extremes of the cactus lobes, it would not be misleading to view these for now as a form of "parity checks", or a built-in redundancy for controlling potential errors in coding the data.
Lexical Cacti 5
Lexical Cacti (concl.) Example 5. Lexical Level: an angry ape ate a big bug Figure 8 shows the abstract lexical cactus and two forms of lexical files for the character stream "an angry ape ate a big bug ". an angry ape ate a big bug o | yo-o o |/ / ro-o o o o |/ / | | go-O eo-o eo-o o |/ |/ |/ / no---po---to-O | / o o | / | | | / go-o go-o o | / |/ |/ / | / io---uo-o | / | / | / | / | / | / | / | / | / | / o |/ |/ / ao----------bo-o | / | / | / | / | / | / | / | / | / | / | / | / |/ @ ( a ( n ( g ( r ( y , ( ) ) , ( ) ) , ( ) ) + , p ( e , ( ) ) , t ( e , ( ) ) , ( ) ) + , b ( i ( g , ( ) ) , u ( g , ( ) ) , ( ) ) , ( ) ) (7 a5 (5 n2 (2 g1 (1 r1 (1 y1 ,1 (0 )0 )0 ,0 (0 )0 )0 ,0 (0 )0 )1 ,0 p1 (1 e1 ,1 (0 )0 )0 ,0 t1 (1 e1 ,1 (0 )0 )0 ,0 (0 )0 )1 ,0 b2 (2 i1 (1 g1 ,1 (0 )0 )0 ,0 u1 (1 g1 ,1 (0 )0 )0 ,0 (0 )0 )0 ,0 (0 )0 )0 Figure 8. Lexical Cactus: an angry ape ate a big bug What we want to be on the lookout for in this last example of a lexical cactus is the way that the prefix-sharing strategy codes embedded words, the way that the lexical spelling of the word "a" is initial to "an", "angry", "ape", and "ate", and the way that the characters of the word "an" are also preficial to "angry". It is only the concrete versions of the lexical cactus and the corresponding traversal string that contain the real information about whether a prefix of a word in the "lexicon" or lexical level L_1 is a word in its own right within L_1. This information is coded in the 'code' field of the idea-form flag, and represents a frequency count of just how many times a character in a particular position has appeared as a part of a word in the data stream. For instance, the following fragment of the above lexical file illustrates how the word "an" is recorded as an element of L_1. (7 a5 (5 n2 (2 g1 (1 r1 (1 y1 ,1 (0 )0 )0 ,0 (0 )0 )0 ,0 (0 )0 )1 ^ | This frequency count being greater than zero indicates that "an" is a word in the lexicon. For convenience on those occasions when we do not care about the exact frequency counts on the nodes, but only about whether they are zero or not, we can transfer this information about "prefixes of words that are also words" to the abstract cactus string by marking the corresponding right parenthesis with an extra plus sign, "+", in this way: ( a ( n ( g ( r ( y , ( ) ) , ( ) ) , ( ) ) + ^ | This plus sign reminds us that "an" is a word in the lexicon. As a way of marking the information about prefix words on the abstract lexical cactus, let us use the device of a big node "O" for the node just before the lobal descent to the stem in question. Thus we have this: o | yo-o o |/ / ro-o o |/ / go--O <----------------- This big node means "an" is a word. | / o |/ ... ... / no---po---to-O <-------- This big node means "a" is a word. | / o o | / | | | / go-o go-o o | / |/ |/ / | / io---uo-o | / | / | / | / | / | / | / | / | / | / o |/ |/ / ao----------bo-o | / | / | / | / | / | / | / | / | / | / | / | / |/ @ Figure 9. Making a Big Point of a Prefix Word
Literal Cacti
Literal Cacti 1
Literal Cacti | There are no strings, | There are no strings, | There are no strings on me! Let us return to our littlest example of a two-level formal language, and pick up on the way that Theme One stores information about the literal level L_2. Example 2. Two-Level Formal Language: am Recall the two-level formal language L = (L_1, L_2) whose only word, or member of L_1, is the sequence of characters <"a", "m">, and whose only phrase, or member of L_2, is the singleton word sequence <"am">. Formally speaking, we have the following data: L_1 = {<"a", "m">} c !A!*. L_2 = {<"am">} = {<<"a", "m">>} c !A!**. Example 2. Literal Level: am Theme One stores its data about the literal level of a 2-level formal language in the form of a "literal cactus". As always, one may choose to view this information as an abstract graph, as a concrete pointer graph, or as a text file consisting of the characters that encode a traversal string for the graph. Things begin to get a little bit complicated at this point. Just as the lexical cactus that stores the data for L_1 is painted with single characters from the alphabet !A!, the literal cactus that stores the data for L_2 needs to be painted with words from L_1. This is achieved, not by recording the words themselves as character strings in the literal cactus, but by storing just their "ideas", that is, pointers to forms in the lexical cactus that serve as a type of "hash codes" for the words in L_1. These indirect identifier references are recorded in the "alias" or the 'as' fields of the paint-bearing forms in the literal cactus. In order to see how these "hash nodes" work, we shall need to drive a stratum deeper into the concrete data structure that supports both the lexical and the literal data bases. The display below shows a memory dump of the index structure that is formed in the relevant piece of computer memory when the Indexer, starting from scratch, has taken up the initial segment of a data stream that begins "a", "m", " ", " ". ( dump index ( 1003407 ( 0 1003510 1003407 0 1003201 ( 0 1005513 1004006 1 1005513 a 0 0 1005700 1 a 1005700 ( 0 1005803 1006112 1 1005803 m 0 0 1005906 1 m 1005906 , 0 0 1006215 1 1006215 ( 0 1006402 1006009 0 1006402 ) 0 1006215 1006402 0 1006009 ) 0 1005700 1005803 0 1006112 , 0 0 1002911 0 1002911 ( 0 1003014 1003304 0 1003014 ) 0 1002911 1003014 0 1003304 ) 0 1003201 1005513 0 1004006 ( 0 1007001 1003510 1 1007001 1005906 0 1007104 1 am 1007104 , 0 0 1003800 1 1003800 ( 0 1003903 1004109 0 1003903 ) 0 1003800 1003903 0 1004109 ) 0 1004006 1007001 0 1003510 ) 0 1003407 1003201 0 )) The first column of the index dump shows the address of the form. The second column shows the character in the form's 'sign' field. The third, fourth, and fifth columns list the addresses in the form's 'as' field, 'on' field, and 'by' field, respectively. The sixth column shows the number in the form's 'code' field. The last column highlights the identifier, if any, that is associated with a paint-bearing lexical or literal form. Figure 10 plots the data of the index dump as a graph, showing the shape and some of the concrete details of the graph-theoretical data structure that is built up in memory when the Indexer has taken up the incept of a data stream that begins "a", "m", " ", " ". o-----o o-------|--o | | o----o | | o->| )0 |--o | |6402| | o----o | ^ o------o | / o-----o o-----o o-----------------------|-/-----|--o | o-------|--o | | o----o o----o o----o< o----o | | | o----o | | o->| m1 |->| ,1 |->| (0 |->| )0 |--o | o->| )0 |--o | |5803| |5906| |6215| |6009| | |3014| | o----o o----o o----o o----o | o----o | ^ ^ | ^ o------o | o----|--------------------------o | / o-----o o---------------|-/-----|--------------------------------|-/-----|--o | | o----o o----o< | o----o o----o< o----o | | o->| a1 |->| (1 |-------|------>| ,0 |------------->| (0 |->| )0 |--o | |5513| |5700| | |6112| |2911| |3304| | o----o o----o o o----o o----o o----o | ^ o-\---------------------------------------------o | / \ | / \ o-----o | / \ o-------|--o | | / \ | o----o | | | / \ o->| )0 |--o | | / \ |3903| | | / \ o----o | | / \ ^ o------o | / \ | / o-----o | / o-\---------------------|-/-----|--o | | / | o----o o----o o----o< o----o | | | / o->| 1 |->| ,1 |->| (0 |->| )0 |--o | | / |7001| |7104| |3800| |4109| | | / o----o o----o o----o o----o | | / ^ o-----------------------------o | / | / | / | / o-----o o-------|-/------------------------------|-/-----------------------|--o | | o----o< o----o< o----o | | o->| (1 |-------------------------->| (1 |------------------->| )0 |--o | |3201| |4006| |3510| | o----o o----o o----o | ^ ^ ^ o------o | | | / @ @ o--------|-/-o lex lit | o----o< | o-->| (0 |---o |3407| o----o ^ | @ Figure 10. Index Graph: am In Figure 10, the pointer marked "lex" points to the root form of the lexical cactus for L_1, while the pointer marked "lit" points to the root form of the literal cactus for L_2. The lex and lit root forms are lodged in a piece of utility data structure that serves as a convenient dopstick or palette for keeping them together during processing. The thing to notice in Figure 10 is the "alias" (or is it "alibi"?) pointer that extends from the literal cactus to the lexical cactus. In this particular case, the literal form # 7001 has an 'as' field that points to the lexical form # 5906. The latter form serves in effect as the environmentally unique "hash code" for the word "am". Figure 11 demonstrates, in the case of our present example, a quick way to sketch the abstract versions of the lexical and literal cacti, and it also gives the text file representations of the corresponding traversal strings. o | mo-o o o |/ / am | ao-o `o-o |/ |/ @ @ lex lit am.lex = (1 a1 (1 m1 ,1 (0 )0 )0 ,0 (0 )0 )0 am.lit = (1 am 1 ,1 (0 )0 )0 Figure 11. Lexical Cactus + Literal Cactus: am
Literal Cacti 2
Literal Cacti (concl.) The text file representations of lexical and literal cacti give Theme One a "long-term memory", a more permanent way of storing up the "experience" of a given stream of characterness and putting it away for future revival. Moreover, when Theme One reloads a previously saved pair of lex and lit files, it has the luxury of being able to do a little more pre-processing that it otherwise had in the midst of an ongoing character stream, and so we next look to an illustration of that. The display below shows a memory dump of the index structure that is formed in the relevant piece of computer memory when the Indexer has loaded the lex and lit files that were shown in the legend of Figure 11. For reasons that shall be clear in time, let's call this reloaded version the "tabbed index". ( dump index ( 1004315 ( 0 1004502 1004315 0 1002911 ( 0 1003201 1004708 1 1003201 a 0 0 1003304 1 a 1003304 ( 0 1003510 1004006 1 1003510 m 0 0 1003613 1 m 1003613 , 1004914 0 1003800 1 `am 1003800 ( 0 1003903 1003407 0 1003903 ) 0 1003800 1003903 0 1003407 ) 0 1003304 1003510 0 1004006 , 0 0 1004109 0 1004109 ( 0 1004212 1003014 0 1004212 ) 0 1004109 1004212 0 1003014 ) 0 1002911 1003201 0 1004708 ( 0 1004914 1004502 1 1004914 1003613 1004914 1005101 1 am 1005101 , 0 0 1005204 1 1005204 ( 0 1005307 1004811 0 1005307 ) 0 1005204 1005307 0 1004811 ) 0 1004708 1004914 0 1004502 ) 0 1004315 1002911 0 )) Figure 12 plots the data of the "tabbed index" dump as a graph, showing the graph-theoretical data structure that is formed in memory when the Indexer has loaded the lex and lit files shown once more in the legend of the Figure. o-----o o-------|--o | | o----o | | o->| )0 |--o | |3903| | o----o | o--------------------o ^ o------o / \ | / o-----o o-----o / o---------\-------------|-/-----|--o | o-------|--o | o | o----o o----o o----o< o----o | | | o----o | | | o->| m1 |->| ,1 |->| (0 |->| )0 |--o | o->| )0 |--o | | |3510| |3613| |3800| |3407| | |4212| | | o----o o----o o----o o----o | o----o | | ^ ^ | ^ o------o | | o----|--------------------------o | / o-----o | o---------------|-/-----|--------------------------------|-/-----|--o | | | o----o o----o< | o----o o----o< o----o | | | o->| a1 |->| (1 |-------|------>| ,0 |------------->| (0 |->| )0 |--o | | |3201| |3304| | |4006| |4109| |3014| | o o----o o----o o o----o o----o o----o | \ ^ o-\---------------------------------------------o \ | / \ \ | / \ o-----o \ | / \ o-------|--o | \| / \ | o----o | | \ / \ o->| )0 |--o | |\ / \ |5307| | | \ / \ o----o | | \ / \ o---o ^ o------o | \ / \ | / | / o-----o | \ / o-\-----|-/-------------|-/-----|--o | | \ / | o----o< o----o o----o< o----o | | | \/ o->| 1 |->| ,1 |->| (0 |->| )0 |--o | | /\ |4914| |5101| |5204| |4811| | | / o---------------------->o----o o----o o----o o----o | | / ^ o-----------------------------o | / | / | / | / o-----o o-------|-/------------------------------|-/-----------------------|--o | | o----o< o----o< o----o | | o->| (1 |-------------------------->| (1 |------------------->| )0 |--o | |2911| |4708| |4502| | o----o o----o o----o | ^ ^ ^ o------o | | | / @ @ o--------|-/-o lex lit | o----o< | o-->| (0 |---o |4315| o----o ^ | @ am.lex = (1 a1 (1 m1 ,1 (0 )0 )0 ,0 (0 )0 )0 am.lit = (1 am 1 ,1 (0 )0 )0 Figure 12. Tabbed Index Graph: am Except for one sling and one arrow, the tabbed index graph in Figure 12 is isomorphic to the untabbed index graph in Figure 10. Of course, the actual addresses of the forms are different, but that is to be expected whenever the lex and lit files are reloaded in a different environment. Comparing the tabbed index graph of Figure 12 with the index graph of Figure 10, we can see that the extra arrow is the arc from the lex form # 3613 to the lit form # 4914, and the extra sling is the 'on'-loop at the lit form # 4914. I will refer to these as the "tab link" and the "tab loop", respectively, because they are accessed by using the tab key on the keyboard. In general, the tab loop is extended to a "tab cycle" whenever there is more than one appearance of the same lexical item in the same literal cactus. The tab link in Figure 12 points from the "hash form" of the lexical item "am" to the site of its first invocation in the literal cactus. The tab loop in this particular case merely constitutes a self-reference at this initial site, but would more generally expand into a tab cycle as the literal cactus grows, to encompass all of the occurrences of a lexical item. The preceding discussion provides a first glance at the structural anatomy of lexical and literal cacti. There is quite a bit more to say on this score, and then we would have barely yet scratched the surface when it comes to their functional roles in adaptive indexing and experiential learning. All in the fullness of time. But now we have the minimal background that we need to get back to logical cacti, and that amounts to such a compelling subject that I cannot resist returning to it at once.
Logical Cacti
Logical Cacti 1
Up till now we've been working to hammer out a two-edged sword of syntax, honing the syntax of cactus graphs and cactus expressions and turning it to use in taming the syntax of two-level formal languages. But the purpose of a logical syntax is to support a logical semantics, which means, for starters, to bear interpretation as sentential signs capable of denoting objective propositions about a universe of objects.
One of the difficulties we face is that the words interpretation, meaning, semantics, and their ilk take on so many different meanings from one moment to the next of their use. A dedicated neologician might be able to think up distinctive names for all the aspects of meaning and all the approaches to them that concern us, but I will do the best I can with the common lot of ambiguous terms, leaving it to context and intelligent interpreters to sort it out as much as possible.
The formal language of cacti is formed at such a high level of abstraction that its graphs bear at least two distinct interpretations as logical propositions. The two interpretations concerning us here are descended from the ones C.S. Peirce called the entitative and the existential interpretations of his systems of graphical logics.
Existential Interpretation
Table 13 illustrates the existential interpretation of cactus graphs and cactus expressions by providing English translations for a few of the most basic and commonly occurring forms.
Entitative Interpretation
Table 14 illustrates the entitative interpretation of cactus graphs and cactus expressions by providing English translations for a few of the most basic and commonly occurring forms.
Logical Cacti 2
The main things to take away from Tables 13 and 14 are the following two ideas, one syntactic and one semantic.
- The compositional structures of cactus graphs and cactus expressions are constructed from two kinds of connective operations.
- There are two ways of mapping these compositional structures into the compositional structures of propositional sentences.
The two kinds of connective operations are described as follows.
- The node connective joins a number of component cacti to a node:
- The lobe connective joins a number of component cacti to a lobe:
The two ways of mapping cactus structures to logical meanings are summarized in Table 15, which compares the entitative and existential interpretations of the basic cactus structures, in effect, the graphical constants and connectives.
Logical Cacti 3
The abstract character of the cactus language relative to its logical interpretations makes it possible to give abstract rules of equivalence for transforming cacti among themselves and partitioning the space of cacti into formal equivalence classes. The transformation rules and equivalence classes are “purely formal” in the sense of being indifferent to the logical interpretation, entitative or existential, one happens to choose.
Two definitions are useful here:
- A reduction is an equivalence transformation which applies in the direction of decreasing graphical complexity.
- A basic reduction is a reduction which applies to a basic connective, either a node connective or a lobe connective.
The two kinds of basic reductions are described as follows.
- A node reduction is permitted if and only if every component cactus joined to a node itself reduces to a node.
- A lobe reduction is permitted if and only if exactly one component cactus listed in a lobe reduces to an edge.
That is roughly the gist of the rules. More formal definitions can wait for the day when we need to explain their use to a computer.
Logical Cacti 4
The foregoing discussion has given a fairly thorough description of the abstract graphs and the concrete data structures falling under the name of painted and rooted cacti. The “paints” serve to organize lexical and literal data by marking the characters and phrases of a two-level formal language. That appears at first sight to put the matter as concretely as possible, free from all traces of interpretive play or flexibility.
But there is an aspect of the prefix-sharing strategy which gives each word in a lexical cactus and each phrase in a literal cactus a double meaning. For one thing, it stands for itself, as always; For another thing, it stands for the family of words or the family of phrases, as the case may be, which has that sequence of characters or that sequence of words as its prefix.
For example, consider the two-level language that is given as follows: L_1 = {"a", "all", "an", "angry", "ape", "apes", "are", "ate", "bees", "big", "bold", "bug", "buzz"} L_2 = {"all bees buzz", "all apes are bold", "an angry ape ate a big bug"} We make the following observations about this example: 1. The prefix class of "a" in L_1, written "[a]L_1", or simply "[a]" if the context is understood, is the set of all words in L_1 that begin with "a". 2. The prefix class of "bu" in L_1, written "[bu]L_1", or simply "[bu]" if the context is understood, is the set of all words in L_1 that begin with "bu", namely, the set {"bug", "buzz"}. 3. The prefix class of "all" in L_2, written "[all]L_2", or simply "[all]" when the context is understood, is the set of all phrases in L_2 that begin with "all", namely, the set {"all bees buzz", "all apes are bold"}. In general terms, a prefix, whether it belongs to the language or not, can be used to "stand for", that is, as a proxy, a representative, or a symbol for, the associated prefix class, which constitutes a subset of the language in question. In graphical terms, the path up to a point in a lexical or literal cactus can be used, under the proper alternative interpretation, to stand for the whole class of paths in the cactus that run from the root, through that point, to a syntactic terminus, in so many ways extending the initial path in question. The situation that we have just now been looking at is only a very special case of a much more general phenomenon, falling under a principle that I will describe this way: Information is form before matter. That is not a definition -- it is only an emphasis. I am often tempted to express the idea by saying that information is form, not matter, but the more I reflect on it the less certain I become that form and matter are not all one in the end, so the best that I can do for now is to emphasize what seems fair to stress in the meantime. One of the consequences of this principle is that all codes are abstract, formal, and symbolic to some degree, which means that no code has the power to determine its interpretation perfectly. I will not attempt to prove this principle -- not knowing how long the line between form and matter will hold, it would probably be pointless to try -- I will merely call attention to examples of it as they arise. The most pressing pertinent example arises in the case of logical cacti, so let us now turn to consider that.
Logical Cacti 5
Bare Cacti and Their Arithmetic I will now elaborate a strategy that I use whenever I get worried about the "meaning" or the "ontology" of "variables". The problematic status of the variable can be seen to become especially acute in light of the principle just stated, concerning the interpretive relativity of form and matter in the signs that bear information, that is, in light of the circumstance that the distinction between their form and their content is relative to interpretation. The acuteness is due to the circumstance that the very distinction between constant and variable now becomes relative to interpretation in this light. In order to approach this issue from a slightly different perspective than is usually taken up, I will not speak of constants and variables, whatever those are, but return to the description of cacti in the media of "paints". I introduce a few bits of informal language that will speed the discussion: Generally speaking, one often finds that a particular formal language under view will contain an "arithmetic" sub-language, all of whose expressions are composed solely of symbols called "constant symbols", and as such singled out from the "algebraic" language as a whole, whose expressions may also contain symbols called "variable symbols". For the moment, I will keep the colorful terms "arithmetic" and "algebraic", but try to avoid especially the use of the word "variable", with all its accretions of mystifying connotations. By definition, an "impression" is an expression in the arithmetic sub-language. Back in realm of cacti and cactus expressions, I make the following definitions: A "bare cactus" is one devoid of paint, or what is the same thing, a cactus that has every node painted with the empty set of paints. Bare cacti and bare cactus expressions are also known as "impressions", as in "impressions of value", and these are regarded as limiting cases of the more general cacti and cactus expressions that we shall come to apprize as "expressions of value". What brings the question of "value" into this realm of abstract expressions and special impressions is that there is a set of rules that can be used to equate every impression with one or the other of these two cacti: @ or |, where I use the vertical bar "|" as an in-line picture of the rooted edge. I now present a set of "abstract rules of equivalence" (AROE's) that divide the space of impressions into exactly two equivalence classes. Rather than trying to come up with the most elegant set of rules from the axiomatic standpoint, I will merely give the rules that seem to be the most frequently useful in practice, and that will serve to rationalize the algorithm used in the Theme One program. o-----------------------------------------------------------o | ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` ` ` ` ` o ` o ` ` ` ` ` ` ` ` o ` ` ` ` ` ` ` ` ` | | ` ` ` ` ` ` ` ` `\ /` ` ` ` ` ` ` ` ` | ` ` ` ` ` ` ` ` ` | | ` ` ` ` ` ` ` ` ` @ ` ` ` ` = ` ` ` ` @ ` ` ` ` ` ` ` ` ` | | ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | o-----------------------------------------------------------o | ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` ` ` ` `( ) ( )` ` ` = ` ` ` `( )` ` ` ` ` ` ` ` ` | | ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | o-----------------------------------------------------------o | Axiom I_1.` ` Distract <--- | ---> Condense ` ` ` ` ` ` ` | o-----------------------------------------------------------o o-----------------------------------------------------------o | ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` ` ` ` ` ` o ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` ` ` ` ` ` | ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` ` ` ` ` ` o ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` ` ` ` ` ` | ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` ` ` ` ` ` @ ` ` ` ` = ` ` ` ` @ ` ` ` ` ` ` ` ` ` | | ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | o-----------------------------------------------------------o | ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` ` ` ` ` (( )) ` ` ` = ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | o-----------------------------------------------------------o | Axiom I_2.` ` ` Unfold <--- | ---> Refold ` ` ` ` ` ` ` ` | o-----------------------------------------------------------o o-----------------------------------------------------------o | ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` x_1 `x_2` `...` x_k ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` `o----o-...-o----o` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` \ ` ` ` ` ` ` / ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` `\` ` ` ` ` `/` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` \ ` ` ` ` / ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` `\` ` ` `/` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` ` \ ` ` / ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` ` `\` `/` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` ` ` \ / ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` ` ` `@` ` ` ` ` ` ` = ` ` ` ` ` ` `@` ` ` ` ` ` ` | | ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ( x_1, x_2, ..., x_k )` ` = ` ` ` ` ` <blank> ` ` ` ` ` | | ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` ` ` ` ` ` ` ` IF AND ONLY IF` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `o` ` ` ` ` ` ` | | ` Just one of the x_1, x_2, ..., x_k` `=` `|` `=` `( )` ` | | ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `@` ` ` ` ` ` ` | | ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | o-----------------------------------------------------------o | Lobe Evaluation Rule` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | o-----------------------------------------------------------o Two special cases of the Lobe Evaluation Rule are as follows: o-----------------------------------------------------------o | ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` ` ` `x` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` `o-...-o-o-o-...-o` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` \ ` ` ` ` ` ` / ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` `\` ` ` ` ` `/` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` \ ` ` ` ` / ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` `\` ` ` `/` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` ` \ ` ` / ` ` ` ` ` ` ` ` ` ` ` ` `x` ` ` ` ` ` ` | | ` ` ` ` ` `\` `/` ` ` ` ` ` ` ` ` ` ` ` ` `o` ` ` ` ` ` ` | | ` ` ` ` ` ` \ / ` ` ` ` ` ` ` ` ` ` ` ` ` `|` ` ` ` ` ` ` | | ` ` ` ` ` ` `@` ` ` ` ` ` ` = ` ` ` ` ` ` `@` ` ` ` ` ` ` | | ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | o-----------------------------------------------------------o | ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` `( , , , x , , , )` ` ` = ` ` ` ` ` ` (x) ` ` ` ` ` ` | | ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | o-----------------------------------------------------------o | Rule I_3` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | o-----------------------------------------------------------o o-----------------------------------------------------------o | ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` ` ` `o` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` `a` ` `m`|`n` ` `z` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` `o-...-o-o-o-...-o` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` \ ` ` ` ` ` ` / ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` `\` ` ` ` ` `/` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` \ ` ` ` ` / ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` `\` ` ` `/` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` ` \ ` ` / ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` ` `\` `/` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | ` ` ` ` ` ` \ / ` ` ` ` ` ` ` ` ` ` ` a...m n...z ` ` ` ` | | ` ` ` ` ` ` `@` ` ` ` ` ` ` = ` ` ` ` ` ` `@` ` ` ` ` ` ` | | ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | o-----------------------------------------------------------o | ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | | (a, ..., m, ( ), n, ..., z) = ` ` ` ` a...m n...z ` ` ` ` | | ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | o-----------------------------------------------------------o | Rule I_4` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` | o-----------------------------------------------------------o
Logical Cacti 6
Bare Cacti and Their Arithmetic (cont.) To be continued ...
Examples
Jets and Sharks
Jets and Sharks 1
It is easy to spend a long time on the rudiments of learning and logic before getting down to practical applications — but I think we've circled square one long enough to expand our scope and see what the category of programs envisioned in Theme One can do with more substantial examples and exercises.
During the development of the Theme One program I tested successive implementations of its Reasoning Module or Logical Modeler on appropriate examples of logical problems current in the literature of the day. The PDP Handbook of McClelland and Rumelhart set one of the wittiest gems ever to whet one's app‑titude so I could hardly help but take it on. The following text is a light revision of the way I set it up in the program's User Guide.
Example 5. Jets and Sharks
The propositional calculus based on the minimal negation operator can be interpreted in a way resembling the logic of activation states and competition constraints in one class of neural network models. One way to do this is to interpret the blank or unmarked state as the resting state of a neural pool, the bound or marked state as its activated state, and to represent a mutually inhibitory pool of neurons by the proposition The manner of representation may be illustrated by transcribing a well-known example from the parallel distributed processing literature (McClelland and Rumelhart 1988) and working through a couple of the associated exercises as translated into logical graphs.
Displayed below is the text expression of a traversal string which Theme One parses into a cactus graph data structure in computer memory. The cactus graph represents a single logical formula in propositional calculus and this proposition embodies all the logical constraints defining the Jets and Sharks data base.
Jets and Sharks 2
Example 5. Jets and Sharks (cont.)
As we saw last time, Theme One reads the text file shown above and constructs a cactus graph data structure in computer memory. The cactus graph represents a single logical formula in propositional calculus and that proposition embodies the logical constraints defining the Jets and Sharks data base.
Our cactus graph incorporates a vocabulary of 41 logical terms, each of which represents a boolean variable, so the proposition in question, call it is a boolean function of the form Given we know a truth table for takes over two trillion rows and a venn diagram for takes the same number of cells. Topping it off, there are boolean functions of the form and is just one of them.
Measures of strategy are clearly needed to negotiate patches of cacti like those.
Jets and Sharks 3
Example 5. Jets and Sharks (cont.)
Given a representation of the Jets and Sharks universe in computer memory, we naturally want to see if the memory serves to supply the facts a well-constructed data base should.
In their PDP Handbook presentation of the Jets and Sharks example, McClelland and Rumelhart suggest several exercises for the reader to explore the performance of their neural pool memory model on the tasks of retrieval and generalization (Exercise 2.1).
Using cactus graphs or minimal negations to implement pools of mutually inhibitory neurons lends itself to neural architectures on a substantially different foundation from the garden variety connectionist models. At a high level of abstraction, however, there is enough homology between the two orders to compare their performance on many of the same tasks. With that in mind, I tried Theme One on a number of examples like the ones suggested by McClelland and Rumelhart.
What follows is a brief discussion of two examples as given in the original User Guide. Next time I'll fill in more details about the examples and discuss their bearing on the larger issues at hand.
With a query on the name “ken” we obtain the following output, giving all the features associated with Ken.
With a query on the two features “college” and “sharks” we obtain the following outline of all features satisfying those constraints.
From this we discover all college Sharks are 30‑something and married. Further, we have a complete listing of their names broken down by occupation.
References
- McClelland, J.L. (2015), Explorations in Parallel Distributed Processing : A Handbook of Models, Programs, and Exercises, 2nd ed. (draft), Stanford Parallel Distributed Processing Lab. Online, Section 2.3, Figure 2.1.
- McClelland, J.L., and Rumelhart, D.E. (1988), Explorations in Parallel Distributed Processing : A Handbook of Models, Programs, and Exercises, MIT Press, Cambridge, MA. “Figure 1. Characteristics of a number of individuals belonging to two gangs, the Jets and the Sharks”, p. 39, from McClelland (1981).
- McClelland, J.L. (1981), “Retrieving General and Specific Knowledge From Stored Knowledge of Specifics”, Proceedings of the Third Annual Conference of the Cognitive Science Society, Berkeley, CA.
Resources
Applications
Documentation
References
- Awbrey, S.M., and Awbrey, J.L. (May 1991), “An Architecture for Inquiry • Building Computer Platforms for Discovery”, Proceedings of the Eighth International Conference on Technology and Education, Toronto, Canada, pp. 874–875. Online.
- Awbrey, J.L., and Awbrey, S.M. (January 1991), “Exploring Research Data Interactively • Developing a Computer Architecture for Inquiry”, Poster presented at the Annual Sigma Xi Research Forum, University of Texas Medical Branch, Galveston, TX.
- Awbrey, J.L., and Awbrey, S.M. (August 1990), “Exploring Research Data Interactively • Theme One : A Program of Inquiry”, Proceedings of the Sixth Annual Conference on Applications of Artificial Intelligence and CD-ROM in Education and Training, Society for Applied Learning Technology, Washington, DC, pp. 9–15. Online.
Document History
Language Of Cacti
- http://web.archive.org/web/20150224134418/http://stderr.org/pipermail/inquiry/2004-December/thread.html#2135
- http://web.archive.org/web/20060415083155/http://forum.wolframscience.com/showthread.php?threadid=649
- http://web.archive.org/web/20061121231602/http://forum.wolframscience.com/archive/topic/649-1.html
Propositional Equation Reasoning Systems
- http://web.archive.org/web/20141210145032/http://stderr.org/pipermail/inquiry/2004-April/thread.html#1341
- http://web.archive.org/web/20141207162001/http://stderr.org/pipermail/inquiry/2004-May/thread.html#1391
- http://web.archive.org/web/20141210154610/http://forum.wolframscience.com/showthread.php?threadid=297
- http://web.archive.org/web/20141210150520/http://forum.wolframscience.com/archive/topic/297.html
Theme One Program • Exposition (2003)
- http://web.archive.org/web/20150224210600/http://stderr.org/pipermail/inquiry/2003-March/000102.html
- http://web.archive.org/web/20150224210601/http://stderr.org/pipermail/inquiry/2003-March/000103.html
- http://web.archive.org/web/20061013222119/http://stderr.org/pipermail/inquiry/2003-March/000104.html
- http://web.archive.org/web/20080908074156/http://stderr.org/pipermail/inquiry/2003-March/000105.html
- http://web.archive.org/web/20081012073249/http://stderr.org/pipermail/inquiry/2003-March/000106.html
- http://web.archive.org/web/20081007071618/http://stderr.org/pipermail/inquiry/2003-March/000107.html
- http://web.archive.org/web/20080828013646/http://stderr.org/pipermail/inquiry/2003-March/000108.html
- http://web.archive.org/web/20081006115254/http://stderr.org/pipermail/inquiry/2003-March/000109.html
- http://web.archive.org/web/20081012104413/http://stderr.org/pipermail/inquiry/2003-March/000110.html
- http://web.archive.org/web/20081007042925/http://stderr.org/pipermail/inquiry/2003-March/000111.html
- http://web.archive.org/web/20080829043118/http://stderr.org/pipermail/inquiry/2003-March/000112.html
- http://web.archive.org/web/20081007065533/http://stderr.org/pipermail/inquiry/2003-March/000113.html
- http://web.archive.org/web/20081007043317/http://stderr.org/pipermail/inquiry/2003-March/000114.html
- http://web.archive.org/web/20080908075558/http://stderr.org/pipermail/inquiry/2003-March/000115.html
- http://web.archive.org/web/20080908080336/http://stderr.org/pipermail/inquiry/2003-March/000116.html
Theme One Program • Exposition (2005)
- http://web.archive.org/web/20150109152200/http://stderr.org/pipermail/inquiry/2005-February/002348.html
- http://web.archive.org/web/20150109152201/http://stderr.org/pipermail/inquiry/2005-February/002349.html
- http://web.archive.org/web/20061013233439/http://stderr.org/pipermail/inquiry/2005-February/002350.html
- http://web.archive.org/web/20081120193342/http://stderr.org/pipermail/inquiry/2005-February/002351.html
- http://web.archive.org/web/20081120184622/http://stderr.org/pipermail/inquiry/2005-February/002352.html
- http://web.archive.org/web/20061013233504/http://stderr.org/pipermail/inquiry/2005-February/002353.html
- http://web.archive.org/web/20081121105019/http://stderr.org/pipermail/inquiry/2005-February/002354.html
- http://web.archive.org/web/20061013233332/http://stderr.org/pipermail/inquiry/2005-February/002355.html
- http://web.archive.org/web/20061013233616/http://stderr.org/pipermail/inquiry/2005-February/002356.html
- http://web.archive.org/web/20081121104528/http://stderr.org/pipermail/inquiry/2005-February/002357.html
- http://web.archive.org/web/20081121114930/http://stderr.org/pipermail/inquiry/2005-February/002358.html
- http://web.archive.org/web/20061013233413/http://stderr.org/pipermail/inquiry/2005-February/002359.html
- http://web.archive.org/web/20150109152359/http://stderr.org/pipermail/inquiry/2005-February/002360.html
- http://web.archive.org/web/20150109152401/http://stderr.org/pipermail/inquiry/2005-February/002361.html
- http://web.archive.org/web/20061013233259/http://stderr.org/pipermail/inquiry/2005-February/002362.html
- http://web.archive.org/web/20081121103109/http://stderr.org/pipermail/inquiry/2005-February/002363.html
• Overview • Blog • Exposition • Logical Cacti • Appendices • Document History •
- Adaptive systems
- Artificial intelligence
- Automated reasoning
- Boolean algebra
- Boolean functions
- Computational complexity
- Constraint satisfaction
- Declarative programming
- Differential logic
- Formal languages
- Functional logic
- Graph theory
- Inquiry driven systems
- Intelligent systems
- Knowledge representation
- Learning systems
- Learning theory
- Logic
- Logical graphs
- Logical modeling
- Machine learning
- Model theory
- Peirce, Charles Sanders
- Programming
- Proof theory
- Propositional calculus
- Relation theory
- Scientific method
- Semiotics
- Sign relations
- Spencer Brown, George
- Sequence learning
- Systems engineering
- Systems theory
- Visualization