FOM: More on canonical codings

[JoeShipman@aol.com]

In my previous posting I suggested enumerating finite presentations of groups 
by first enumerating all possible relator words as follows
W1=x
W2=x'
W3=xx
W4=x''
W5=x'x
W6=xx'
W7=xxx
W8=x'''
W9=x''x
W10=x'x'
W11=x'xx
W12=xx''
W13=xx'x
W14=xxx'
W15=xxxx
W16=x''''
W17=x'''x
W18=x''x'
W19=x''xx
W20=x'x''
W21=x'x'x
W22=x'xx'
W23=x'xxx
W24=xx'''
W25=xx''x
W26=xx'x'
W27=xx'xx
W28=xxx''
W29=xxx'x
W30=xxxx'
W31=xxxxx
W32=x'''''
W33=x''''x
etc.

If you don't see the pattern, we are enumerating words in the 2-letter 
alphabet {x'} that begin with x, which is the same as counting in base 2 
using x for 1 and ' for 0, and then we are reinterpreting those words as 
words over the denumerably infinite alphabet {x, x',x'',x''',x'''',...}

The next step is to fold the doubly infinite set of letters 
{x1,x2,x3,...,x1^-1, x2^-1,x3^-1,...} into this alphabet in the obvious way, 
so that x corresponds to x1, x' corresponds to x1^-1, x'' corresponds to x2, 
and so on.

This gives a simple enumeration of presentations of groups -- 
{}
{W1}
{W2}
{W1,W2}
{W3}
{W1,W3}
{W2,W3}
{W1,W2,W3}
{W4}
{W1.W4}
etc.

EXCEPT that we have not listed the generators.  I had suggested that each 
presentation have only those generators x_i which appeared in some relation, 
but this is ugly and not particularly canonical, since we could also say that 
all generators up to the last one that appears in a relation are present.

However, for our original purposes of finding a canonical undecidable set, it 
is not necessary to use presentations of arbitrary finitely presented groups. 
 It is already the case that the triviality problem for 2-generator finitely 
presented groups is undecidable, so we only need to enumerate 2-generator 
presentations.  This is much easier, because we can enumerate the words on 
{a,b,a^-1,b^-1} (or, more compactly, {a,b,a',b'}) easily:

W1=a,
W2=b,
W3=a',
W4=b',
W5=aa,
W6=ab,
W7=aa',
W8=ab',
W9=ba,
W10=bb,
W11=ba',
W12=bb',
W13=a'a,
W14=a'b,
W15=a'a',
W16=a'b',
W17=b'a,
W18=b'b,
W19=b'a',
W20=b'b',
W21=aaa,
W22=aab,
W23=aaa',...

So the candidate for a canonical undecidable set of integers is: given N in 
base 2 as 2^i_1 + 2^i_2 + ... + 2^i_m, where the exponents are distinct, is 
the group presented by {a,b:W_i1,W_i2,...W_i_m} trivial?

I am not sure whether this is better than my earlier example which involved 
canonically enumerating Diophantine equations (given an integer as a product 
of powers of primes, interpret the exponent of the nth prime as the 
coefficient of the nth monomial, where monomials are enumerated by the same 
trick, with the exponent of the mth prime corresponding to the power of the 
mth variable).

Can anyone suggest other "canonical unsolvable problems"?

-- Joe Shipman