John Horton Conway 1937–2020

April 14, 2020

tags: Collatz conjecture, complexity, FRACTRAN, in memoriam, John Conway, Life, Logic, memorial, modular arithmetic, Princeton, set theory, surreal numbers, Turing universality, undecidability

An appreciation

Names for large numbers source

John Horton Conway just passed away from complications of COVID-19. We are all saddened by this news, and we hope you all are doing your best to stay safe and help others cope.

Today Ken and I thought we would reflect on some of Conway’s many contributions and emphasize three in which we see connections to computational complexity.

Conway was a Fellow of the Royal Society, and was the first recipient of the London Mathematical Society’s Pólya Prize. His nomination to the Royal Society reads:

A versatile mathematician who combines a deep combinatorial insight with algebraic virtuosity, particularly in the construction and manipulation of “off-beat” algebraic structures which illuminate a wide variety of problems in completely unexpected ways. He has made distinguished contributions to the theory of finite groups, to the theory of knots, to mathematical logic (both set theory and automata theory) and to the theory of games (as also to its practice).

A Life Force

Conway may be most noted for his game of Life. This is a two-dimensional cellular automaton. Conway invented it in 1970, which he rounded up from 1969. The game—and Martin Gardner’s 1970 column on it in Scientific American—made him famous in the wider community. The website conwaylife.com and several others link to more information than we could digest in a lifetime.

We want to emphasize instead how Conway was a special force in mathematics. He applied an almost elementary approach to deep hard problems of mathematics. This is a unique combination. There have been mathematicians who worked on deep problems and also on recreational math, but few who established integral flows across the boundary between them. Conway infused both with magic in a way conveyed by an iconic photograph of his Princeton office in 1993:

Guardian via Dith Pran, NY Times source

What Ken remembers is how accessible Conway was outside his office. “I know I met him at least once while I was an undergraduate at Princeton in 1979 or 1980, though this is overlaid by a memory of finding just him and a few others in the Fine Hall tea room when I was there for my tenth reunion in 1991. My most evocative memory is when Conway gave an evening talk to the undergraduate mathematics club at Oxford when I was there sometime after 1981. It was relatively sparsely attended, perhaps because it was literally a dark and stormy winter night. But after his lecture we all got to huddle around him for another hour in the tea room as he regaled us with stories and mathematical problems.”

We also remember that Conway was one of Andrew Wiles’s main confidants during the months before Wiles announced his proof of Fermat’s Last Theorem in June 1993. Here is a transcript of a PBS Nova documentary on the proof in which Conway appears prominently. Ken has picked out two of Conway’s other contributions that we feel may have untapped use for research in complexity theory.

Conway’s Numbers

One of this blog’s “invariants” is first-name last-name style, thus “Godfrey Hardy” not “G.H. Hardy.” But we make an exception in Conway’s case. Partly this owes to how his initials were amplified by Donald Knuth in his novella Surreal Numbers:

In the beginning, everything was void, and J.H.W.H. Conway began to create numbers.

Besides the void (that is, ${\emptyset}$ ), the creation uses the idea of a left set ${L}$ and a right set ${R}$ . Every number has the form ${\langle L~|~R \rangle}$ . The initial number is

$\displaystyle \langle \emptyset ~|~ \emptyset\rangle = 0.$

Once a number is generated, it can be in the ${L}$ or ${R}$ of other numbers. Thus, next come

$\displaystyle \begin{array}{rcl} \langle 0 ~|~ \emptyset \rangle &=& 1\\ \langle \emptyset ~|~ 0 \rangle &=& -1. \end{array}$

You might think of ${\langle 0 ~|~ 0 \rangle}$ next, but it violates the invariant

$\displaystyle (\forall \ell \in L)(\forall r \in R)\neg (r \leq \ell).$

which defines an ${\langle L~|~R \rangle}$ form to be a number.

The relation ${\leq}$ is inductively defined for ${a = \langle L_a ~|~ R_a \rangle}$ and ${b = \langle L_b ~|~ R_b \rangle}$ by

$\displaystyle a \leq b \quad\equiv\quad (\forall \ell_a \in L_a)(\forall r_b \in R_b)\neg(b \leq \ell_a \;\lor\; r_b \leq a).$

