G61.1825: Using Wolfram’s Cellular Automata as Models of Human Communication

Prof. Ray Dougherty

Fall 2003

This course analyzes the computational requirements (pattern matching abilities, problem solving skills, and memory) required by the human brain to learn and use a language. Each student learns the software of Wolfram’s New Kind of Science to conduct computational psycho-linguistic experiments with cellular automata, finite state grammars, and Markov models. We contrast the processing capacities and data structures found in human language with those found by Konrad Lorenz in ducks, geese, and chimps. We show that the arguments offered by Chomsky and Miller to reject finite state models were empirically flawed. We discuss data from child language acquisition (Piaget) and brain damage (Luria) to show that coordination is simpler than subordination. A main focus is on computational notation and processes to represent language and communication data in humans (adult and child) and animals (ethology). Students will run cellular automata experiments using Wolfram’s NKS software or Mathematica.

Goals

The course aims to provide a solid working knowledge of the differences between ‘derivation’ and ‘structure’ in generative grammars and in the computational mechanisms that underlie those grammars. The main course text, Stephen Wolfram (2002) A New Kind of Science, provides a detailed set of elementary computational tools that can provide students with weekly exercises they must run on NYU computers. Through hands-on operation with Wolfram’s cellular automata, students will gain a thorough understanding of the differences between finite state automata and phrase structure grammars. We shall argue that the computational mechanisms that underlie human language capacities are finite state and that the only tree structures possible in human languages are those generable by finite state automata. This explains why there seem to be two types of ‘merge’ operation: one (two memory merge) on strings and one (three memory merge) defining phrases. A pure finite state grammar allows only two memory merge operations, and hence, if any tree is produced, the lowest (terminal) nodes may bear lexical labels, but no ‘higher’ nodes can bear labels, in some cases, because there are no higher nodes.

Before Wolfram’s A New Kind of Science - which includes hundreds of simple programs that run on programs available at NYU (NKS Explorer and Mathematica) - there was no hands-on way for anyone to understand the problems of ‘derivation’ and ‘structures’ without learning to program in a higher level language (perl, lisp, prolog…). For this course, no student needs to learn to program, rather, all student projects only require students to design experiments in automata and enter a small set of parameters into the NKS programs to run the cellular automata.

The focus of the class is on the relation between computational process and structure, and specifically, on the mechanisms by which a small finite grammar can make precise explicit claims about an unbounded number of structures (infinite use of finite means). We will cast human language in the ethological perspective on Konrad Lorenz and relate the processes (but not the structures) of human language to the processes of animal intelligence.

The course has three natural divisions:

(I) We will (a) present Wolfram’s cellular automata and some elementary formal language theory, (b) show how to run Wolfram’s software, (c) discuss how cellular automata can clarify the relation of human language processing to the communication and problem solving capacities of animals studied by Lorenz and Tinbergen: including: ducks, the octopus, chimps, amoeba, and paramecium. We shall argue that cellular automata define the basic ‘information unit’ of the human language capacity. Students will understand automata by observing them produce graphic output on Wolfram’s programs.

(II) We shall study the development of derivation versus structure in generative grammar from the mid 1950s until today. We shall focus on finite state grammars versus phrase structure grammars and show that all of the arguments used to show finite state grammars were inadequate, when closely examined, show the reverse: that phrase structure grammars are inappropriate. We discuss the competence (PSG) versus performance (finite state) distinction and argue it was misstated.

(III) We shall use our understanding of the differences between finite state and phrase structure grammars to understand ideas in two recent papers: Chomsky (2001) ‘Beyond Explanatory Adequacy’ and Collins (2001) ‘Eliminating Labels’. We shall argue that if the computational mechanisms of human language capacity are finite state (like Wolfram’s cellular automata) then one would expect ‘string’ and not ‘phrase’ to be the crucial structural unit (like Chomsky’s ‘phase’, which is not a ‘phrase’, and seems to be a ‘string’). By definition finite state grammars normally (two memory merge) produce no labels, hence, as one might expect, careful detailed work, like that of Collins, which assumes labels existed, if successful at gaining insight into human language processes, should prove labels are extraneous as research leads to the true underlying finite state mechanisms. The conclusions about data structures in both these papers follow as a natural consequence of the assumption that human language processing is finite state. We discuss how we can go beyond ‘explanatory adequacy’ that is simply given as propositional statements constraining structures by presenting the properties of the human computational mechanisms that generate and process utterances.

