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.

----