That is, no member of the left-set of ${a}$ “bumps” ${b}$ (in the sense of rowing races) and ${a}$ does not bump any member of the right-set of ${b}$ . Note that ${R_a}$ and ${L_b}$ are not involved—they already behave correctly owing to the invariant. The numbers ${a,b}$ are equal if ${a \leq b}$ and ${b \leq a}$ both hold. The rule for addition is

$\displaystyle a + b = \langle (L_a \boxplus b) \cup (a \boxplus L_b) ~|~ (a \boxplus R_b) \cup (R_a \boxplus b) \rangle,$

where ${L_a \boxplus b = \{\ell_a + b: \ell_a \in L_a\} = b \boxplus L_a}$ and so on. The logical rule ${\emptyset \boxplus a = \emptyset}$ for any ${a}$ makes the definition of addition well-founded. This yields the numerical fact

$\displaystyle 0 + 0 = \langle (\emptyset \boxplus 0) \cup (0 \boxplus \emptyset) ~|~ (\emptyset \boxplus 0) \cup (0 \boxplus \emptyset) \rangle = \langle\emptyset ~|~ \emptyset\rangle = 0.$

It is immediate that ${+}$ is commutative. There is also a rule for multiplication but addition gives us enough to talk about here.

Redundancy and Simplicity

It is straightforward to compute that ${0 + 1 = 1}$ and ${-1 + 0 = -1}$ . Now consider:

$\displaystyle -1 + 1 = \langle (\emptyset \boxplus 1) \cup (-1 \boxplus \{0\}) ~|~ (-1 \boxplus \emptyset ) \cup (\{0\} \boxplus 1)\rangle = \langle -1 ~|~ 1\rangle.$

This is a legal number. You can check that the relations ${\langle -1 ~|~ 1\rangle \leq 0}$ and ${0 \leq \langle -1 ~|~ 1\rangle}$ both hold. Thus—as a number rather than a “form”—the number ${\langle -1 ~|~ 1\rangle}$ equals ${0}$ .

That seems to make sense since ${0}$ is the average of ${-1}$ and ${1}$ , but now compute ${2 = 1 + 1}$ as a formal Conway number and consider ${c = \langle -1 ~|~ 2\rangle}$ . This also satisfies the relations ${c \leq 0}$ and ${0 \leq c}$ , so ${c}$ must likewise equal ${0}$ . Thus ${\langle L ~|~ R \rangle}$ is not some kind of numerical interpolation between ${L}$ and ${R}$ . The interpretation that grabbed my imagination as a teenager in 1976 is that:

${\langle L ~|~ R \rangle}$ equals the simplest number that is between ${L}$ and ${R}$ .

This is especially evocative in cases like ${\langle 1 ~|~ \emptyset \rangle}$ , which is what one gets by computing ${1 + 1}$ . In general, ${m+1}$ is the simplest number between ${m}$ and ${\emptyset}$ . Conway made this a theorem by giving each number a set-theoretic ordinal for its “time of generation” and proved that ${\langle L ~|~ R \rangle}$ always equals a (the) least-ordinal number ${c}$ such that ${\ell \leq c \leq r}$ for every ${\ell \in L}$ and ${r \in R}$ .

Conway’s rules allow ${L}$ and ${R}$ to be infinite sets—any sets of numbers built by the rules of set theory. Then not only do all real numbers emerge at ordinal times, so do infinitesimals and further richness of structure. We should remember that Conway began as a set theorist with a dissertation under Harold Davenport titled Homogeneous ordered sets. All Conway numbers with finite creation times are dyadic rational numbers, which may seem trivial from the standpoint of set theory, but those are akin to binary strings.

What became magic was how Conway’s rules characterize games. Through games we can also interpret forms like ${\langle 0 ~|~ 0 \rangle}$ that are not numbers. I did not know about complexity when I purchased Conway’s book On Numbers and Games around 1980, let alone the connections between games and complexity. The book has a lot of depth that might be useful to complexity theory. To quote Peter Sarnak, per this article by Conway’s biographer Siobhan Roberts on Conway’s meeting with Kurt Gödel:

The surreal numbers will be applied. It’s just a question of how and when.

Modular Programming

Most of us know that the conditional-jump instruction

if (x == 0) goto k

where k is the label of another instruction, creates a universal programming language when added to the usual programming primitives of assignment, sequencing, and simple arithmetic. Conway was a maven of the “modular-jump”:

if (x == 0 mod m) goto k.