Provisional weekly syllabus

Week 1. Introduction to Wolfram’s New Kind of Science and cellular automata.

What is an automaton? How does it make infinite use of finite means? What is meant by ‘generate’, ‘random’, and ‘complex’? Human intuitions about ‘random’, ‘complexity’, and ‘grammatical’. Do not be frightened by Wolfram’s notation. The ideas are simple.

Read:

  1. Wolfram, The Foundations for a New Kind of Science, pp. 1-51.
  2. Review of Wolfram’s NKS in the New York Review of Books.
  3. Review of Wolfram’s NKS in Nature.

Week 2. How to Run Wolfram’s Software.

Discuss the various types of cellular automata. What is meant by ‘universal’? Wolfram’s numbering system for automata. Why some cellular automata (30, 110) are far more interesting than others. We compare phrase structure grammars with Wolfram’s basic automata and with his substitution automata. How rules or automata make infinite use of finite means.

Read:

  1. Wolfram, The World of Simple Programs, pp. 52-75.
  2. Wolfram, Mechanisms in Programs and Nature, pp. 297-363.

Week 3. Wolfram’s ‘The Universe is a Computer’ versus Konrad Lorenz on ‘Animal Intelligence’.

We will advance the argument that the cellular automaton is not a ‘thing’ (like a machine) but is a ‘measure’ (like a gram, a foot, or an erg). A ‘cellular automaton’, as an idealization and abstraction, is to animal intelligence what a ‘cell’ is to biology, or an ‘atom’ to chemistry. It is the smallest unit of computational intelligence for pattern recognition, problem solving, or memory structure – as these terms are used by Konrad Lorenz. We develop Wolfram’s cellular automata (in total opposition to his philosophic views) to claim that the cellular automata reflects the smallest units of operation of animal and human intelligence. Cellular automata may or may not play some role in the physical processes of the universe, but they definitely play a role in how intelligent animals perceive, understand, and communicate.

Read:

  1. Wolfram, Processes of Perception and Analysis, pp. 547-637.
  2. Wolfram, Notes, pp. 1125.
  3. Wolfram, look up ‘linguistics’, ‘perception’, ‘cognition’ in his index.
  4. Assorted readings by Konrad Lorenz.


Week 4. Cognitive Psychology and Linguistics: ‘explicate an intuitive notion’

In Syntactic Structures Chomsky says that a goal of the linguistic study of a language, L, is to explicate the intuitive notion ‘grammatical in L’ and ‘grammatical’ in human language. In a real sense all of Wolfram’s work explicates two intuitive notions: ‘complex’ and ‘random’. But he leaves these totally undefined. We shall define them relative to the animal intelligence that is analyzing the patterns.

Read:

  1. Look up ‘random’ and ‘complex’ in Wolfram’s index and read the passages, attempting at all times to decide whether his discussion makes any sense. Most reviewers say it does not. I think it does, but only if we understand cellular automata as the elements of cognition.
  2. Konrad Lorenz, Behind the Mirror, Chapters 1,2, and 3 on ‘releasers’.

Week 5. How to run Wolfram’s NKS Software and other related programs

The various types of automata. Cellular automata. Finite State Devices. The phenomena of ‘center embedded structures’ versus finite state automata.

Read:

  1. Shannon and Weaver, pp.
  2. Chomsky, Syntactic Structures, finite state versus PSG: pp. 18-34,
  3. Chomsky, Aspects of the Theory of Syntax, Methodological Preliminaries, pp. 3-18.
  4. Selected parts of the Chomsky and Miller articles in The Handbook of Mathematical Psychology.
  5. Look up ‘substitution automata’ in Wolfram and skim over the passages.

