Unrecognizable Sets of Numbers

Source: Minsky, M., & Papert, S. (1966). Unrecognizable Sets of Numbers. Journal of the Association for Computing Machinery, 13(2), 281-286. 

Unrecognizable Sets of Numbers

Marvin Minsky and Seymour Papert

Massachusetts Institute of Technology, Cambridge, Massachusetts
Journal of the Association for Computing Machinery, Vol. 13, No. 2 (April, 1966), pp. 281–286

Abstract. When is a set A of positive integers, represented as binary numbers, “regular” in the sense that it is a set of sequences that can be recognized by a finite-state machine? Let π_A(n) be the number of members of A less than the integer n. It is shown that the asymptotic behavior of π_A(n) is subject to severe restraints if A is regular. These constraints are violated by many important natural numerical sets whose distribution functions can be calculated, at least asymptotically. These include the set P of prime numbers for which π_P(n) ≈ n / log n for large n, the set of integers A(k) of the form n^k for which π_A(k)(n) ≈ n^(1/k), and many others. The technique cannot, however, yield a decision procedure for regularity since for every infinite regular set A there is a nonregular set A’ for which |π_A(n) – π_A'(n)| ≤ 1, so that the asymptotic behaviors of the two distribution functions are essentially identical.

1. Introduction

Let A be some set of positive integers written in binary notation. It is natural to ask what kind of computing machine could recognize [1] the set in the sense of deciding whether a given binary sequence represents a number belonging to A. The technique described in this note enables one to show that certain sets cannot be recognized by finite state automata (i.e., these sets are not “regular” [2]). The essential idea is this: Let π_A(n) be the number of members of A less than the integer n. It is shown that the asymptotic behavior of π_A(n) is subject to severe restraints if A is regular. These constraints are violated by many important natural numerical sets whose distribution functions can be calculated, at least asymptotically. These include the set P of prime numbers, for which π_P(n) ≈ n / log n for large n, the set of integers A(k) of the form n^k for which π_A(k)(n) ≈ n^(1/k), and many others. The technique cannot, however, yield a decision procedure for regularity, since for every infinite regular set A there is a nonregular set A’ for which |π_A(n) – π_A'(n)| ≤ 1, so that the asymptotic behaviors of the two distribution functions are essentially identical.

We consider here only the binary representation, so as to avoid pompous statements, but the same results can be obtained for any radix by changing all 2’s to r’s in the sequel. We warn readers not to confuse the statement that the primes written in binary form are not a regular set with the trivial statement that the set of strings of prime length is not regular.

2. Notation

(1) Consider the set of strings of 0’s and 1’s of which the first symbol is a 1, i.e., N = 1(0 ∨ 1)* using Kleene’s notation [2].

(2) Such strings are regarded ambiguously as integers to the base 2 or as strings of 0’s and 1’s. Numbers are presented to the machine high digits first. (This convention is innocuous since the set of reversed strings of a regular set is regular.)

(3) For any integer x, L(x) is the number of digits in x, i.e., 2^(L(x)-1) ≤ x < 2^L(x).

(4) Define x · y = 2^L(y) · x + y; that is, “.” is concatenation.

(5) A always denotes a set of positive integers and π_A(n) the cardinality of {x | 1 ≤ x ≤ n}.

(6) If A is regular, let M_A denote the reduced (i.e., minimal) automaton which recognizes A. In the discussion of any particular automaton M, Q is used for its set of states, q_0 for its initial state, Q_F for its set of “final states” (whose occurrence signifies acceptance of a string), and δ(q, x) for the state-transition function, i.e., the sequence x drives the automaton from state q to the state δ(q, x).

(7) A dead state is a state q such that δ(q, x) ∈ Q_F is satisfied by no x. (If the automaton is reduced this is equivalent to saying δ(q, x) = q for all x, since there is only one dead state in a minimal machine.)

(8) We are interested in subsets of N = 1(0 ∨ 1)* rather than in subsets of (0 ∨ 1)*. We consider as trivial the part of the automaton which merely verifies that the input sequence begins with a 1. We shall depart from the assumption of minimality by allowing a special dead state into which the machine is driven by an initial zero. In the sequel, “dead state” means dead state other than this special one.

