March 2008 - mathfun@mailman.xmission.com

[math-fun] Collatz chaos
by Marc LeBrun 18 Mar '08

18 Mar '08

Years ago I idly iterated smooth functions that generalized Collatz, such as x/2 cos^2 pi x/2 + 3x+1 sin^2 pi x/2 It's just now struck me (doh!) that such functions have a 3-cycle, hence cycles of all periods. Funny how some of them are integral.

1 0

Re: [math-fun] A very peculiar paper
by Steve Witham 17 Mar '08

17 Mar '08

>From: Marc LeBrun <mlb(a)well.com> > >First define an arbitrary well-ordering on the set of all functions F >(thus I guess requiring AC). Let's call this "complexity". > >Then, for each t, set w(t) = f[t](t), where f[t] is the "simplest" f >such that f[t](tau) = v(tau) for all tau strictly < t. > >That is, w(t) has the value at t of the "simplest" f which correctly >predicts the past values of v(t) strictly prior to t. This sounds something like Ray Solomonoff's algorithmic complexity and predictors based on it. He looks at universal Turing machine programs, and their lengths in bits. He builds a machine that gives odds for every possible result by taking all the machines that predicted all the previous values, and weighting each by 2^(-length). Something like sum for all f that predicted {y[1] ... y[t-1] } { if f(t) = y then 2^-length(f) else 0 } P(y,t) = ----------------------------------------------- sum for all f that predicted {y[1] ... y[t-1] } { 2^-length( f ) } The funny thing is you don't feed the past into the machines. Rather, you work with sets of machines that generated the past. Marc's summary sounds the same. Obviously with Solomonoff's method, the simplest function is strongly weighted, but it can also be outvoted by a large number of runners-up agreeing on a different prediction. Turing machines work on finite bit strings, so no real numbers either as input (t values) or output. Of course you can adapt his stuff to, e.g., floating point. For all that, and the intractability, I think Solomonoff's is a nice pinning down of Ockham's razor. He was this far in the...1950's? 1960's? --Steve

1 0

Re: [math-fun] What are the values of A and B?
by Gareth McCaughan 17 Mar '08

17 Mar '08

Dan Asimov wrote (off-list, presumably to spare me the embarrassment I so richly deserve) > But don't the terms of the problem say the numbers are > 1 ? Oh yeah, so they do. So what Scheherezade actually discovers from Petrouschka's first remark is that the number isn't of the form pq or p^2. -- g

1 0

Re: [math-fun] A very peculiar paper
by Marc LeBrun 16 Mar '08

16 Mar '08

>= Dan Asimov > Well, that may well be how they "do it". > But my conviction is that, regardless of how they try to do this, > there is no such thing as predicting, in any sense, an *arbitrary* function f [...] > in the sense of determining anything at all about f(x) for x >= t from the information given by f(x) for x < t . Well they are claiming *some* "sense" that survived refereeing (despite notational horrors), which is why I'm hoping someone who likely understands these things better than I (eg you!) will read the actual article and provide some further explanation. Or at least think about the construction I described and what it might lead to? I suspect this is one of those "watch me pull a rabbit out of my hat" tricks where it turns out that it really isn't a rabbit nor is it actually a hat. But even so I'd like to at least better understand what kind of rodent haberdashery is going on here. The authors say a lot of peculiar but suggestive things, often one right after another: "at almost every instant the strategy predicts some [valid] ''epsilon-glimpse'' of the future" "these results do not give a practical means of predicting the future" "the mu-strategy will correctly predict the present from the past on a set of full measure" "One needs to be cautious about interpreting that the mu-strategy is correct with probability 1. For a fixed true scenario, if one randomly selects an instant t then [it] does tell us [it] will be correct at t with probability 1. However if one fixes the instant t, and randomly selects a true scenario, then the probability that [it] is correct might be zero, or might not even exist, depending..." "...there is a scenario v in which strategy g is wrong at every point in W..." "the mu-strategy still almost always correctly predicts some of the future" With regard to AC they say it's "necessary to prove the existence of such strategies, [since] ZFC is adequate but ZF is not" having (I think) just argued that the contrary implies "there exists a set of reals that does not have the property of Baire (and is not Lebesgue measurable)". Alas I have no idea what that concretely means, other than gathering that there's subtlety hidden in "an *arbitrary* function f". Help, anyone?

1 0

Re: [math-fun] A very peculiar paper
by Dan Asimov 16 Mar '08

16 Mar '08

