Article 15953 of rec.puzzles: Path: ms!darwin.sura.net!mips!spool.mu.edu!agate!dog.ee.lbl.gov!hellgate.utah.edu!asylum.utah.edu!tolman From: tolman%asylum.utah.edu@cs.utah.edu (Kenneth Tolman) Newsgroups: rec.puzzles Subject: Godel, Escher, Bach Message-ID: <1992May24.221644.20413@hellgate.utah.edu> Date: 25 May 92 04:16:43 GMT Article-I.D.: hellgate.1992May24.221644.20413 Organization: University of Utah CS Dept Lines: 41 In Hofstadter's excellent book, he proposes the idea of any TNT being equivalent to a puzzle in which you attempt to derive a certain string given the rules of production and an axiom(s). I am interested in playing with these, and hopefully some other people will develop new rules with other symbols to play with :) You are going to attempt to show a way to generate a certain string, or demonstrate that it can not be done. Here are the rules for this: 1) If you have 01 you may replace it with 010. 2) If you have a string you may "invert" every character 0->1 1->0. 3) If you have 11 you may eliminate it. 4) You may take any whole string, reverse it and tack it on its end. THE AXIOM: 01 STRINGS TO TRY TO PRODUCE (or prove impossible to make) 1. 1 2. 0011 3. 0101 4. 1001100110011 5. 011000 You can not introduce any new axioms (obviously), here are some examples: 01 -> 0110 (rule 4) 0110 -> 00 (rule 3) 00 -> 11 (rule 2) or maybe 0110 -> 01100 (rule 1) Note that ANY production rule set will have to have BOTH lengthening and shortening rules to be interesting (otherwise you can rapidly figure out what is possible and what is not) What other types of generalizations can be made about production rules? Anyone have any ideas? Article 15956 of rec.puzzles: Path: ms!darwin.sura.net!mips!zaphod.mps.ohio-state.edu!cs.utexas.edu!swrinde!gatech!bloom-beacon!eru.mt.luth.se!lunic!sunic2!ugle.unit.no!nuug!nntp.nta.no!hal.nta.no!stein From: stein@hal.nta.no (Stein Kulseth FBA) Newsgroups: rec.puzzles Subject: Re: Godel, Escher, Bach [SPOILERS] Message-ID: <1992May25.124753.20315@nntp.nta.no> Date: 25 May 92 12:47:53 GMT References: <1992May24.221644.20413@hellgate.utah.edu> Sender: news@nntp.nta.no Organization: Norwegian Telecom Research Lines: 74 Nntp-Posting-Host: elvis.nta.no In article <1992May24.221644.20413@hellgate.utah.edu>, tolman%asylum.utah.edu@cs.utah.edu (Kenneth Tolman) writes: |> |> 1) If you have 01 you may replace it with 010. |> 2) If you have a string you may "invert" every character 0->1 1->0. |> 3) If you have 11 you may eliminate it. |> 4) You may take any whole string, reverse it and tack it on its end. |> |> THE AXIOM: |> 01 |> |> STRINGS TO TRY TO PRODUCE (or prove impossible to make) |> |> 1. 1 |> 2. 0011 |> 3. 0101 |> 4. 1001100110011 |> 5. 011000 [SPOILERS FOLLOW] 01 -> 10 (2) -> 1001 (4) -> 10011001 (4) -> 100101001 (1) -> 011010110 (2) -> 0010110 (3) -> 00100 (3) -> 11011 (2) -> 011 (3) -> 0 (3) -> 1 (2) 01 -> 010 (1) -> 010010 (4) -> 101101 (2) -> 1011010 (1) -> 10110100 (1) -> 100100 (3) -> 011011 (2) -> 0011 (3) 01 -> 010 (1) -> 101 (2) -> 1010 (1) -> 0101 (2) 01 -> 0110 (4) -> 01100110 (4) -> 0110011001100110 (4) -> 01100110011000 (3) -> 011001100101000 (1) -> 0110011001010000 (1) -> 01100110010010000 (1) -> 10011001101101111 (2) -> 100110011001111 (3) -> 1001100110011 (3) 01 -> 0110 (4) -> 01100110 (4) -> 011000 (3) These are trial-and-error quick solutions, however it is easy to show that there is a general procedure that can produce any string. 01 -> 010 (1) Now let n be the number of trailing 0's in the target string (possibly zero), apply rule 1 n times: 010 -> 010[n*0] 010[n*0] -> 101[n*1] Then let m be the number of 1's precedeing the trailing zeros. As we now operate on the inverted string we insert these also as zeros by rule 1: 101[n*1]-> 101[m*0][n*1] 101[m*0][n*1] -> 010[m*1][n*0] We then insert 0's and 1's by this procedure until we have made 010010[target string] and then: 010010[target string] -> 101101[inverted target string] (2) -> 1001[inverted target string] (3) -> 0110[target string] (2) -> 00[target string] (3) -> 11[inverted target string] (2) -> [inverted target string] (3) -> [target string] (2) -- Stein Kulseth Norwegian Telecom Research, Box 83, N-2007 KJELLER, NORWAY internet: stein@hal.nta.no X400: stein.kulseth@forskning.teledir.no Phone: + 47 6 80 98 05 Fax: + 47 6 81 00 76 Article 15952 of rec.puzzles: Path: ms!darwin.sura.net!mips!swrinde!cs.utexas.edu!uunet!comp.vuw.ac.nz!waikato.ac.nz!canterbury.ac.nz!math!wft From: wft@math.canterbury.ac.nz (Bill Taylor) Newsgroups: rec.puzzles Subject: Tiling with 2x2 & 3x3 squares. Extensions. Message-ID: <1992May25.144449.5181@csc.canterbury.ac.nz> Date: 25 May 92 02:44:48 GMT Organization: Department of Mathematics, University of Canterbury Lines: 85 Nntp-Posting-Host: math.canterbury.ac.nz The story so far.... Kanad Chakraborty proposed the problem:- can one tile a 25x25 square with a mixture of 2x2 and 3x3 squares? He supplied a proof that one couldn't, which Dan Hoey clarified and extended to tiling rectangles of suitable size. John Rickard produced VERY neat coloring proof (which can also extend to the rectangular case). Dan Hoey asked the extended question: what about a general combination of two sorts of squares, (axa) and (bxb), to tile rectangles with. Here is the answer (modulo mistakes). Both the Chakraborty-Hoey and the Rickard proofs extend to this general case. THEOREM ~~~~~~~ A rectangle can be tiled with (axa) and (bxb) squares, iff (i) gcd(a,b)=1 , and any of the following hold: either: both sides of the rectangle are multiples of a; or: both sides of the rectangle are multiples of b; or: one side is a multiple of (ab), and the other is any length EXCEPT one of a finite number of "bad" lengths: those numbers which are NOT positive integer combinations of a & b. { By Sylvester's theorem there are (a-1)(b-1)/2 of these, the largest being (a-1)(b-1)-1. } (ii) gcd(a,b) = d . Then merely apply (i) to the problem with a,b replaced by a/d, b/d and the rectangle lengths also divided by d. i.e. all cells must appear in (dxd) subsquares. ------ PROOF It is clear that (ii) follows from (i), and that simple constructions give the "if" part of (i). For the "only if" part, we prove that... (S) If one side of the rectangle is not divisible by a, and the other is not divisible by b, then the tiling is impossible. The results in (i) follow immediately from (S). To prove (S): ( Chakraborty-Hoey style ). ~~~~~~~~~~~~~~~~ Let the width of the rectangle be a NON-(a-multiple). Then the number of bxb squares starting (i.e. top edge) at row 1 must be a NON-a-multiple. Thus the number of bxb starting at row 2 must BE an a-multiple. Similarly for the number starting at rows 3,4,...,b . Then the number starting at row (b+1) must be a NON-a-multiple again. Similarly the number starting at rows (2b+1), (3b+1), (4b+1),... must all be non-a-multiples. So if the number of rows is NOT a multiple of b, (call it bx+r), then row (bx+1) must have a NON-a-multiple of bxb squares starting there, i.e. at least one, and there is no room left to squeeze it in. [QED] ---- A Rickard-style proof of (S) is ..BBB....BBWWW...WBBB....BBWWW...W(..etc) ~~~~~~~ also possible, by ..BBB....BBWWW...WBBB....BBWWW...W coloring the rectangle in ..BBB....BBWWW...WBBB....BBWWW...W vertical strips as shown here: <- a ->< b-a ><- a ->< b-a > Every square tile covers an a-multiple of black squares. But if the width is a NON-b-multiple, and the number of rows is a NON-a-multiple, then there are a NON-a-multiple of black squares in total. [QED] (Note: the coloring must have 1 column of blacks on the right, and any ==== spare columns of whites on the left.) ----------------------------------- ----------------------------------- For a further extension, what rectangles is it possible to tile with (axa), (bxb) & (cxc) squares together ? For example, with 2x2, 3x3 and 5x5 tiles, and looking at tiling large squares only; it seems to be possible to tile all (nxn) squares EXCEPT for n=1,7,13,19 only. These numbers are some of the early numbers not divisible by 2,3,5, but with a few gaps. I leave it to others to work out the full details of this extension. =================== Bill Taylor. wft@math.canterbury.ac.nz Article 15978 of rec.puzzles: Path: ms!darwin.sura.net!mips!spool.mu.edu!uunet!pipex!ibmpcug!ibmpcug!mantis!tony From: tony@mantis.co.uk (Tony Lezard) Newsgroups: rec.puzzles Subject: Re: Godel, Escher, Bach Message-ID: Date: 26 May 92 14:10:00 GMT Article-I.D.: mantis.D8wDLB2w164w References: <1992May24.221644.20413@hellgate.utah.edu> Organization: Mantis Consultants, Cambridge. UK. Lines: 32 tolman%asylum.utah.edu@cs.utah.edu (Kenneth Tolman) writes: > In Hofstadter's excellent book, he proposes the idea of any TNT being > equivalent to a puzzle in which you attempt to derive a certain string > given the rules of production and an axiom(s). I am interested in playing > with these, and hopefully some other people will develop new rules with > other symbols to play with :) A fun book. While it's been ages since I read it, I do remember one problem that always bothered me and I spent ages, to no avail, trying to solve it. For what follows, it might be worthwhile to bone up on TNT first... Remember when he was introducing TNT he gave some examples of predicates (did he call them that?) that one might want to prove, eg. "x is odd", or "x is prime" and he gave a list of about five predicates for the reader to express in TNT for fun. The last one on the list was "x is a power of 2" which Doug warned might be a bit tricky (there is no exponentiation operator in TNT) but was nothing compared to "x is a power of 10". Although I forget the precise syntax of TNT, I remember cracking "x is a power of 2" by expressing it as, roughly, "for all y, y divides x and y is prime implies y is 2" (got it?), but this approach can't work for being a power of 10 (the obvious extension on the above (add "or 5" at the end) allows eg. x=400). Did anyone out there manage to solve this one? +++ Tony Lezard: tony@mantis.co.uk or failing that, arl10@phx.cam.ac.uk +++ ** Seeking accommodation (just nights) in/near Phoenix, Ariz. for the ** ** week starting September 6th. Luxury not a requirement and will pay! ** ** Please email me if you know of someone who might be able to help. ** Article 15981 of rec.puzzles: Path: ms!darwin.sura.net!jvnc.net!netnews.upenn.edu!sagi.wistar.upenn.edu From: weemba@sagi.wistar.upenn.edu (Matthew P Wiener) Newsgroups: rec.puzzles Subject: Re: Godel, Escher, Bach Message-ID: <78933@netnews.upenn.edu> Date: 26 May 92 17:43:42 GMT References: <1992May24.221644.20413@hellgate.utah.edu> Sender: news@netnews.upenn.edu Reply-To: weemba@sagi.wistar.upenn.edu (Matthew P Wiener) Organization: The Wistar Institute of Anatomy and Biology Lines: 41 Nntp-Posting-Host: sagi.wistar.upenn.edu In-reply-to: tony@mantis.co.uk (Tony Lezard) In article , tony@mantis (Tony Lezard) writes: >Although I forget the precise syntax of TNT, I remember cracking "x is >a power of 2" by expressing it as, roughly, "for all y, y divides x and >y is prime implies y is 2" (got it?), but this approach can't work for >being a power of 10 (the obvious extension on the above (add "or 5" at >the end) allows eg. x=400). Did anyone out there manage to solve this one? (I didn't "solve" it, since I learned the answer long before GEB existed.) As far as I know, nothing short of coding sequences works for powers of 10. This means that you have to express the notion of both a sequence s= and how to extract its members s->s_i in TNT. Given this, coding up "x is a power of ten" becomes "there is a sequence s and a length n such that s0=1 and for each i Date: 27 May 92 03:45:30 GMT Article-I.D.: husc3.1992May26.234532.12641 References: <1992May24.221644.20413@hellgate.utah.edu> <78933@netnews.upenn.edu> Organization: Harvard Math Department Lines: 42 Nntp-Posting-Host: ramanujan.harvard.edu In article <78933@netnews.upenn.edu> weemba@sagi.wistar.upenn.edu (Matthew P Wiener) writes: :In article , tony@mantis (Tony Lezard) writes: :>Although I forget the precise syntax of TNT, I remember cracking "x is :>a power of 2" by expressing it as, roughly, "for all y, y divides x and :>y is prime implies y is 2" (got it?), Yes, but simpler still is "for all y[>0], 2*y+1 does not divide x". :> but this approach can't work for :>being a power of 10 (the obvious extension on the above (add "or 5" at :>the end) allows eg. x=400). Did anyone out there manage to solve this one? : :(I didn't "solve" it, since I learned the answer long before GEB existed.) : :As far as I know, nothing short of coding sequences works for powers of 10. :[...] What I came up with when I read GEB was essentially POWER_OF_10(x) := "for all y such that R(y), Q(y,10) implies Q(y,x)", where R(D,u) := "there exist relatively prime m,n such that u=m^2-D*n^2", and R(y) is a mild restriction needed to make sure that if m and n are coprime then so are the coefficients of (m+n*sqrt(D))^k, for instance R(y) := "y is congruent to 3 mod 4 and not divisible by 5". This is more in line with Hofstadter's hint that one needs to use quite a bit of number theory. It should also work for arbitrary values of 10. :-) [Actually I don't think I ever worked out a complete proof that, for appropriate R(y), POWER_OF_10 does characterize the powers of 10; but I believe it should be a straightforward, albeit tedious, application of standard ideas and methods.] :OK, work with this to go one step further: how do you say "x is 10^n"? I don't see how to do this using my above trick. One can certainly adapt Matiyasevich's methods, though. ObPuzzle: give a rigorous definition of what your statement that "nothing short of coding sequences works" means. ;-) --Noam D. Elkies (elkies@zariski.harvard.edu) Department of Mathematics, Harvard University Article 15990 of rec.puzzles: Xref: ms rec.puzzles:15990 sci.math:27442 Path: ms!darwin.sura.net!mips!sdd.hp.com!cs.utexas.edu!rutgers!netnews.upenn.edu!sagi.wistar.upenn.edu From: weemba@sagi.wistar.upenn.edu (Matthew P Wiener) Newsgroups: rec.puzzles,sci.math Subject: Re: power-free characterization of {10^n} [Re: Godel, Escher, Bach] Message-ID: <79004@netnews.upenn.edu> Date: 27 May 92 14:48:35 GMT References: <1992May24.221644.20413@hellgate.utah.edu> <78933@netnews.upenn.edu> <1992May26.234532.12641@husc3.harvard.edu> Sender: news@netnews.upenn.edu Reply-To: weemba@sagi.wistar.upenn.edu (Matthew P Wiener) Followup-To: rec.puzzles Organization: The Wistar Institute of Anatomy and Biology Lines: 35 Nntp-Posting-Host: sagi.wistar.upenn.edu In-reply-to: elkies@ramanujan.harvard.edu (Noam Elkies) In article <1992May26.234532.12641@husc3.harvard.edu>, elkies@ramanujan (Noam Elkies) writes: >:As far as I know, nothing short of coding sequences works for powers of 10. >What I came up with when I read GEB was essentially >POWER_OF_10(x) := "for all y such that R(y), Q(y,10) implies Q(y,x)", >where R(D,u) := "there exist relatively prime m,n such that u=m^2-D*n^2", Misprint: R(D,u) should be Q(D,u). >and R(y) is a mild restriction needed to make sure that if m and n >are coprime then so are the coefficients of (m+n*sqrt(D))^k, for instance >R(y) := "y is congruent to 3 mod 4 and not divisible by 5". This is >more in line with Hofstadter's hint that one needs to use quite a bit >of number theory. It should also work for arbitrary values of 10. :-) I expect that Hofstadter himself was thinking of the Goedel beta function, which relies on the Chinese remainder theorem. >:OK, work with this to go one step further: how do you say "x is 10^n"? >I don't see how to do this using my above trick. One can certainly >adapt Matiyasevich's methods, though. Considering that Matiyasevich used Pellian methods to encode powers of the golden ratio, this isn't surprising. >ObPuzzle: give a rigorous definition of what your statement that >"nothing short of coding sequences works" means. ;-) Obviously I was wrong. The rigorous version would be something akin to the Robinson-Davis-Putnam all-but-proof of M's theorem, where they had reduced the problem to finding a single Diophantine "roughly exponential" relation. -- -Matthew P Wiener (weemba@sagi.wistar.upenn.edu) Article 15992 of rec.puzzles: Xref: ms rec.puzzles:15992 sci.math:27452 Path: ms!darwin.sura.net!mips!think.com!hsdndev!husc-news.harvard.edu!ramanujan!elkies From: elkies@ramanujan.harvard.edu (Noam Elkies) Newsgroups: rec.puzzles,sci.math Subject: Re: power-free characterization of {10^n} Message-ID: <1992May27.133724.12654@husc3.harvard.edu> Date: 27 May 92 17:37:23 GMT References: <78933@netnews.upenn.edu> <1992May26.234532.12641@husc3.harvard.edu> <79004@netnews.upenn.edu> Organization: Harvard Math Department Lines: 23 Nntp-Posting-Host: ramanujan.harvard.edu In article <79004@netnews.upenn.edu> weemba@sagi.wistar.upenn.edu (Matthew P Wiener) writes: :In article <1992May26.234532.12641@husc3.harvard.edu>, :elkies@ramanujan (Noam Elkies) writes: :>POWER_OF_10(x) := "for all y such that R(y), Q(y,10) implies Q(y,x)", :>where R(D,u) := "there exist relatively prime m,n such that u=m^2-D*n^2", : :Misprint: R(D,u) should be Q(D,u). Right --- sorry about that. :[...] :>ObPuzzle: give a rigorous definition of what your statement that :>"nothing short of coding sequences works" means. ;-) : :Obviously I was wrong. [...] I didn't mean to needle you about that, but to suggest that it may be hard if not impossible to even precisely *define* what it means to say that a TNT formula does or does not rely on coding squences. --Noam D. Elkies (elkies@zariski.harvard.edu) Department of Mathematics, Harvard Univ.