(9) For convenience the following convention is adopted: For any set A, and any real number x, π_A(x) = π_A([x]), where [x] is the integral part of x. Where π_A(n) is a “natural” function, such as n / log n, x / log x will be used as an approximation of [x] / log [x] for very large values of x.

3. Theorems

First, the consequences of M having dead states will be shown.

PROPOSITION 1. Let M = M_A and suppose:
(a) δ(q_0, α) is a dead state,
(b) λ_0 = (α + 1) / α, and
(c) lim_{n → ∞} [ π_A(n) / π_A(λ_0 n) ] = θ.
Then θ = 1.

PROOF. Put n_m = 2^m · α. Then λ_0 n_m = 2^m (α + 1). By assumption (a), there is no β such that α · β ∈ A. In other words, no matter what m is chosen, there is no n ∈ A such that n_m = 2^m α ≤ n < 2^m α + 2^m = λ_0 n_m, where m = L(β). Then π_A(n_m) / π_A(λ_0 n_m) = 1, because there are no members of A between n_m and λ_0 n_m. But { π_A(n_m) / π_A(λ_0 n_m) } is an infinite subsequence of the sequence, supposed by assumption (c) to be convergent, { π_A(n) / π_A(λ_0 n) }. It follows that the limit, θ, of this sequence (if the limit exists) is 1.

The underlying fact, then, is that dead states produce large gaps in the sequence of numbers recognized by a machine. Below, it is shown that if there is no dead state, the gaps cannot grow in the same manner.

We immediately deduce the weakened, but easier-to-use:

PROPOSITION 2. If π_A(n) / π_A(λ n) → θ(λ) for all real λ and if θ(λ) = 1 only if λ = 1, then A cannot be a regular set whose reduced automaton has a dead state.

In some interesting cases (see below), π(n) / π(λ n) fails to converge. We can still sometimes use a sharper but less elegant criterion:

PROPOSITION 3. Let a_r be the r-th member of A in order of magnitude. Then if lim_{r → ∞} [ (a_{r+1} – a_r) / a_r ] = 0, A cannot be a regular set whose reduced automaton has a dead state.

PROOF. Suppose that A is a regular set whose reduced automaton has a dead state, and let α, λ_0, and n_m be defined as in the proof of Proposition 1. Denote by k_m the number of members of A smaller than n_m, i.e., k_m is the largest integer such that a_{k_m} < n_m. Since no member of A can lie between n_m and λ_0 n_m, we have: a_{k_m + 1} ≥ λ_0 n_m. Thus:
(a_{k_m + 1} – a_{k_m}) / a_{k_m} ≥ (λ_0 n_m – n_m) / n_m = λ_0 – 1 = 1 / α.
It follows that (a_{r+1} – a_r) / a_r cannot converge to 0 as r → ∞.

Finally, we look at the other side of the coin; what happens if M has no dead state?

PROPOSITION 4. If A is regular and M has no dead state, then π_A(n) / n ≥ 2^(-2N), where N is the number of states of M_A. Thus the density of A cannot converge to zero.

PROOF. For each integer t we shall define a 1-1 into map g: g: [2^(Nt), 2^(Nt+1)) → [2^(Nt), 2^(Nt+N)) ∩ A, where [a, b) denotes the interval a ≤ x < b. For any α ∈ [2^(Nt), 2^(Nt+1)), let β_α be the smallest integer for which α · β_α ∈ A. Such a β_α must exist because δ(q_0, α) is not dead. Moreover, β_α < 2^N because the shortest path from δ(q_0, α) to a member of Q_F cannot be longer than N – 1. It follows that α · β_α < 2^(Nt+N) so that α · β_α ∈ [2^(Nt), 2^(Nt+N)) ∩ A. Thus if we define g(α) = α · min { β | α · β ∈ A }, g has the required range. To see that it is 1-1, we simply note that α is recoverable as the first Nt digits of g(α).

It follows that [2^(Nt), 2^(Nt+N)) ∩ A contains at least as many members as [2^(Nt), 2^(Nt+1)). Therefore, π_A(2^(Nt+N)) ≥ 2^(Nt+1) – 2^(Nt) = 2^(Nt). Now consider an arbitrary number n. For some t, n ∈ [2^(Nt), 2^(N(t+1))), and since π_A(x) increases monotonically:
π_A(n) / n ≥ π_A(2^(Nt)) / 2^(N(t+1)) ≥ 2^(N(t-1)) / 2^(N(t+1)) = 2^(-2N).

