Minimalist Syntax and the Many Faces of Recursion

This blog post summarizes the confusing web of concepts associated with recursion, and comments on how they are related to each other. In particular, I will show how each of the concepts relates to the minimalist structure building operation Merge.

The following discussion was inspired by reading Lobina 2017, where some of these issues are discussed in more detail. But Lobina 2017 lacks an easy-to-reference appendix where all the notions and interrelations are defined. 

There are seven different (but related) concepts I will discuss:

1. Recursive Definition of a Function

2. Recursive Definition of a Procedure

3. Self-Embedded Structures

4. Recursively Enumerable (Semi-Decidable) Set

5. Recursive (Decidable) Set

6. Inductive Definition of a Set

7. Proof by Induction

1. Recursive Definition of a Function

A function f is defined recursively when the value of the function for a particular argument f(n) is calculated in terms of the value of the function for lower values of the same argument. The classical example is the factorial function:

a. f(n) = 1 if n = 1 (base case)

b. f(n) = n x f(n-1) if n > 1 (recursive case)

Comment: Merge is not defined recursively in this sense. Merge takes two syntactic objects and produces a larger syntactic object: Merge(A,B) = {A,B}, there is no self-reference involved in this definition (Lobina 2017: 95).

2. Recursive Definition of a Procedure

A computer program subroutine is recursive if the execution of that subroutine involves an independent call to the same subroutine.

Comment: “recursive definition of a function” and “recursive definition of a subroutine” are very closely related: the former being employed in mathematics, and the latter in computer science. Neither of them is directly related to Merge, in the sense that Merge is not defined recursively in this sense.

3. Self-Embedded Structures

Self-embedding is the property of natural language syntax where a constituent with syntactic category label X (e.g., TP, T’, VP, NP, DP, PP) can dominate another constituent with the same syntactic category label X (e.g., TP, T’, VP, NP, DP, PP). For example in ‘a picture of Chomsky’, the DP ‘a picture of Chomsky’ dominates the DP ‘Chomsky’.

Comment: When linguists use the term “recursion” they are often referring to self-embedded structures in this sense. Self-embedded structures arise naturally under a theory of Merge that creates labeled structures (see Collins and Stabler 2016 for a discussion Merge and labeling).

Comment: In a system without labels, any hierarchical structure would be self-embedding (one set within another). But this is not the traditional conception of “recursion” that linguists have in mind.

Comment: Some people distinguish between direct recursion involving immediate dominance, and indirect recursion involving dominance but not immediate dominance.

4. Recursively Enumerable (Semi-Decidable) Set

A set is recursively enumerable if there exists a precise algorithm that can generate (enumerate) the members of that set. For example, there may be a particular Turing machine that generates the set.

Comment: The use of the term “recursive” has origins in computability theory. One of the many equivalent formulations of “computable function” involves recursion in the sense of “recursive definition of a function” above. But other formulations (such as Turing machines) do not. 

Comment: The set of sentences generated by a particular I-language is recursively enumerable.

5. Recursive (Decidable) Set

A set is recursive (decidable) if there exists a precise algorithm that can decide for any given element if it is a member of that set or not.

Comment: The set of sentences generated by a particular I-language may also be recursive, but it is less obvious.

6. Inductive Definition of a Set

A set S is defined inductively if there is a set of initial elements B and a function that generates the rest of the elements such that:

a. For all x, if x is in B, then x is in S.

b. If x is in S, then f(x) is in S.

c. There are no other elements of S.

Comment: The set of syntactic objects can be defined inductively in this way.

a. If x is a lexical item, it is a syntactic object.

b. If x and y are syntactic objects, then Merge(x,y) is a syntactic object.

c. There are no other syntactic objects.

Comment: The syntactic objects are the closure of the lexicon with respect to Merge.

Comment: The property (b) is what Chomsky has in mind when he uses the term “recursive”, see the Chomsky quotes below.

7. Proof by Induction

Proof by induction is a way of proving that a statement S is true for all positive integers. 

a. Base Case: Show S is true for n=1. 

b. Inductive Step: Show that if S is true for n (an arbitrary integer), it is also true for n+1.

If the base case and the inductive step hold, then S is true for all positive integers.

Comment: Various properties of Merge can be proven by induction. See the appendix Collins and Stabler 2016 (available upon request).

Chomsky Quotes

In recent work, Chomsky seems to use “recursive” in the sense of definition 6 above (“Inductive Definition of a Set”) (see a-e below). But in other publications, he refers to “recursive enumeration” which tends to suggest definition 4 (“recursively enumerable set”) (see f-g) below. In no circumstances does Chomsky take “recursion” to mean self-embedding.

a. “Note further that Merge is recursive in that it can target the objects that it creates in subsequent applications. In other words, in principle, the output of one application of Merge can serve as input to another application of Merge.” (Chomsky et. al. 2023: 4)

b. “The basic property of recursive generation requires that any object already generated be accessible to further operations.” (Chomsky, Gallego and Ott 2019: 245)

c. “It’s an invariant property of humans that the language faculty involves recursion. Well, what’s the basic idea of recursion? It’s that every object that’s generated must be available for later computations.” (Chomsky 2019: 276)

d. “NS has one operation that comes "free," in that it is required in some form for any recursive system: the operation Merge, which takes two elements A,B, already constructed, and creates a new one consisting of the two-in the simplest case, {A,B}. (Chomsky 2004: 108)

e. “Given the numeration N, the operations of CHL recursively construct syntactic objects from items in N and syntactic objects already formed.” (Chomsky 1995: 226)

f. “Similarly, some disruption of the neural basis for cognitive systems yielded recursive enumeration, nature then reconstructed the new system as SMT (so we would like to show).” (Chomsky 2024: 20)

g. “An adequate grammar must at the very least provide a recursive enumeration of the grammatical sentences of the language: it must be what is technically called a ‘generative grammar’.” (Chomsky 2022: 349)

Acknowledgments

I thank Andreas Blumel and Ed Stabler for commenting on a version of this post.

References

Chomsky, Noam. 1995. The Minimalist Program. MIT Press, Cambridge.

Chomsky, Noam. 2004. Beyond Explanatory Adequacy. In Adriana Belletti (ed.), Structures and Beyond, 104–131. Oxford: Oxford University Press.

Chomsky, Noam. 2019. Some Puzzling Foundational Issues: The Reading Program. Catalan Journal of Linguistics (Special Issue), 2633-285.

Chomsky, Noam, Ángel J. Gallego, and Dennis Ott. 2019. Generative Grammar and the Faculty of Language: Insights, Questions and Challenges. Catalan Journal of Linguistics (Special Issue), 229–261.

Chomsky, Noam. 2022. Genuine Explanation and the Strong Minimalist Thesis. Cognitive Semantics 8, 347-365.

Chomsky, Noam, T. Daniel Seely, Robert C. Berwick, Sandiway Fong, M.A.C. Huybregts, Hisatsugu Kitahara, Andrew McInnerney, Yushi Sugimoto. 2023. Merge and the Strong Minimalist Thesis. Cambridge University Press, Cambridge.

Chomsky, Noam. 2024. The Miracle Creed and SMT. In Matteo Greco and Davide Mocci (eds.), A Cartesian Dream: A Geometrical Account of Syntax in Honor of Andrea Moro. Lingbuzz Press.

Collins, Chris and Edward Stabler. 2016. A Formalization of Minimalist Syntax. Syntax 19, 43-78. 

Lobina, David J. 2017. Recursion. Oxford University Press, Oxford.