June 2012 - mathfun@mailman.xmission.com

[math-fun] "Life: probability of halting or settling
by Warren Smith 24 Jun '12

24 Jun '12

>From: Mike Stay <metaweta(a)gmail.com> I'd like to compute the first bits of the "halting probability" of Conway's life; since CAs don't halt, I'd like to compute the probability that it evolves to a state that's easily detectable by Golly, like all empty or a still life or cyclic. (Also, I know the number is uncomputable, but that doesn't preclude a finite computable prefix.) Since any translation or reflection of a pattern has the same outcome as the original, I'd like to choose a measure on the set of cells such that computing the measure of all the translations and reflections of a pattern is easy. Any suggestions? --but isn't this probability zero? I mean, if you were running life on some finite-size grid-torus, then it would be nonzero but... 1. on an infinite grid, there will with prob=1 be some unboundedly large region of the grid containing the worst possible pattern it could contain, which will last for time>=T before you regard it as settled, where T can be made unboundedly large. 2. Returning to the finite-size grid-torus, since there are only a finite set of states, the thing is certain to be periodic, so then the probability is 1.

2 1

[math-fun] Fast scheme to recognize polyominos?
by Warren Smith 24 Jun '12

24 Jun '12

A "polyomino" is an interior-connected set of grid squares in the plane, and for my purposes we may demand also "simply connected" (i.e. no holes). Two polyominos are equivalent if congruent. The number of N-square polyominos is here: http://oeis.org/A000104 Your (admittedly somewhat vaguely defined) mission is to figure out a fast algorithm to recognize which polyomino I just gave you. I might rotate it any of 4 ways, mirror it or not, and translate it by any integers (x,y) before giving it to you. --- I have a solution in mind incidentally, which for an N-omino will run in O(N) operations and output a unique bitstring polyomino name which is at most 3*N*lg3 bits long (lgX=log base 2 of X). This is optimal except for the constant hidden in the "O" and the constant 3*lg3=4.754887... which perhaps could somehow be improved to about 2.0224 which then would be optimal assuming certain standard conjectures about polyomino-count asymptotics. The scheme I have in mind will not do that and is stuck at 4.75..., but by "hashing" my scheme's bitstring down to a smaller bitlength we could reduce this to 4.0448 which is a factor of two times optimal and a "random hash function" (if one exists) would do this collisionlessly with good probability. But it might be possible to do better than my scheme.

1 0

Re: [math-fun] that Turing sequence
by Adam P. Goucher 24 Jun '12

24 Jun '12

We can also obtain the sequence from removing the first two terms of the rabbit sequence. 1 10 10|1 10|110 10|110101 10|11010110110 ... (This is equivalent to the first definition, as the string '10' acts as a factory for producing an extra '1' at each stage.) So, we have M = 4(R - 1/2) = 4R - 2, where M is the Munafo constant 0.839213... and R is the Rabbit constant: http://mathworld.wolfram.com/RabbitConstant.html Sincerely, Adam P. Goucher

2 1

[math-fun] The final Google Turing puzzle: what is 11010110110101101011011...
by Robert Munafo 24 Jun '12

24 Jun '12

I've been trying to "solve" the 3-line, 39-symbol Turing machine that you get at the "end" of the Google doodle puzzles. See [1] below for background. After solving the 6 puzzles, click on the little color "dog" icon in the upper right to see the 39-step program I'm investigating. After working through the normal puzzles, the Google doodle starts replaying the solutions of the Turing puzzles, and the "=" box in the upper right changes to something that looks like a little dog, or maybe the Trojan Rabbit from Monty Python and the Holy Grail [4], on a colored background. If you click on the doggie/bunny, the puzzle playback is replaced with a much more complex Turing program. The pattern on the tape grows to the right, here is how the program starts (with "." for an erased cell): at step 1: 1 at step 2: . at step 5: .1 at step 8: .10 at step 11: 110 at step 13: 1.0 at step 17: 1.01 at step 20: 1.010 at step 24: 11010 at step 26: 11.10 at step 31: 11.101 at step 35: 110101 at step 37: 110.01 at step 42: 110.011 at step 45: 110.0110 at step 50: 11010110 at step 52: 1101.110 at step 58: 1101.1101 at step 63: 110101101 at step 65: 11010.101 at step 71: 11010.1011 at step 74: 11010.10110 at step 80: 11010110110 etc... I'm counting head movements and writing or erasing a symbol as "steps". When a 0 or 1 symbol in the middle gets erased, it seems to be always replace it with the same symbol again. Thus it makes sense to ignore these temporary erasures and just look at the whole binary string. It grows only to the right, and it's an irregular pattern. As the pattern grows, the successive values are 110, 11010, 110101, 11010110, 110101101, 11010110110, ... or in decimal: 6, 26, 53, 214, 429, 1718, 6874, 13749, ... which is not presently in OEIS (even just the first 3 terms give no match). By step 49720, it has written: 1101011011010110101101101011011010110101101101011010110110101101101011010110110101101101011010110110101101011011010110110101101011011010110101101101011011010110101101101011011010110101101101011010110110101101101011010110110101101101011010110110101101011011010110110101101011011010110101101101011011010110101101101011011010110101101101011010110110101101101011010110110101101011011010110110101101011011010110110101101011011010110101101101011011010110... It looks like any initial substring, no matter how long, occurs arbitrarily many times in the rest of the digits, but the occurrences are irregularly spaced. Taken as a binary fraction (0.1101011011010...) it is equivalent to 0.8392137714451652585671495977783023880500088230714420678280105786051... in decimal. It is irrational; the sequence of approximating fractions is: 0 / 1 1 / 1 5 / 6 21 / 25 26 / 31 47 / 56 167 / 199 214 / 255 1665 / 1984 5209 / 6207 6874 / 8191 438271 / 522240 1321687 / 1574911 1759958 / 2097151 3603955713 / 4294443008 ... It doesn't fit any simple algebraic formula; my RIES program finds nothing [2]. I got nothing with ISC+ either [3] (but I might be using it wrong, I think you need to try different numbers of digits: if 0.83921377144516 finds nothing, try 0.8392137714451, and so on.) Let me know if you have ideas for other, fancier tests I can apply to this sequence, the fraction, etc. - Robert Munafo [1] Background: If you go to Google today (Sat June 23rd) the Google Doodle is a Turing machine. Initially it's running a binary counter program, until you click the green "Play" button to pay the Turing game. It gives you 6 "easy" turing programming puzzles, which you solve by pushing the yellow buttons to set certain program steps, then press Play to see if you got it. If you solve the puzzles and start over (or reload, I'm not sure) it gives you 6 "hard" puzzles. [2] See http://mrob.com/pub/ries/ries.php?target=0.839213771445165 I also did a much longer RIES run on my own machine. [3] http://isc.carma.newcastle.edu.au/index [4] http://www.youtube.com/watch?v=T2PdyxMtiYM Okay it's not that close a resemblance, but I couldn't resist. -- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com

4 6

[math-fun] Propp's coin-tossing
by Guy Haworth 24 Jun '12

24 Jun '12

Estimating X' seem straightforward. Estimating p is an 'inverse problem' but {n, X} ==> Pr(p = p') ... and for each p', we expect p'n' heads from n' tosses of the coin. I suspect for large n, this is not far from X.n'/n. Guy