Combining this result with the consequences of Propositions 2 and 3 leads to the following Criterion.

CRITERION. To prove that a set, A, is not regular, it is sufficient to verify Condition 1 and Condition 2 or 2′:
• Condition 1. π_A(n) / n → 0 as n → ∞
• Condition 2. π_A(n) / π_A(λ n) → θ(λ) as n → ∞ and θ(λ) ≠ 1 for all λ ≠ 1.
• Condition 2′. (a_{n+1} – a_n) / a_n → 0 as n → ∞.
If A is regular, by Proposition 1 it has a dead state but by Proposition 2 or 3 it has none.

4. Applications

First, some examples are discussed that can be settled using the Criterion of Section 3.

Example 1. A = { m^k | k a fixed integer }. Clearly π_A(n) ≈ n^(1/k) so that:
(1) π_A(n) / n → n^(1/k – 1) → 0 as n → ∞
(2) π_A(n) / π_A(λ n) → λ^(-1/k) ≠ 1 for all λ ≠ 1.
Therefore A is not regular. (This application includes the result proved by Ritchie [3] by ad hoc arguments on the set of perfect squares in binary.)

Example 2. Let P be the set of prime numbers. It is well known that π_P(n) ≈ n / log n. Thus π_P(n) / n ≈ 1 / log n → 0 as n → ∞, satisfying Condition 1. On the other hand,
π_P(n) / π_P(λ n) ≈ (n log λn) / (λ n log n) = (log λ + log n) / (λ log n) → 1 / λ ≠ 1 (for λ ≠ 1).
Again, Conditions 1 and 2 are satisfied; therefore, P is not regular.

Example 3. Let B be the set of all prime powers, i.e., B = { p^m | p prime, m an integer }.
Write B as: B = B_1 ∪ B_2 ∪ … ∪ B_k ∪ … where B_k = { p^k | p prime }.
Then for each k we have, exactly, π_{B_k}(n) = π_P(n^(1/k)).
To compute π_B(n), first note that if n_0 ∈ B, n_0 < n then for exactly one k and p, n_0 = p^k < n, so that:
k < log_p n ≤ log_2 n, i.e., n_0 ∈ B_1 ∪ … ∪ B_{[log_2 n]}.
It follows that π_B(n) = π_P(n) + π_P(n^(1/2)) + … + π_P(n^(1/[log_2 n])).
Thus π_B(n) ≈ (n / log_e n) + (2 n^(1/2) / log_e n) + … + ([log_2 n] n^(1/[log_2 n]) / log_e n).
Since 2 n^(1/2) + … + [log_2 n] n^(1/[log_2 n]) < 2 (log_2 n)^2 n^(1/2), and ((log_2 n)^2 n^(1/2)) / log n → 0 as n → ∞, we have π_B(n) ≈ n / log_e n ≈ π_P(n).
Thus the set B has the same asymptotic density as P and is not regular. A similar argument shows that the set { n^m | n, m integers, m ≥ 2 } is not regular.

Example 4. We now illustrate the use of the Criterion in cases where the ratio π_A(n) / π_A(λ n) fails to converge. Let C be the set of binary palindromes, i.e., sequences invariant under reversal. To show that C is not regular, first verify that Condition 1 is satisfied. This is easy; since the first half of the binary digits of an n-digit palindromic number is determined by the last half, neglecting the small odd-even effects, then π_C(n) / n ≈ (√n) / n → 0. Then, by Proposition 1, if C is regular it must be recognized by an automaton with a dead state. But this is impossible since every sequence can be completed to produce a palindrome of twice its length. Q.E.D.

One could, although it would be foolish to do so in this case, come to the same conclusion by using Condition 2′. To do so, estimate the difference a_{n+1} – a_n between the n-th palindrome and the next. If a_n is of even length, 2k, it can be written a_n = b_n 2^k + b̂_n, where b̂_n is the sequence of digits of b_n written in reverse order. If a_n is of odd length, 2k+1, it has the form a_n = b_n 2^(k+1) + δ 2^k + b̂_n, where δ is 0 or 1. It is easy to see that b_{n+1} is either b_n or b_n + 1, so that in each case a_{n+1} – a_n cannot be larger than the order of √a_n. It follows that (a_{n+1} – a_n) / a_n → 0 as n → ∞.

