On Tue, 23 Sep 2003, Jack Smith wrote:
Given a binary string (i.e. a finite sequence of 0's and 1's) we
choose any two digit substring 01 and replace it by a string of the
form 100...0 using an arbitrary (but finite) number of zeros. Prove
by induction that this transformation can not be performed infinitely
many times, i.e. this sequence of transformations must terminate for
any input string.
That is any finite string.
Transform the string into a polynomial
a_n x^n + ... + a_1 x + a_0
where a_j is the number of 0's before x^j which represents a 1.
Now every transformation preserves the number of 1's.
Thus the exponents of the polynomial are unchanged.
A transformation upon 01 for the j^th 1 is
a_j x^j + a_(j-1) x^(j-1) -> (a_j - 1)x^j + (a_(j-1) + c)x^(j-1)
for positive integer c.
This reminds me of Goodstein's theorem, the simplest theorem
independent of Peano's axioms.
The induction is complex. Every transformation increases a coefficient at
the cost of decreasing by one the previous coefficient.
One way to proceed is to consider the polynomial in x as an ordinal
polynomial in w. Thus every transformation decreases the ordinal
represented by the polynomial. If the transformations could proceed
forever then there would be an infinite descending sequences of ordinals,
which is impossible as the ordinals are well ordered with a first
element.
--
Another way to think the same is let the string be
(a_n, ... a_1, a_0) where
a_j is the number of 0's before the j-th 1 and a_0 is the number of
trailing 0's.
Now well order the n+1-tuples lexigraphically with the higher index being
given the greater dominance. IE (1,3,2) < (1,4,1)
Again the same reasoning, for each transformation h on a string s
h(s) < s
and h(s) is like s, an n+1-tuple.
This can't continue downward forever as the tuples are well ordered.
----