Week 6. Finite State Grammars versus Phrase Structure (Categorial) Systems.

Chomsky and Miller, plus many others, published articles on these systems and we will go over many of their discussions. We will focus on the systems of Chomsky and Miller.

Read: (parts of the following)

  1. Miller and Chomsky. Finitary Models of Language Users
  2. Chomsky and Miller. Introduction to the Formal Analysis of Natural Languages.
  3. Gross and others on INTEX, a computational finite state grammar.

Week 7. A Human Languages (is / is not) a set. The Mixup of Competence and Performance.

In the earliest work, Chomsky, Miller, and others assumed that the competence model of human grammar involved tree structures (phrase markers) involving labeled nodes. The performance model was a finite state grammar. Their arguments were fundamentally flawed, not in the mathematics, but in their application to the empirical data provided by natural languages.

Read:

  1. Various papers from psycholinguists discussing center embeddings, in particular the work of Gibson.
  2. Various readings from Chomsky and others on competence and performance.
  3. Selections from Greasy, Grimy, Gopher Guts, a collection of children’s chants.

Week 8. Cellular Automata, Automata, Finite State Grammars: description or explanation?

What is meant by observational, descriptive, and explanatory adequacy? In general, all attempts at explanatory adequacy involve the presentation of ‘language universals’ that impose constraints on structures (c-command, linearity, hierarchy, and so on), and usually these structures are individual trees, each assigned to a particular sentence or construction. We shall discuss moving beyond this structural concept of explanatory adequacy and entering a realm where all constraints follow from the types of computational mechanisms that are permitted in the human cognition. We do not have constraints on derivation or structures, but on the mechanisms (cellular automata) underlying these derivations and structures. This is actually much simpler than it sounds.
Read:

  1. Passages from Cartesians about trisecting an angle with a ruler and a compass.
  2. Readings yet to be selected.

Week 9. Recursive Processes in Human Language: Coordination versus Subordination.

Why does human language have two different processes for embedding one structure in an identical structure, to state the problem obliquiely. We should say, why does human language have two processes, such that while executing one of them, can briefly pause and execute either of the processes before resuming where it left off? We will mainly focus on coordination and investigate data from children and brain damaged people (Luria). Why is Mary, Sue, and Alice simpler than Mary or Sue and Alice? Or is it? Why do children acquire coordination before
subordination? If they do. Why do brain damaged people fail to process subordination but accept coordination in many cases. Is the book’s cover simpler than the cover of the book? Why? How? We shall argue that structurally the answers cannot be stated since the issues involve processing.

Read:

  1. Assorted readings from Luria, Piaget, and Ph.D. dissertations.
  2. Readings from various works on coordination, particularly of pronouns such as: you and me, him and I, us and you, and so on.
  3. Readings from pyscholinguists (Gibson especially) on ‘difficulty of processing.
  4. Readings about processing difficulty of garden path sentences (Fodor mainly)

Week 10. Finite State Automata Processing Model versus a Phrase Marker Grammar on ‘complexity’ in structures, derivations, and processing.

Why are some center embedded sentences almost perfect and others horrible? Why does no language have center embeddings over degree 3, and usually not over degree 2. We discuss verb final versus English type languages.

Read:

  1. Assorted works by Kuno on Japanese and German center embeddings.
  2. Selected works by Gibson on center embedding.
  3. Wolfram on ‘substitution automata’ and ‘recursion’.

Week 11. Finite State Automata versus Phrase Marker Grammars on ‘coordination: and, or, nor’.

We will examine the proposals of Janne Bondi Johannessen in her book Coordination to see the role her notational conventions play in her explanation of the existing patterns of coordinate data in languages around the world. Although Chomsky and Miller (and almost everyone) assume coordination is ‘simpler’ or ‘less complex’ than subordination, we shall see that this is probably not so. The ‘processes’ involved in coordination are probably simpler (less lexical) than those of subordination, but they are intertwined in an extremely complex way.

