February 2004 - mathfun@mailman.xmission.com

[math-fun] odometer word game
by Richard Schroeppel 03 Jun '04

03 Jun '04

zimb zinc chromatic chromatid Rich

2 1

[math-fun] 4 pile nim
by Thane Plambeck 01 Apr '04

01 Apr '04

David Gale writes: > Before I start here's something more in the math-fun spirit. I'm offering two hundred bucks ($200) for a solution of the following Nim variant. > There are 4 piles, ordinary Nim rules, the only difference being that the game ends when three of the four piles are empty. OK---I'll bite, if no one else will. Case I: (Single non-empty heap) Answer: *0 (the game is already over) everything is a P position, ie 2nd player to move wins. Case II: (Two nonempty heaps, sizes m and n). Everything is an N-position. A wiinning move to take everything in one of the heaps. For extra credit (but not for the $200), after a few minutes of noodling I got the nim heap equivalent is BitXor[m-1,n-1] +1. Case III: (Three nonempty heaps, sizes r,s,t). Assume r <= s <= t. Every move involving taking a whole heap leads to a (Case II) N position. What are the three heap P positions? 1,1,1 is a P position for example. Then 1,1,t for other t>1 is always an N position, since there's a move to 1,1,1. It looks like the P positions are in one-to-one correspondence with every pair (a,b) = (s-r, t-s) with a, b nonnegative. Ie, the P position (1,1,1) corresponds to the choice (a,b) = (0,0), and (for example), the P position (2,3,4) corresponds to the choice (1,1), (and for another example), (4,6,7) corresponds to (2,1), ET CETERA, where I don't really know what ET CETERA means. Assuming this correspondence is valid, how to recover r from a and b? This should be achievable---but not after two glasses of chianti. Is it hopeless to give a formula for the Case III nim equivalent? Case IV: (Four nonempty heaps). Hmmm.... Thane Plambeck 650 321 4884 office 650 323 4928 fax http://www.plambeck.org

5 5

Re: [math-fun] preprint: uncertainty principle in AIT
by Mike Stay 26 Feb '04

26 Feb '04

Thanks for all the comments on the paper. It was clear that the connection with Heisenberg's relation needed clarification, so that part has been rewritten. The article has been accepted for publication in Int. J. Th. Phys. -- Mike Stay staym(a)clear.net.nz http://www.cs.auckland.ac.nz/~msta039

1 0

[math-fun] preprint: uncertainty principle in AIT
by Mike Stay 24 Feb '04

24 Feb '04

Greg Chaitin defined Omega_U as the halting probability for a self-delimiting Turing machine U. (Self-delimiting means that the domain of U is a prefix-free set; that is, no program is the prefix of another.) I noticed that Chaitin's theorem about the (un)computability of bits of Omega_U can be recast as an uncertainty principle. My professor and I have written a paper; a preprint is available at http://www.cs.auckland.ac.nz/CDMTCS/researchreports/235cris.pdf I'd appreciate any comments. Thanks! -- Mike Stay staym(a)clear.net.nz http://www.cs.auckland.ac.nz/~msta039

10 13

Re: [math-fun] preprint: uncertainty principle in AIT
by Mike Stay 23 Feb '04

23 Feb '04

Eugene Salamin wrote: > > > I see no application of Godel incompleteness to > > > physics. Questions such as whether the whole of > > > physics is finitely describable are unanswerable, > > > since, unlike mathematics, physics is limited by what > > > can be measured rather than by what can be postulated. > > > > I agree. One interesting paper I read claimed to show > > that if your physical theory predicts that some > > measureable quantity is equal to an uncomputable number, > > you'll never be able to verify your theory > > algorithmically! Of course, if the Church-Turing thesis > > is false for some physical system, then perhaps we could > use that to verify it. > > To obtain an uncomputable number as a measurement result > requires measuring to infinite precision, and this is not > possible. > > Gene It's not the infinite precision that's the important part, it's that you can't know how close your approximation to the number is. Say, for instance, the theory predicts Omega. You go and measure the appropriate property to a known accuracy, and then try to compute bits of Omega to compare it with. You can only prove a finite number of bits with any given algorithm. You could start enumerating programs and running them; if the "weight" of the halting programs exceeds the measured value, then you can falsify the theory. But if they're less than the measured number, there's no way to determine how close you are to the correct value, so you can never verify the theory to an arbitrary but finite accuracy algorithmically. -- Mike Stay staym(a)clear.net.nz http://www.cs.auckland.ac.nz/~msta039

1 0

Re: [math-fun] preprint: uncertainty principle in AIT
by Mike Stay 23 Feb '04

23 Feb '04

