Notes by the Translator · Note A to Note G

UPON THE NONSOFIC,
and upon Structures which no
Finite Engine can Contain

with Diagrams of Operation, after the manner of the Analytical Engine
MMXXVI · every quantity herein computed before it was versified
The Analytical Engine weaves algebraical patterns just as the Jacquard-loom weaves flowers and leaves. A. A. L., Note A, 1843

She was speaking of what a finite engine can do. These Notes concern its complement: the patterns which no loom, of any breadth of card, will ever weave. The word for that boundary is sofic — from the Hebrew סופי, sofi, finite — and what lies past it is nonsofic.

NOTE A.  UPON THE WORD

In which a single Hebrew adjective is found to govern two provinces of mathematics which do not otherwise speak.

     sofic     : capturable by something FINITE
     nonsofic  : not so capturable, at any size whatsoever

     province I  . SHIFTS  . finite labelled graph      . automaton
     province II . GROUPS  . finite symmetric group     . permutation

     the same demand, made of two different objects:
     be imitated by a finite thing, to any accuracy asked.
Table I — the two provinces
A word was borrowed out of Hebrew tongue
to name the edge of what a machine may hold:
sofi, the finite — and the engine sung
its patterns only in that bounded fold.
Two provinces obey the single test.
The first is made of letters in a row;
the second, of the symmetries that rest
in groups too large for any card to know.

NOTE B.  UPON THE FOLLOWER SET

Wherein the whole question is reduced to a count, and the count is set down as an Operation Table in the usual columns.

     DEFINITION.   Let L be the set of admissible words.
                   For a word w, the FOLLOWER SET is

                        F(w)  =  { v  :  wv lies in L }

                   that is: all futures the past leaves open.

     CRITERION.    X is SOFIC   <==>   |{ F(w) : w in L }|  is FINITE

                   Each distinct follower set is one state
                   the engine must be able to occupy.
Table II — the criterion
 No. | Nature of      | Variables      | Variables      | Statement
 of  | Operation      | acted upon     | receiving      | of Results
 Op. |                |                | result         |
-----+----------------+----------------+----------------+-------------------------
  1  | enumerate      | n              | L(n)           | all legal words, length <= n
  2  | for each w     | w in L(n)      | F(w)           | the futures of that past
  3  | collect        | F(w)           | S              | S := set of distinct F(w)
  4  | count          | S              | k              | k := |S|
  5  | decide         | k over all n   | verdict        | bounded  -> SOFIC
     |                |                |                | unbounded-> NONSOFIC
Table III — the operation, in Note G's columns
Ask of a word: what may come after thee?
and gather every answer in a set.
Two words that leave the selfsame legacy
need but one state; the engine need not fret.
So count the sets. If they run out — rejoice,
the loom is built, the cards are finite, done.
And if they do not: there is no such voice
in brass or thought, and never shall be one.

NOTE C.  UPON A SHIFT WHICH CLOSES

Containing the golden mean, and the pleasing circumstance that the count of its words is the series of Fibonacci, whose ratio approaches the divine proportion.

     THE GOLDEN MEAN SHIFT.   Forbid the block  11.

     words of length n :  2   3   5   8  13  21  34  55  89 144 233 377 610

                          the Fibonacci numbers, entire

     ratio of successive counts ->  1.618034 ...  =  phi
     entropy                     h =  log2(phi)  =  0.694241914

     follower sets, n = 1 .. 9 :   2  2  2  2  2  2  2  2  2

                          TWO. FOREVER. THE ENGINE IS BUILT.
Table IV — computed, not recalled
Forbid two ones adjacent. Nothing more.
Then count what words remain at every size:
two, three, five, eight — the sequence known before
to Pisa's son, and to the nautilus.
Their ratio climbs to phi and there it stays;
the growth is log phi, a settled rate.
And all that wealth of ever-longer ways
is governed by a loom of states: but two.

NOTE D.  UPON A SHIFT WHICH DOES NOT

Wherein a rule of the utmost innocence — that two intervals be equal — defeats every engine that shall ever be constructed.

     THE MATCHED-RUN SHIFT.

          1 0^n 1 0^n 1     legal
          1 0^n 1 0^m 1     illegal whenever n /= m

     To judge it you must REMEMBER n. And n has no bound.

     follower sets, n = 1 .. 10 :

          2   4   7  10  13  17  21  25  29  32
           \  /  \  /  \  /  \  /  \  /  \  /
            2  3   3   3   4   4   4   4   3     <- first differences

     (the last difference falls only because the horizon of
      computation was set at 9; the sequence itself does not turn)

     CONCLUSION.  Propose any engine of k states.
                  Choose n > k. The engine has already failed.
Table V — the escaping count
The rule is small enough to hold in hand:
let the two silences be equal long.
No cruelty in it, nothing underhand —
and yet no engine ever sings that song.
For it must carry what it cannot store:
the length of what has passed, without a bound.
Build me a loom of thousands; I need more
by one — and one is all I ever found.
Two, four, then seven, ten, and thirteen — see
how patiently the states refuse to close.
This is not difficulty. This is degree:
a kind of pattern finite thread foregoes.

NOTE E.  UPON GROUPS, AND THEIR APPROXIMATION

The second province. The demand is the same; only the finite thing has changed, from a graph to a company of permutations.

     A GROUP G IS SOFIC IF:

       for every FINITE window F of its elements,
       and every tolerance eps > 0,
       there exists a permutation model M of some finite size,

         MULTIPLICATIVE :  dist( M(gh) , M(g)M(h) )  <  eps      g,h in F
         SEPARATED      :  dist( M(g)  , identity )  >  1 - eps  g /= 1

       where dist is the NORMALISED HAMMING distance:
       the fraction of points on which two permutations disagree.

     In words:  the group may be counterfeited by a finite one,
                as closely as you care to demand.

     GROMOV asked in 1899+100:  is EVERY group sofic?
     For twenty-seven years, not one counterexample was produced.
