435,473 Members | 3,229 Online
Need help? Post your question and get tips & solutions from a community of 435,473 IT Pros & Developers. It's quick & easy.

# Induction question, help needed.

 P: n/a 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. Jul 17 '05 #1
6 Replies

 P: n/a 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. ---- Jul 17 '05 #2

 P: n/a In article <20**************************@posting.google.com >, st*******@yahoo.com (Jack Smith) writes:Help needed on this question. Any help is appreciated. Thanks inadvance.Given a binary string (i.e. a finite sequence of 0's and 1's) wechoose any two digit substring 01 and replace it by a string of theform 100...0 using an arbitrary (but finite) number of zeros. Proveby induction that this transformation can not be performed infinitelymany times, i.e. this sequence of transformations must terminate forany input string. 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...1&pagecount=25 abstract: http://www.springerlink.com/app/home...ts,id:100499,1 conference paper (RTA 1995) on this topic: http://www.informatik.uni-trier.de/~...tml#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: gr******@logic.at www: http://www.logic.at/staff/gramlich ================================================== ====================== -- ================================================== ====================== Bernhard Gramlich Vienna University of Technology e-mail: gr******@logic.at www: http://www.logic.at/staff/gramlich ================================================== ====================== Jul 17 '05 #3

 P: n/a On Tue, 23 Sep 2003 22:18:31 -0700, Jack Smith wrote: 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. 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 Jul 17 '05 #4

 P: n/a 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. Jul 17 '05 #5

 P: n/a Jack Smith wrote: 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. 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 Jul 17 '05 #6

 P: n/a "Christopher Blunck" wrote in message news:... On Tue, 23 Sep 2003 22:18:31 -0700, Jack Smith wrote: 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. 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 Why don't you tell us how you really feel. Jul 17 '05 #7

### This discussion thread is closed

Replies have been disabled for this discussion.