In complexity theory we know that mod- ${m}$ gates having 0-1 inputs define the idea of ${\mathsf{ACC}}$ circuits, with ${\mathsf{ACC}^0}$ denoting problems solved by families of these circuits having fixed depth and polynomial size. If we don’t insist on fixed depth and unary inputs, we get modular programs. They are more complex than ${\mathsf{ACC}^0}$ circuits, but we can learn from what can be done concretely with them.

Conway created a particular form of modular programs in a language he called FRACTRAN. A program is just a list of positive fractions ${\frac{a_r}{b_r}}$ in lowest terms. The input is an integer ${n}$ held in a separate register. Each fraction represents the code line

$\displaystyle \text{if } (n*a_r \equiv 0 \pmod{b_r}) \{ n = n\frac{a_r}{b_r}; \text{goto start} \};$

In other words, each iteration takes the first fraction ${f}$ such that ${nf}$ is an integer and updates ${n}$ to ${nf}$ ; if there is no such fraction then the program exits and outputs ${n}$ .

For example, the following FRACTRAN program given in Wikipedia’s article implicitly computes integer division:

$\displaystyle \left[\frac{91}{66},~\frac{11}{13},~\frac{1}{33},~\frac{85}{11},~\frac{57}{119},~\frac{17}{19},~\frac{11}{17},~\frac{1}{3}\right].$

The notation is unary: The input ${x}$ has the form ${2^n 3^d 11}$ and the ouput is ${5^q 7^r}$ where ${n = qd + r}$ with remainder ${r < d}$ . This already hints the fact that FRACTRAN is a universal programming language. Powers of primes serve as memory registers. The following program computes the Hamming weight ${k}$ of the binary expansion of a natural number ${x}$ encoded as ${2^x}$ , returning the value ${13^k}$ :

$\displaystyle \left[\frac{33}{20},~\frac{5}{11},~\frac{13}{10},~\frac{1}{5},~\frac{2}{3},~\frac{10}{7},~\frac{7}{2}\right].$

This might help bridge to our notions of ${\mathsf{ACC}}$ . The Wikipedia article does a good job of de-mystifying the fractions in terms of their actions on the prime-power registers under the unary-style encoding. We wonder what happens when we try to work directly with binary encodings.

The Collatz Example

The famous “ ${3n+1}$ ” problem of Lothar Collatz is a case in point. It iterates the function

$\displaystyle T(n) = \begin{cases} \frac{3n+1}{2} & \text{if } n \text{ is odd} \\ \frac{n}{2} & \text{if } n \text{ is even} \end{cases}$

The following FRACTRAN program given by Kenneth Monks iterates ${T(n)}$ under the unary encoding ${2^n}$ :

$\displaystyle \left[\frac{1}{11},~\frac{136}{15},~\frac{5}{17},~\frac{4}{5},~\frac{26}{21},~\frac{7}{13},~\frac{1}{7},~\frac{33}{4},~\frac{5}{2},~\frac{7}{1}\right].$

Note that since the last fraction is an integer the program runs forever. If ${n = 1}$ so that the input is ${2}$ , it would go ${2 \rightarrow 5 \rightarrow 4 \rightarrow 33 \rightarrow 3 \rightarrow 21 \rightarrow 26 \rightarrow 14 \rightarrow 2 \cdots}$ and thus cycle, unless we stop it. The powers of ${2}$ that appear in its output give the desired sequence.

More natural to us, however, is the following modular program—which can use binary or any notation:

start: if (n == 1) { halt; } if (n == 0 mod 2) { goto div; } n = 3*n + 1; div: n = n/2; goto start;

One can generalize the Collatz problem to moduli ${m > 2}$ . For each ${k < m}$ we have a linear transformation ${n \mapsto c_k n + d_k}$ that always gives an integer value when ${n \equiv k \pmod{m}}$ . We want to know about the orbits of numbers ${n}$ under this iteration.

In fact, this is exactly what FRACTRAN does. Take ${m}$ to be the least common multiple of the denominators ${b_r}$ in a FRACTRAN program ${[\frac{a_r}{b_r}]}$ . Then for each ${r}$ we can list the remainders ${k}$ that are multiples of ${b_r}$ and we get ${c_k = \frac{a_r}{\gcd(k,m)}}$ , with ${d_k = 0}$ . The Turing-universality of FRACTRAN then proves a general theorem Conway stated in 1972:

Theorem 1 Generalized Collatz-type problems for moduli ${m > 2}$ are undecidable.

