Induction question, help needed.

[Jack Smith]

Help needed on this question. Any help is appreciated. Thanks in
advance.

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.

[William Elliot]

Re: Induction question, help needed.

On Tue, 23 Sep 2003, Jack Smith wrote:
[color=blue]
> 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.
>[/color]
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.

----

[Bernhard Gramlich]

Re: Induction question, help needed.


In article <20b84b19.03092 32118.403b6bd2@ posting.google. com>,
stegen123@yahoo .com (Jack Smith) writes:[color=blue]
>Help needed on this question. Any help is appreciated. Thanks in
>advance.
>
>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.[/color]

This is a well-known (solved) type of termination problem in string
rewriting, a subfield of term rewriting. Here are some related links:

term rewriting homepage:

http://rewriting.loria.fr/

journal paper (AAECC 2000) by Zantema/Geser on this topic:
pdf:

http://www.springerlink.com/app/home/content.asp?wasp=f83ebu4j807jtj4e67vl&referrer=contribution&format=2&page=1&pagecount=25

abstract:

http://www.springerlink.com/app/home/contribution.asp?wasp=1lbfddxhqncvtk6lwvtp&referrer=parent&backto=issue,1,5;journal,19,44;linkingpublicationresults,id:100499,1

conference paper (RTA 1995) on this topic:

http://www.informatik.uni-trier.de/~ley/db/conf/rta/rta95.html#ZantemaG95

technical report version (1994) from Zantema's homepage:
ftp://ftp.cs.ruu.nl/pub/RUU/CS/techr.../1994-44.ps.gz
Hans Zantema's homepage:

http://www.win.tue.nl/~hzantema/

Alfons Geser's homepage:

http://research.nianet.org/~geser/

Hope this helps,
Bernhard Gramlich.

=============== =============== =============== =============== ============
Bernhard Gramlich Vienna University of Technology
e-mail: gramlich@logic. at www: http://www.logic.at/staff/gramlich
=============== =============== =============== =============== ============
--
=============== =============== =============== =============== ============
Bernhard Gramlich Vienna University of Technology
e-mail: gramlich@logic. at www: http://www.logic.at/staff/gramlich
=============== =============== =============== =============== ============

[Christopher Blunck]

Re: Induction question, help needed.

On Tue, 23 Sep 2003 22:18:31 -0700, Jack Smith wrote:
[color=blue]
> Help needed on this question. Any help is appreciated. Thanks in
> advance.
>
> 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.[/color]


Hey donkey-

Why'd don't you do one of two things:
- pick up a CS book and expend brain power to determine how to solve your
CS assignment
- reboot your computer, launch MS Windows, and switch to a major other than
computer science.


You brain dead idiots that mistakenly believe you can find solutions to your CS
assignments on usenet are the reason why our profession is filled with
dimwitted neandethrals.

Here's a quarter - go to your career center and switch majors to something
that will allow you to play XBox, PS2, or whatever the hell other gaming
system that you mistaked for "computer science".


People like you make me sick,
-c

[Jack Smith]

Re: Induction question, help needed.

Now I have been working on the question...and I decided to do
induction on the length of the binary string.

So for the base case x=0 or x=1...which obviously terminates.

then I assumed for k>=0 it terminates for all |x|<=k

Now I am trying to prove the Induction Step...but I am having trouble.


ANy hints on how I can prove this?? Or maybe I am performing induction
on the wrong property? Any help is appreciated. Thanks.

[Bart Demoen]

Re: Induction question, help needed.

Jack Smith wrote:
[color=blue]
> Now I have been working on the question...and I decided to do
> induction on the length of the binary string.
>
> So for the base case x=0 or x=1...which obviously terminates.
>
> then I assumed for k>=0 it terminates for all |x|<=k
>
> Now I am trying to prove the Induction Step...but I am having trouble.
>
> ANy hints on how I can prove this?? Or maybe I am performing induction
> on the wrong property? Any help is appreciated. Thanks.[/color]

Try induction on the number of 1s in the string and prove also
that after a finite number of replacements, a 1 will show up at the
left (use the induction hypothesis for that)
if you chop off that leftmost 1, you have a string with one 1 less ...

Cheers

Bart Demoen

[Steve High]

Re: Induction question, help needed.

"Christophe r Blunck" <blunck@gst.com > wrote in message news:<pan.2003. 09.25.03.05.01. 631705@gst.com> ...[color=blue]
> On Tue, 23 Sep 2003 22:18:31 -0700, Jack Smith wrote:
>[color=green]
> > Help needed on this question. Any help is appreciated. Thanks in
> > advance.
> >
> > 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.[/color]
>
>
> Hey donkey-
>
> Why'd don't you do one of two things:
> - pick up a CS book and expend brain power to determine how to solve your
> CS assignment
> - reboot your computer, launch MS Windows, and switch to a major other than
> computer science.
>
>
> You brain dead idiots that mistakenly believe you can find solutions to your CS
> assignments on usenet are the reason why our profession is filled with
> dimwitted neandethrals.
>
> Here's a quarter - go to your career center and switch majors to something
> that will allow you to play XBox, PS2, or whatever the hell other gaming
> system that you mistaked for "computer science".
>
>
> People like you make me sick,
> -c[/color]


Why don't you tell us how you really feel.