FOM: More on canonical codings
JoeShipman@aol.com
JoeShipman at aol.com
Tue Sep 4 01:27:28 EDT 2001
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
More information about the FOM
mailing list