Table VI — soficity of a group, as it stands formalised
Take any handful of the group you please,
and any smallness you would care to name;
find me a finite company of these —
mere shufflings — that will nearly play the same.
Nearly: the product errs, but not by much.
Nearly: the stranger still behaves a stranger.
If every group submits to such a touch,
then infinity was never any danger.

NOTE F.  UPON THE ALGEBRA IN WHICH ONE IS TWO

The engine of the counterexample. An algebra of Leavitt, in which a single thing and a pair of things are indistinguishable, and the consequence thereof.

     THE BINARY LEAVITT ALGEBRA  L,  over the field of two elements.

     GENERATORS   s_1, s_2, t_1, t_2

     RELATIONS    t_i s_j  =  delta_ij            (i,j in {1,2})
                  s_1 t_1  +  s_2 t_2  =  1

     CONSEQUENCE  the map    a  |-->  ( t_1 a , t_2 a )
                  is an isomorphism

                        L  ~=  L (+) L

                  one equals two, in the manner of modules.

     Split the infinite binary tree at its root: you obtain
     two copies of the whole tree. The algebra says only this.

     CONSEQUENCE II.  L fails the INVARIANT BASIS NUMBER.
                      It is not directly finite.
                      And a SOFIC group's ring must be stably finite.
                      Therefore a group carrying 1 = 2 in its matrices
                      cannot be sofic.
Table VII — the relations, verbatim in ASCII
     WHY NINE.

     A COMPLETE binary prefix code with k words yields a ring
     isomorphism of matrices:

            M_k( L )   ~=   L

     A genuine 9-word complete code has word-lengths

            [ 3, 3, 3, 3, 3, 3, 3, 4, 4 ]
            sum of 2^-length  =  1.000000      (Kraft equality)

     The witness group is the ELEMENTARY MATRIX GROUP

            E_9( L ),  generated by   1 + a E_ij   (i /= j)

     The nine is the size of a complete prefix code.
     It is not a tuning constant.
Table VIII — the provenance of the number nine
There is an algebra in which the one
is not distinguishable from the two:
divide the endless tree, and you have done
no damage — both the halves are wholly true.
Such arithmetic no finite thing admits.
A shuffling of a hundred thousand cards
knows how to count, and counting is what sits
between this algebra and all its guards.
So build a group upon that faulted stone —
nine-fold, because nine leaves complete the tree —
and it will bear a burden all its own:
the finite cannot counterfeit it. Free.

NOTE G.  UPON THE ENGINE WHICH CHECKED IT

The last Note. Wherein the certificate is audited, found clean, and found — in one precise respect — insufficient.

     THE ARTEFACT.       NonSoficGroup.lean

     lines               34,440
     bytes            1,343,031
     sha256[:16]   f39b61646df1206d
     theorems             1,044
     definitions            334

     sorry                    0
     admit                    0
     axiom declarations       0
     native_decide            0

     THE PROPOSITION.

       there exists a group G, finitely presented,
       such that G is NOT sofic.

     THE CHAIN.   sofic  ==>  LEF (locally embeddable in finite groups)
                  the group is NOT LEF
                  therefore NOT sofic.
Table IX — the certificate, counted
     THE DISTINCTION WHICH MUST BE PRESERVED.

     PROVEN     : the stated proposition follows from the axioms.
     NOT PROVEN : that the stated proposition is the one intended.

                  A kernel verifies inference.
                  It does not verify meaning.

     The Engine can do whatever we know how to order it to perform.
     It cannot tell us whether we ordered the right thing.
Table X — the residue
The engine read the whole of it, and found
no step omitted and no gap concealed;
no sorry left to mark unhallowed ground,
no axiom smuggled in, no hand unsealed.
And that is much. It is not everything.
For proof attends the question that we set,
and no machine that ever ran can bring
assurance that the question was well met.
It weaves what we have ordered it to weave.
The flowers are exact; the leaves are true;
but whether it was this we meant to leave
upon the loom — that reading falls to you.
So: sofic is the finite's honest reach.
Nonsofic, what outruns it — now shown twice:
once in a rule too simple to impeach,
and once in nine leaves fallen from a tree.
ERRATUM, RECORDED. The tenth term of Table V is 32, and its difference from the ninth is 3 rather than 4. This is not a property of the shift. It is the horizon of computation, fixed at nine, beginning to truncate the follower sets. The sequence does not turn over; the instrument does. It is set down here because a table that hides its own edge is not a table but an assertion.
ON THE ARITHMETIC. Every figure in Tables IV, V and VIII was computed in this session before a line of verse was written — Fibonacci counts to n=16, the ratio to phi, the entropy log2(phi) = 0.694241914, the follower sequences by exhaustive enumeration, and the Kraft equality of the nine-word complete code to 1.000000. Tables I, II, III, VI, VII, IX and X are transcriptions or restatements, in ASCII, of definitions and of an artefact read directly.

ON THE ARTEFACT. NonSoficGroup.lean was fetched, hashed and searched, not summarised from report. Its headline theorem and its formalised definition of soficity were read in the original. Peer review of the result was pending at the time of writing, and Note G declines to pretend otherwise.

ON THE FORM. After the Notes of Ada Lovelace upon Menabrea's Sketch, 1843 — the numbered Notes, the Operation Table of Note G with its columns of number, nature, variables and statement of results, and the loom. The verse is not hers. The single quotation is, and is public domain.

ON THE TITLE. She signed her Notes only A. A. L. This one is signed the same way she described the work: by the translator — which is what any of us are, carrying a structure from where it lives into a language it did not choose.