Eugene Salamin wrote: > I don't see your connection between mathematics and > physics. Your only reference to physics is the brief > introduction to the Heisenberg uncertainty principle in > Section 3, but where does it relate to the mathematical > content of your paper? The second-to-last paragraph of chapter 6 argues that for computers whose halting probabilities are computable, you can construct a quantum state where the standard deviation in an observable corresponds to the complexity term in the uncertainty relation. -- Mike Stay staym(a)clear.net.nz http://www.cs.auckland.ac.nz/~msta039

1 0

Re: [math-fun] preprint: uncertainty principle in AIT
by Mike Stay 23 Feb '04

23 Feb '04

(Comments inline) Eugene Salamin wrote: > I failed to find in the paper any connection between > Godel's incompleteness and randomness in physics, other > than a stated conjecture that such exists. Well, the abstract does say that we're *not* looking at incompleteness implying randomness in physics. What we showed was that uncertainty--formally equivalent to Heisenberg's relation in all cases and physically equivalent in some particular cases--implies incompleteness. Perhaps we need to emphasize that more? The conjecture was made by my professor's friend (and I'm sure it has been made before); the only thing our paper contributes toward that conjecture is another hint that some kind of relationship between them seems to exist. Do you think we should strike the conjecture? It was really tacked on at the end. > I see no application of Godel incompleteness to physics. > Questions such as whether the whole of physics is finitely > describable are unanswerable, since, unlike mathematics, > physics is limited by what can be measured rather than by > what can be postulated. I agree. One interesting paper I read claimed to show that if your physical theory predicts that some measureable quantity is equal to an uncomputable number, you'll never be able to verify your theory algorithmically! Of course, if the Church-Turing thesis is false for some physical system, then perhaps we could use that to verify it. > > But here is something to contemplate. A polarizing beam > splitter is a device that splits an input light beam into > its horizontally and vertically polarized components, and > both of these beams are output. Unlike Polaroid sheet, > there is no absorption. If the input light is linearly > polarized at 45 degrees, the output beams have equal > power. Measure each output beam with a detector that can > detect individual photons. For each horizontally > polarized photon, output a zero; for each vertically > polarized photon, output a one. Now you have a random bit > stream. Because of alignment and material imperfections, > the probability of 0 and 1 cannot be made precisely 1/2. > Computer scientists expend a tremendous effort trying to > design computational pseudorandom number generators. But > through quantum mechanics, you get it for free as a gift > from nature. > > Gene > > --- Mike Stay <staym(a)clear.net.nz> wrote: > > Greg Chaitin defined Omega_U as the halting probability > > for a self-delimiting Turing machine U. > > (Self-delimiting means that the domain of U is a > > prefix-free set; that is, no program is the prefix of > > another.) I noticed that Chaitin's theorem about the > > (un)computability of bits of Omega_U can be recast as an > > uncertainty principle. My professor and I have written > > a paper; a preprint is available at > > > http://www.cs.auckland.ac.nz/CDMTCS/researchreports/235cris.pdf > > > > I'd appreciate any comments. > > > > Thanks! > > > > > > -- > > Mike Stay > > staym(a)clear.net.nz > > http://www.cs.auckland.ac.nz/~msta039 -- Mike Stay staym(a)clear.net.nz http://www.cs.auckland.ac.nz/~msta039

2 1

[math-fun] Experimental math workshop
by David H Bailey 23 Feb '04

23 Feb '04

Here's the full announcement, with the tentative program. DHB Experimental Math Workshop Oakland, CA March 29-30, 2004 The University of California, Berkeley, and the Lawrence Berkeley Laboratory are pleased to host a workshop on experimental mathematics, to be held Mar. 29-30, in Oakland, California, USA. Logistics and a preliminary program are shown below. This workshop is designed to bring together a number of leading researchers and students in the emerging field of "experimental mathematics," namely the utilization of advanced computer technology as an active tool for mathematical research. Topics to be covered include computational number theory, symbolic computing tools, high-precision arithmetic techniques, integer relation algorithms, numerical discovery of new mathematical identities, applications of experimental mathematics in physics and other disciplines, experimental mathematics and art, computational techniques for formal proof, parallel computing for experimental mathematics, and others. Organizers: David H. Bailey, Lawrence Berkeley Laboratory, Berkeley, California, USA, dhbailey(a)lbl.gov, 510-495-2773. Jonathan M. Borwein, Dalhousie University, Halifax, Nova Scotia, Canada. Borwein and Bailey are co-authors of the new books "Mathematics by Experiment: Plausible Reasoning in the 21st Century" and "Experimentation in Mathematics: Computational Paths to Discovery." If you wish to attend or participate, please contact Bailey. Logistics: The workshop will be held at the Oakland Marriott City Center Hotel, 1001 Broadway, Oakland, California, USA. The hotel's website is at: http://marriott.com/property/propertyPage.mi?marshaCode=OAKDT A block of sleeping rooms at the group rate of $105 + tax per night, single or double occupancy, has been negotiated with the Marriott Oakland City Center for this meeting. The block starts on Sunday, March 28, ending on Tuesday, March 30. To make a reservation, please call Marriott Reservations at 1-800-991-7249 between 6:00 am and 11:00 pm (PST). Request the "Experimental Math" block in order to receive the group rate. ***Reservations must be made no later than March 7, 2004 to obtain this rate.*** Hotel room rates are subject to applicable state and local taxes (currently 11%) in effect at time of check in. Cancellations must be made at least 72 hours prior to the scheduled date of arrival, or one night's room and tax will be applied to the credit card on file. The hotel is accessible from either the Oakland International Airport (most convenient) or the San Francisco International Airport. From the Oakland airport, you can take a taxi (approx $30), or the Bay Area Rapid Transit train ($3.25). From the San Francisco airport, take an airport shuttle van (fare about $40). Preliminary Program: Monday Mar. 29: 9:00am David H. Bailey, LBNL Welcome 9:15am Jonathan M. Borwein, Dalhousie University "Mathematics by Experiment: Plausible Reasoning in the 21st Century" 10:30am Break 10:45am Richard E. Crandall, Center for Advanced Computation, Reed College "Experimental Mathematics and Bioterror" 11:30am Victor H. Moll, Tulane University "Closed Form Evaluation of Definite Integrals" 12:15pm Lunch (provided) 1:15pm Helaman Ferguson, CCS "Mathematical Sculpture and PSLQ" 2:00pm Sherry Li "A Comparison of Three High-Precision Quadrature Schemes" 2:45pm Break 3:00pm Sinai Robins, Temple University "Sifting Arithmetic Progressions from Taylor Series Coefficients" 3:45pm Open 4:30pm Adjourn for the day 6:00pm Dinner (optional - not provided) Tuesday Mar. 30: 9:00am David H. Bailey, LBNL "Experimental Mathematics and the Normality of Pi" 10:15am Break 10:30am Panel/Group Discussion "What Tools Are Needed for Experimental Mathematics" 11:30am Panel/Group Discussion "What Areas Are Most Fertile for Future Experimental Breakthroughs?" 12:15pm Lunch (provided) 1:15pm Rob Scharein, Simon Fraser University "Knot Plot" 2:00pm Ruchira Datta, U.C. Davis/LBNL "The Experimental Mathematician's Toolkit" 2:45pm Break 3:00pm Andrew de Laix, Wolfram Research, Inc. "Numerical Experiments Using Mathematica" 3:45pm Thayne Plambeck Pretending in Misere Combinatorial Games 4:30pm Adjourn

1 0

[math-fun] Experimental math workshop
by David H Bailey 23 Feb '04

23 Feb '04

Experimental Math Workshop Oakland, CA March 29-30, 2004 The University of California, Berkeley, and the Lawrence Berkeley Laboratory are pleased to host a workshop on experimental mathematics, to be held Mar. 29-30, in Oakland, California, USA. Logistics and a preliminary program are available from Bailey (see below). This workshop is designed to bring together a number of leading researchers and students in the emerging field of "experimental mathematics," namely the utilization of advanced computer technology as an active tool for mathematical research. Topics to be covered include computational number theory, symbolic computing tools, high-precision arithmetic techniques, integer relation algorithms, numerical discovery of new mathematical identities, applications of experimental mathematics in physics and other disciplines, experimental mathematics and art, computational techniques for formal proof, parallel computing for experimental mathematics, and others. Organizers: David H. Bailey, Lawrence Berkeley Laboratory, Berkeley, California, USA, dhbailey(a)lbl.gov, 510-495-2773. Jonathan M. Borwein, Dalhousie University, Halifax, Nova Scotia, Canada. Borwein and Bailey are co-authors of the new books "Mathematics by Experiment: Plausible Reasoning in the 21st Century" and "Experimentation in Mathematics: Computational Paths to Discovery." If you wish to attend or participate, please contact Bailey.

1 0

[math-fun] Permutations
by Jon Perry 20 Feb '04

20 Feb '04

Sum of zero moments of partitions gives A055303 { for (i=1,8, c=0; for (j=1,i!, x=numtoperm(i,j); c+=sum(k=1,i,(k-1)*x[k])); print1(","c)) } Why does sum of second moments = sum of first moments of permutations of 2,3,..n? { for (i=1,8, c=0; for (j=1,i!, x=numtoperm(i,j); c+=sum(k=1,i,(k+1)*x[k])); print1(","c)) } { for (i=1,8, c=0; for (j=1,i!, x=numtoperm(i,j); c+=sum(k=1,i,k*(x[k]+1))); print1(","c)) } Jon Perry perry(a)globalnet.co.uk http://www.users.globalnet.co.uk/~perry/maths/ http://www.users.globalnet.co.uk/~perry/DIVMenu/ BrainBench MVP for HTML and JavaScript http://www.brainbench.com

1 0