Several followup papers have proved stronger and more particular forms of the undecidability. The paper by Monks linked above leverages the unary encoding to show that having ${d_k = 0}$ is essentially without loss of generality for universality; it is titled “ ${3x+1}$ Minus the ${+}$ .”

Having digested universality, it is natural to wonder about complexity. Can we use modular programming to achieve stronger connections between number theory and complexity classes—classes above the level of ${\mathsf{ACC}^0}$ , say? One possible mode of connection is exemplified by this paper from STACS 1994, which both Dick and I attended. We wonder whether the kind of connection noted by Terry Tao in his tribute to Conway can also smooth the way to understanding ${\mathsf{MIP^* = RE}}$ .

Open Problems

Conway posed many open problems himself. Here is a list of five for which he posted cash rewards in the manner of Paul Erdős. The fifth was recently solved. The fourth can be stated in one sentence:

If a set of points in the plane intersects every convex region of area 1, then must it have pairs of points at arbitrarily small distances?

Our condolences go out to his family and all who were enthralled by him in the mathematical world. We could talk endlessly about his impact on mathematics education—even about simple things like how to prove that ${\sqrt{2}}$ is irrational—or try to tangle with his applications of the “Monster” group to modular forms, but those must be for another time. Also see Scott Aaronson’s tribute and its comments section for many more stories and items.

[some small word and format changes, added link to Scott and may add others as time allows]

13 Comments leave one →

KWRegan permalink

April 14, 2020 3:39 pm

Some footnotes. One more personal story regarding Life is that once my Christmas my wish list included a hundred-plus wood chips cut square, which my mother went to great lengths to fulfill. I had worked out that coloring one side black for live cells, using the blank side for newborn cells, and standing dead cells on end for easy culling, would be quicker and more reliable than using the kinds of counters I had to hand. Indeed, a final pass of flipping blank to black before the next iteration would improve on Conway’s own swapping out white stones for black stones on a Go board. But I soon gained access to computers, including a TRS-80 at home, and both speed and reliability were beyond comparison. I must say, however, that computer versions lose a sense of intimacy I felt the first time using pencil and eraser.

Left on the cutting-room floor were discussion of the time overheads for the Life-to-TM and TM-to-Life simulations and more details on the Conway numbers. References for the former include this by Paul Rendell and an earlier paper by Jean-Philippe Rennard on simulating logic gates, which appeared in a book titled Collision-Based Computing. But I recall a more-specific investigation of the time overheads as being quadtratic, which is “somewhere in my office” (when am I going there again?) but I could not find online. Regarding the latter, the set equation ${a + \emptyset = \emptyset}$ looks strange in that this absorption usually pertains to multiplication/concatenation, not addition. This is why I chose the symbol ${\boxplus}$ to denote it. It occurred to me that if ${\emptyset}$ on the left were replaced by “ ${-\infty}$ ” and ${\emptyset}$ on the right by “ ${+\infty}$ ” then the absorption under addition would look right. But one cannot use “infinity” cavalierly because ${\langle L ~|~ R\rangle}$ is used with ${\omega}$ and other infinite sets as ${L}$ and/or ${R}$ . Perhaps not the “void” but plus-and-minus versions of Cantor’s “Ultimate Aleph” superintend the creation. I chose angle brackets rather than the more-standard ${\{ L ~|~ R\}}$ notation to avoid slurring e.g. ${\langle \{0\} ~|~ R\rangle}$ to ${\{0 ~|~ R\}}$ but maybe there is no harm in doing so.

Loading...

Reply
vznvzn permalink

April 14, 2020 8:40 pm

what a blow! curse this virus! conway was a huge inspiration to me, esp his number theoretic + computational work. he invented a “Fractran language” proof in the ~1970s that showed the undecidability of number theoretic propositions similar to Collatz, generalizing the basic structure. this work is rarely cited but think it is quite substantial esp in its relation to hilberts 10th problem which is quite celebrated.

another amazing proof of conway was proving Life is Turing complete. am not sure this proof was ever written down…? think the history of this needs to be better documented. it is built out of the idea of constructing a Turing machine out of Life-gadgets like gliders and glider guns where the glider positions determine 0/1 encoding. there was a web page by Rendell years ago that rendered a variant.