It is interesting to compare this with the (regular) set of sequences of doublets, i.e., sequences like 00110011110011. This set has roughly the same sort of global distribution as the palindromes; but the fine structure of its distribution of gaps causes it (rightly) to elude the Criterion.

The following examples show how the Criterion can fail to yield useful information.

Example 5. Let A(a) be the set of all powers of some fixed integer a, i.e., A(a) = { a^k | a fixed }.
Then log_a(n) – 1 ≤ π_A(n) < log_a(n) so that π_A(n) ≈ log_a(n). Condition 1 is satisfied.
However, π_A(n) / π_A(λ n) ≈ log_a n / log_a λn → 1 as n → ∞, so Condition 2 fails, and so does Condition 2′: (a_{n+1} – a_n) / a_n = a – 1. The Criterion gives no information in this case. In fact A(2) is regular (for a binary machine), while A(3) is not (and vice versa for a ternary machine).

Example 6. Periodic sequences such as 101, 101101, 101101101,… have π(n) = k log n so that π(n) / π(λ n) → 1. Condition 1 fails. (All such sets are regular.)

5. Impossibility of a Converse

Let A be any infinite regular set with an infinite complement and let φ(x) be a noncomputable function with values 0 and 1. Let A’ be the subset of A defined by x ∈ A’ if x ∈ A and (x + 1) ∉ A. A’ is infinite. Let g(n) be an enumeration of A’, without repetitions, and define A* by the conditions:
(1) If x ∈ (A – A’), x ∈ A*
(2) If x = g(n) ∈ A’, then put x in A* if φ(n) = 0; otherwise put x + 1 in A*.

It is clear that A* is not computable, and a fortiori not regular; otherwise φ(n) could be computed by observing a machine that recognizes A* since φ(n) = 0 if and only if g(n) ∈ A*. But π_A(n) and π_{A*}(n) differ by, at the most, 1. Thus, while tests based on asymptotic density can give evidence against regularity, they cannot give evidence for regularity.

6. Upper Bound of Growth Rate of Regular Sets

For the sake of completeness, the following more superficial result is included.

PROPOSITION 5. If A is regular and infinite, there is some K > 0 such that π_A(n) > K log n.

PROOF. Suppose A is regular and that M_A has N states. Let N_0 be any integer. Then there is some x ∈ A with N_0 ≤ L(x) ≤ N_0 + N. To see this, note first that if δ(q_0, y) were dead for every y with L(y) = N_0, then A would be finite. So we can choose a y with L(y) = N_0 and for which y · y_1 ∈ A for some y_1. But if y_1 is chosen to produce the shortest path from δ(q_0, y) to Q_F, then L(y_1) < N. Thus x = y · y_1 is in the stated range.

It follows that there is at least one member of A in each of the intervals [1, 2^N), [2^N, 2^(2N)), …, [2^(kN), 2^((k+1)N)). Therefore, π_A(2^(tN)) ≥ t, and hence, π_A(n) ≥ (log n) / N = K log n.

Example 7. It follows from Proposition 5 that sets such as A = { 2^(2^k) }, which increase “faster than exponentially,” cannot be regular.

7. Discussion

Many questions remain. To what extent will the same kind of methods work on, say, pushdown machines? The criteria will have to change in detail (for example, the palindromes would be recognizable now), but we are inclined to suppose that the pushdown machines will also fail to recognize the arithmetically interesting examples, and that the gap and density arguments can be refined to show this.

We are curious as to whether one can show that { w | n is prime } is not regular by much more elementary means. If not, this might suggest some nontrivial relation between automata theory and number-theoretical areas, such as the theory of rational approximations.

References

1. RABIN, M., AND SCOTT, D. Finite automata and their decision problems. IBM J. Res. Develop. 3 (1959), 114–125.

2. KLEENE, S. C. Representation of events in nerve nets and finite automata. In Automata Studies, Shannon, C. E., and McCarthy, J. (Eds.), Princeton U. Press, Princeton, N. J., 1956, pp. 3–41.

3. RITCHIE, R. W. Finite automata and the set of squares. J. ACM 10, 4 (Oct. 1963), 528–531.