2 1

[math-fun] Vector puzzle
by Warren Smith 23 Jun '12

23 Jun '12

Yes, my "V' and -V removal" ploy can fail if the set of altered vectors is half the cardinality (or more) of the full set. If the old set is -+ -- ++ +- then alter to -+ -- 0+ +0 whereupon the last three sum to 00 but no other subset works (right?). That example indicates that the puzzle cannot be solved by a simple pairing argument, something fancier is needed. If -++ -+- --+ --- +++ ++- +-+ +-- is altered to -++ -+- --+ --- 0++ 0+- +0+ +-0 then what is the subset summing to 000?

3 2

[math-fun] Asimov vector puzzle
by Warren Smith 23 Jun '12

23 Jun '12

Dan Asimov <dasimov(a)earthlink.net> [Jun 23. 2012 07:47]: > I recently heard this cute puzzle: > For some integer n > 0 you have all 2^n vectors of dimension n whose entries are +1 or -1. > Of course the sum of all 2^n of these vectors is the 0 vector. > > Then your three-year-old child changes some of the entries of some of these vectors to 0. > Show that there is still a nonempty subset of the new set of 2^n vectors that sums to the 0 vector. --Mentally pair each +-1 vector with its negation. If the child alters certain vectors V (converting to V'), then remove both V' and -V from the full set (admittedly you may not know what V is, but this proof is merely existential -- a way exists)... and then remaining vectors still will have a pairing as before hence still will sum to 0.

3 3

Re: [math-fun] Friend interested in math-fun
by Dan Asimov 22 Jun '12

22 Jun '12

I don't agree at all. First of all, Rich has already put a brief mention of the fact that we discuss some OT topics. The description reads: << We are a group of people who enjoy math. Our topics range from digit puzzles to current research. We occasionally stray to word games, general science, and reviews of math-related movies. We have a computational bent. Our current traffic level is a few messages per day. >> Of course no sample perfectly represents the experience of being on math-fun, but even a modest sample will probably hugely clarify the kind of place we are -- just for the purpose of prospective members' deciding if they even want to bother signing up and getting the real McCoy. That's my story and I'm stickin' to it. --Dan << I believe that any attempt at sampling would produce a result that is sort of good enough for some people and completely off-base for others. Let's pick some of the questions (and/or puzzles and/or problems) that have been answered, as you suggest. Then what about all the stuff that's not in the form of questions/puzzles/problems? Will people join and get annoyed about the off-topic replies? What counts as off-topic anyway? I might think it's irrelevant, and another member will (rightly) say that the "off-topic" stuff is even more valuable than the original (in his mind). Maybe we could curate the sample to try to keep it up to date, but that makes work (and I think you're trying to avoid making work for anyone and everyone, not just Rich and the new users). A lot of the people viewing a sampling of math-fun will be pretty smart people, I dare say smart enough to figure out what I just said about sampling bias. So they'll have to join the list anyway, see if they like it and un-join later. >> ________________________________________________________________________________________ It goes without saying that .

3 2

Re: [math-fun] Friend interested in math-fun
by Dan Asimov 22 Jun '12

22 Jun '12

Yes, that is the default option. But joining requires your "application" (= e-mail address, essentially) being vetted by Rich. I thought that having a small sample of the archives would save some time and energy. --Dan On 2012-06-22, at 2:02 PM, Robert Munafo wrote: > Why can't this friend just join, and then quit (or unsubscribe) if > they don't like it?

2 1

Re: [math-fun] Gun problem
by Dan Asimov 22 Jun '12

22 Jun '12

I don't think William Feller is on this list, but according to him, the probability p(n) of first hitting -1 at the nth step is p(n) = bin(n, (n-1)/2) / (n * 2^n) where the binomial coefficient should be taken as 0 for n even -- so p(2k) = 0, which is obvious anyway. The generating function for these probabilities is shown to be G(s) = (1 - sqrt(1-s^2)) / s from which G'(1) = oo. Which shows that as Michael said, the expected time to reach -1 is oo. (I found this to be rather surprising.) --Dan Michael wrote: << Surely many people on this list know more than I do about the distribution of times at which the random walker first hits -1. >> ________________________________________________________________________________________ It goes without saying that .

4 4