conway downplayed the signficance of the Life discovery but feel it was not so much false modesty but *unwarranted* modesty. its a discovery of 1st rate. the tendency of other mathematicians to downplay its significance is unwarranted. its a precursor to understanding concepts of complexity and emergence that marked 2nd 20th century math. in my pov its as much significance to math as the Lorenz attractor equations which are more celebrated.

was reading Wolfram recently who was clearly highly influenced by conway with cellular automata but does not (seem to) cite Conway much. would be very interested to understand better/ in more detail the interrelationship/ cross pollination between these two.

hope that someone writes a large, definitive popsci or higher level biography of Conway (ideally with lots of juicy math detail + citations), will be the 1st in line to buy that.

Loading...

Reply
Nabendu Chaki permalink

April 14, 2020 9:40 pm

Thanks for this article… We could know so many things…
Thanks to Ken and Richard! Hope you are fine if I share this for others to know.

Loading...

Reply
- KWRegan permalink
  
  April 15, 2020 12:44 pm
  
  Nabendu, yes, absolutely fine…
  
  Loading...
  
  Reply
jack permalink

April 15, 2020 1:28 pm

As a regular reader – though not a regular understander – of your blog I just wanted to leave a link to the most lively article I found describing John CONWAY:
https://www.theguardian.com/science/2015/jul/23/john-horton-conway-the-most-charismatic-mathematician-in-the-world

Take care of yourselves.
Jack

Loading...

Reply
- rjlipton permalink*
  
  April 15, 2020 9:24 pm
  
  Dear jack:
  
  We appreciate your being a regular reader. We also thank you for the link. Conway was special.
  
  Best and stay safe.
  
  Dick
  
  Loading...
  
  Reply
john gray permalink

April 27, 2020 9:32 am

Not a comment so much as a couple of questions. Clearly Conway was familiar with quantum mechanics (QM) as the free will theorem demonstrated. I have always wondered if Conway was influenced by Dirac hole theory in his notion of the void? In addition, the left right notation has produces numbers in a manner analogous to to raising and lowering operators in the algebraic formulation of some problems in QM such as the harmonic oscillator as well as the some formulations in quantum field theory. Does any one know he discussed this in his popular lectures or his discussions of surreal numbers? I am sure that we will see surreal numbers in formulations in physics someday. “

Loading...

Reply
- RJLipton+KWRegan permalink
  
  May 16, 2020 1:54 pm
  
  JG, I don’t know enough to answer. You did pick up on some of my musings during the writing about whether there is any relation between the left-right notation and Dirac notation. I decided no—indeed, per my followup comment, I became less sure that “the void” is the correct implicit quantity—but decided to keep the Dirac brackets because I felt the standard braces cause other confusion about what is a set and what is not. (Ken writing this.)
  
  Loading...
  
  Reply
  - jeg permalink
    
    May 18, 2020 3:11 pm
    
    thanks JEG
    
    May your blog live long and prosper.
    
    Loading...

	T.D. Nguyen on Just Jim
	joe12361 on Just Jim
	T Nguyen on COMPUTATION, LOGIC, AND INFORM…
	Umayr on 1968 vs 2024
	javaid aslam on 1968 vs 2024
	Ian Z aka nobrowser on 1968 vs 2024
	Enough is enough on 1968 vs 2024
	rjlipton on An Open Problem
	Jordan on An Open Problem
	Jon Awbrey on An Open Problem
	Blog Runner on An Open Problem
	William Gasarch on An Open Problem
	DL on An Open Problem
	Jon Awbrey on An Open Problem
	An Open Problem \| Gö… on Cargo Cult Redo

a personal view of the theory of computation

John Horton Conway 1937–2020

A Life Force

Conway’s Numbers

Redundancy and Simplicity

Modular Programming

The Collatz Example

Open Problems

Like this:

Related

Trackbacks

Leave a ReplyCancel reply

Subscribe to Gödel’s Lost Letter

Our Book

Recent Posts

Top Posts

Recent Comments

Blogroll

Archives

Sitemeter

a personal view of the theory of computation

John Horton Conway 1937–2020

A Life Force

Conway’s Numbers

Redundancy and Simplicity

Modular Programming

The Collatz Example

Open Problems

Share this:

Like this:

Related

Trackbacks

Leave a ReplyCancel reply

Subscribe to Gödel’s Lost Letter

Our Book

Recent Posts

Top Posts

Recent Comments

Blogroll

Archives

Sitemeter

Discover more from Gödel's Lost Letter and P=NP