Marc writes: << Well maybe just a hint? Maybe. I puzzled for quite a while over the article, and really don't grok it, but I *think* the author's "mu-strategy" *might* be paraphrased as follows: . . . >> Well, that may well be how they "do it". But my conviction is that, regardless of how they try to do this, there is no such thing as predicting, in any sense, an *arbitrary* function f : R -> S (where R = reals and S is any given set with |S| >= 2), in the sense of determining anything at all about f(x) for x >= t from the information given by f(x) for x < t . Or put the endpoint t in the right-hand set; either way. (And I happen to accept the Axiom of Choice per se; that part isn't a problem for me.) --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

Re: [math-fun] A very peculiar paper
by Marc LeBrun 16 Mar '08

16 Mar '08

> Can someone give a hint as to why the claim made in the abstract [...] should not be considered ludicrous? Well maybe just a hint? Maybe. I puzzled for quite a while over the article, and really don't grok it, but I *think* the author's "mu-strategy" *might* be paraphrased as follows: Suppose we have some target v(t) from F = {f:R->S} that we want to define a strategy that constructs a "causal predictor" w(t) for v. They claim that such a strategy is plausible because "diagonalizing against" it would require R to be well-ordered. I believe their construction of w(t) is: First define an arbitrary well-ordering on the set of all functions F (thus I guess requiring AC). Let's call this "complexity". Then, for each t, set w(t) = f[t](t), where f[t] is the "simplest" f such that f[t](tau) = v(tau) for all tau strictly < t. That is, w(t) has the value at t of the "simplest" f which correctly predicts the past values of v(t) strictly prior to t. Note that the f[t] picked can still guess the wrong value of v(t). But at different t values the f[t] it picks can change, and whenever it picks one that guesses wrong at t it must pick different ones for all greater t. So as t increases the "causal correctness" of each f[t] must never decrease and moreover the "complexity" also never decreases. They remark that the natural interpretation of "complexity" gives Occam's Razor, but could just as well be the opposite (Occam's Hair?) Apparently they then show (assuming I got all this right) that this strategy produces a w(t) that "usually" guesses right at most t. Moreover it usually will keep each new f around "epsilon into the future" (not sure if that's a fixed epsilon or varies with t). I must admit I don't really "get" all this, and may have got it quite wrong. They refer to "well-known hat puzzles", where a line of prisoners is supposed to guess their own hat colors, hearing only the previous guesses, then generalizing that to indexing the prisoners with higher ordinals (the Beagle Boys in omega-land?). To my taste the exposition suffers from the common fault of not stating clearly up front a road map of how it's going to get where it intends to go, and from gratuitous distracting generalization and analogy--"a black hole does not give a practical time machine." But then, I'm probably both confused AND cranky. Hopefully someone on this list will provide a better exposition!

1 0

[math-fun] A very peculiar paper
by Dan Asimov 16 Mar '08

16 Mar '08

In the Feb. '08 Monthly, a strange article appears. Here is the abstract: << A Peculiar Connection Between the Axiom of Choice and Predicting the Future Authors: Hardin, Christopher S.; Taylor, Alan D. Abstract: We consider the problem of how one might try to guess values of a function based only on knowledge of the function on a subset of the domain, without any assumptions about the function being analytic or even continuous. At the level of a single point, this is a hopeless problem. When one considers a collection of many points, however, it is often possible, using the Axiom of Choice, to guess in such a way that most of the guesses are correct. In particular, there exists a strategy which, for an arbitrary function f from the reals into some set, will for all but countably many t correctly guess the value of f on an interval [t, t + d), d > 0, given only the values of f(x) for x < t. If one interprets this function as the evolution of a system over time, this means that, in principle, one can almost always predict an interval of the system's future based only on its past, without any assumption of continuity. >> I haven't read it, but this sounds so ridiculous on the face of it, it's tempting to just ignore it completely. Can someone give a hint as to why the claim made in the abstract (that it is possible to predict something about a arbitrary function's values for x >= t from its values from x < t) should not be considered ludicrous? --Dan P.S. I checked the calendar, and indeed it is not April 1. _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

3 2

Re: [math-fun] A very peculiar paper
by Dan Asimov 16 Mar '08

16 Mar '08

Joshua wrote: << On Sat, Mar 15, 2008 at 3:12 PM, Dan Asimov <dasimov(a)earthlink.net> wrote: > In particular, there exists a strategy which, for an arbitrary function f from the reals into some set, Maybe it only works for f : R -> {0} or some other one element set? I can do pretty well predicting that function's future. I would be surprised by not find it ludicrous if the image set had two elements. If the image set is the reals, it does indeed seem ludicrous. Maybe there's something in there about "describable functions" so there's only countably many functions possible? (E.g. functions that can be described with at most so many words, or functions containing finitely much information for some suitable definition of information). >> Actually, I see that the only condition they *do* put on the range set S (i.e., for an arbitrary function f : R -> S where R = reals) is that |S| >= 2. --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

Re: [math-fun] Patents
by N. J. A. Sloane 16 Mar '08

16 Mar '08

David, The best pat. att. in my 30 years of filing patents: Ron Slusky, rdslusky(a)verizon.net (mention my name) Best regards Neil Neil J. A. Sloane AT&T Shannon Labs, Room C233, 180 Park Avenue, Florham Park, NJ 07932-0971 Email: njas(a)research.att.com Office: 973 360 8415; fax: 973 360 8178 Home page: http://www.research.att.com/~njas/

1 0

[math-fun] Patents
by David Wolfe 15 Mar '08

15 Mar '08

Does anyone out in math-funland know of a patent attorney, ideally with some experience with puzzles? I've drafted a provisional patent application for the US, and wanted to run it by someone before mailing it off. Thanks, David

1 0