Read:

  1. Johannessen, Selected readings from Coordination, mainly the last two chapters.
  2. Assorted readings on the computational analysis of coordinate structures.

Week 12. Levels of Adequacy for a Structural or Computational Analysis of Language.

We examine the ideas of observational, descriptive, and explanatory adequacy introduced in Aspects by Chomsky. We discuss early views that language was a set and the McCawley versus Chomsky controversy. We discuss the ‘subset theory’ of Berwick and others. Our main focus is on what lies beyond ‘old’ explanatory adequacy.

Read:

  1. Chomsky, Beyond Explanatory Adequacy. (only focus on what is ‘merge’?)
  2. Chomsky, Aspects, Chapter 2.
  3. McCawley’s review of Knowledge of Language in Language.
  4. Chomsky’s reply to McCawley.

Week 13. Zellig Harris on Phrase Structure-like Data Structures.

A phrase marker shows (a) elements are linearly ordered, (b) the elements are hierarchically organized into non-overlapping sequences, and (c) the elements are labeled with ‘titles’ to show there are similarities and differences among the sequences. A finite state grammar can certainly generate phrase markers, albeit tortuously. A finite state grammar (depending on how you look at it – horizontally or vertically) will easily shows elements are linearly ordered. Only with great difficulty and ad hoc buffers will it show that the elements are hierarchically organized. With more ad hoc additions, in the form of buffers and indexing addressing schemes, a finite state grammar can assign labels. So to find that a grammar can honky-dory do its job without any labels (above lexical categories), is a plus for a finite state grammar. A finite state grammar implemented on a computing machine (automata) with one or two auxiliary buffers would allow (depending on the number and type of buffers) some (center) embedding and tree structure – but not much. We shall discuss grammars that assign structures or define strings that do not have any (or very many) labels.
We shall argue that the structure assigned a sentence (string) is not to enable that string to be assigned a semantic interpretation or to enable us to compare on part of the string with another (compare two noun phrases, for example). The grammar assigns a structure to a string to show how it stands in a constellation of all of the other strings in the language. A language, following Harris, might best be thought of as being n-tuples of utterances, where finite state grammars define the strings in any of the n-tuples (perhaps in terms of paraphrase and cooccurrence).

Read:

  1. Chris Collins, ‘Eliminating Labels’
  2. Selections from Zellig Harris, ‘Transformational Grammar’
  3. Readings from Maurice Gross and others on INTEX finite state analysis.

Week 14. Review and Discussion of the Changes in the Concept ‘Explanation in Linguistics’.

Classroom discussion. A brief overview of a general form of code (a multiplex code) that can be clarified greatly in terms of cellular automata. This general code applies in genetics, economics, and linguistics, and – we shall argue – this is because the code may or may not reflect anything about the physical world external to a human, but it reflects completely the cognitive mechanisms a human brings to the perception and understanding of experience. If the only tool you have is a hammer, everything looks like a nail. If the only tools human’s have in their perception and cognition are small class of ‘preprogrammed’ cellular automata, then they will have ‘clear’ intuitions about these phenomena and ‘guess’ very well in these situations. We will discuss the possible existence of a ‘unified’ cognition theory that argues that the human mind is a Procrustean Bed (defined by cellular automata) which defines the possibilities for ‘experience’, ‘knowledge’, and ‘intuition’ for humans.

Read:

  1. Dougherty et. al. ‘Ordered Acyclic Digraphs (ODAGs) Invariant Under a Half-Turn: Some Implications for Formal and Natural Language Syntactic Theory’

Requirements

This is a lecture course. Students are expected to run programs as homework assignments.

There will be a midterm and a final paper due. Weekly assignments will be handed out.

The weekly assignments will require students to run Wolfram’s software and obtain printouts, which must then be turned in to the professor.

For a midterm, each student must review the published reviews of Wolfram’s New Kind of Science, and then write their own review of his book and comment on whether they agree or disagree with the published reviews.

Students may select a final project in line with their skills and interests. Many final projects will be suggested. All students must do a term paper, there will be no final exam.

Last Modified: July 8, 2003