LINGUIST List 2.602

Tue 01 Oct 1991

Disc: Is Language Finite?

Editor for this issue: <>


  1. "Michael Kac", Re: 2.595 Is Language Infinite?
  2. Tom Lai, Is language infinite?
  3. Terry Langendoen, is language infinite?

Message 1: Re: 2.595 Is Language Infinite?

Date: Mon, 30 Sep 91 17:36:29 -0500
From: "Michael Kac" <>
Subject: Re: 2.595 Is Language Infinite?
Answer to Linguist subscriber Macrakis on how Langendoen and Postal get
uncountably infinite languages: the answer is that they argue, contrary
to the standard position, that there are sentences of infinite length.
(See Chapter 3 of their book.)
Alexis Manaster-Ramer makes a couple of comments in his most recent posting
that I want to strongly second. The first is that the question of finiteness/
nonfiniteness of languages is not a factual one; the second is his expression
of discomfort with the cavalier way in which the Langendoen-Postal thesis is
rejected by most linguists. I'm reluctant to take up a lot more space with
my endless 2 cents worth but encourage Linguist subscribers who are interested
in the issue to correspond with me personally. My address is kaccs.umnedu.
Michael Kac
Mail to author|Respond to list|Read more issues|LINGUIST home page|Top of issue

Message 2: Is language infinite?

Date: Tue, 1 Oct 91 11:20 +8
Subject: Is language infinite?
I appreciate Alexis Manaster Ramer's remarks of Sept. 29. I apologize
for any previous strong-worded comments of mine.
The notions of countable and uncountable infinity are, I agree,
mathematical convenience. But, that they are such only because they
are useful, i.e. they do reflect something that is significant. For
example, a properly written computer program should, at least,
terminate after a _finite_ number of operations. If there is an
unending loop like WHILE TRUE DO BEGIN STATEMENT END then the number
of operations will be _(countably) infinite_. The physical
significance is that this program will never terminate.
As for the cardinality of language or of individual languages, natural
or not natural, I have been silent for some time to sort out my ideas
and to listen to other contributors to the discussion. Now, I would say
(1) To use computing jargon, any (particular) language over a finite
alphabet with no upper bound on the length of its strings is
(2) Natural languages have finite inventories of phonemes. It follows
from (1) that if there is no upper bound on the length of words (there
may be dispute over this point), the lexicons can be (countably) infinite;
(cf. linguists' perception of "open" lexicons)
(3) If the sentences of a language is to be formed by words extracted from
an infinite (countable) lexicon, and as recursion entails the possibility
of sentences of any length, the set of sentences (of this language) is
_uncountably_ infinite.
Point (3) above should answer Macrakis' query on the possibility of
uncountable cardinality in set theory.
We will not get into any paradox (a concern of Macrakis'). Whereas natural
languages can be perceived as infinite, any actual simulation of a natural
language on a computer is finite. (Can I assume that it is impossible for
us to have infinite computer lexicons?)
Sorry for the length of this posting. Looking forward to views of
Tom Lai.
Mail to author|Respond to list|Read more issues|LINGUIST home page|Top of issue

Message 3: is language infinite?

Date: Mon, 30 Sep 91 17:02:17 MST
Subject: is language infinite?
In a recent LINGUIST posting, Alexis Manaster-Ramer writes:
 The same applies, of course, the Langendoen/Postal work: I still cannot
 believe that Terry and Paul could seriously claim that the issue of
 whether NL sentences are merely of unbounded length or of infinite
 length (and whether the collection of English sentences was countable
 or not) a factual question. But by the same token I cannot understand
 the self-righteous dismissal of their proposals by those who somehow
 possess the certitude (that I so notably lack) that NL sentences are
 only of finite length.
I cannot speak for Paul, but I agree with Alexis that the question of
the size of natural languages is a theoretical one. As a matter of
fact, we can all agree (even Jacques Guy), that NLs are at least of
some finite size. How much larger they are depends on whether one
considers that grammars of natural languages contain what Paul and
I called "size laws", of which the following are possibilities.
(For simplicity, I assume that these all deal with the notion of
1. There is some fixed, finite n, such that all sentences of all
natural languages are no longer than n. Something like this assumption
was made by Peter Reich in a paper in LANGUAGE in 1969.
2. All sentences of all natural languages are of finite length, but
there is no n, as in (1). This is the standard Chomskyan assumption.
3. There are no size laws. That is there are no priniciples of grammar
that either explicitly or implicitly limit the length of sentences in
natural languages. This is the assumption that Paul and I defend,
basically on simplicity grounds.
Paul and I show that given (3), and given a principle of grammar
concerning coordinate compounding, there are transfinitely many
sentences in all natural languages for which that principle holds.
The principle itself is quite simple and we think uncontroversial.
It says in effect if expressions of type X (such as the type of
declarative sentences) are compoundable by coordination, then for
any two or more expressions of that type, there is at least one
coordinate compound in the language, also of type X, made up of
those expressions. To see how this works in a simple case, let us
limit our (uncompounded) expressions of type X to the countably
infinite set B = <<(I know that)**n Babar is happy: n >= 0>>.
(Note: I use << and >> as set delimiters, to avoid transmission
difficulties with the curly brace symbols.) From the principle,
there is an expression of type X for every member of the power set
of B, excluding the empty set. Call this set B'. For example, B'
contains <<Babar is happy, I know that I know that Babar is
happy>>, and corresponding to this member is the expression, also
of the appropriate type, Babar is happy and I know that I know that
Babar is happy. (In fact, there are other expressions as well, but
we ignore these.) By standard assumptions of set theory, B' has
greater cardinality than B. Paul's and my result then follows,
unless one imposes a size law such as (2), which effectively (and
in our view arbitrarily) limits the application of the coordinate
compounding principle to sets of expressions of finite cardinality
(that is, one replaces the "two or more" in my formulation above by
the range 1 < x < infinity, where x ranges over the number of
expressions that are coordinately compounded).
Paul and I argue that the best theories of natural languages are those
which do not countenance size laws, which we claim have two properties:
1. they are not constructive (e.g., generative);
2. they support a realist (i.e., Platonist) view of natural languages.
The first property certainly must hold, but given the spirit of much
contemporary theorizing is less controversial than it was when we
published our book in 1984, if it was even controversial then, given
the rise of "principles and parameters" based theories of natural
languages during the 1980s. The second property, it now strikes me,
does not hold. Paul and I spilled a lot of ink trying to clarify
Chomsky's "conceptualist" view of natural languages, and having
clarified it, to show that it is incorrect. But it now strikes me as
quite easy to work out a coherent conceptualist theory of natural
languages that does not incorporate a size law. In fact, any
principles and parameters theory that does not do so, but that does
include what strikes me as the patently correct principle of
coordinate compounding, will yield the result that natural
languages (albeit, E-languages, in Chomsky's terminology) are of
transfinite size.
Mail to author|Respond to list|Read more issues|LINGUIST home page|Top of issue