August 2015 - mathfun@mailman.xmission.com

[math-fun] Pointer Permutation Machines a la Deutsch-Schorr-Waite
by Henry Baker 26 Aug '15

26 Aug '15

I've been looking again at what I call "pointer permutation" machines a la the Deutsch-Schorr-Waite (DSW) marking algorithm for garbage collection. Gosper utilized the PDP10 Exchange instruction to implement a Lisp-like CONS in HAKMEM. (DSW machines go back to a time even before the invention of Lisp to the IPL-V language of Carnegie Mellon (nee Tech), where IPL-V programs constructed linked lists in registers using an "assembly language" approach to list processing. IPL-V becomes a permutation machine if one crosses out the use of pointer copying operations.) (One of the reasons why I'm intrigued by these machines is that they can often be run *backwards*, as each permutation operation has an inverse. The other reason is that I know how to speed these machines up, by putting in actual reference counts behind the scenes, replacing DEEP-COPY by a constant-time refcnt increment operation, and using a "hash cons" scheme behind the scenes to make sure that deep recursive EQUAL can always be optimized into shallow EQ. (See my paper "Lively Linear Lisp", which explains these speedup tricks.)) DSW machines can only *permute* pointers, and can neither create nor destroy them. Therefore, the reference counts of the objects pointed to remain *constant*. There is a problem, however. Without some restrictions, pointers can become involved in *cycles*, and if the reference counts are all exactly *one*, then such a cycle becomes *disconnected* from the rest of the world. Therefore, it becomes important to elucidate rules which can guarantee that objects can never become disconnected. Machine model. A finite set of *registers* -- R0, R1, ..., Rk. (Perhaps k ~ 16 or k ~ 32.). A set of *atoms* which have no restrictions on reference counts. Think of atoms as small integers or characters. A set of *objects* which have two *components* -- CAR and CDR -- which can point to either *atoms* or other *objects*. A set of permutations on registers -- e.g., Ri -- and components of registers, e.g., CAR(Ri), CDR(Ri). These component expressions CAR(Ri), CDR(Ri) only make sense if Ri points to an object (not an atom). A set of *swapping* operations, e.g., Ri<->Rj (i /= j), or Ri<->CAR(Rj) (i /= j) or Ri<->CDR(Rj) (i /= j). We note that if Rj points to an atom, then Ri<->CAR(Rj) will FAIL without making any changes. We also allow for a *control stack*, which can store atoms and program return addresses *but not pointers*. Thus, we can have recursive programs, but it is up to the recursive program itself to save & restore any list structure pointers. [Here is a *huge* advantage for modern hack-proof programming: we should have little need for "address randomization" as currently practised by Microsoft & others.] A set of rotation permutation operations. We follow the Common Lisp convention in which rotations are a cyclic left shift. Thus, we can have rotate(Ri,Rj,Rk), where i,j,k are all distinct, and rotate(Ri,Rj,CAR(Rk)), i,j,k distinct, etc. Similarly, rotate(Ri,Rj,CAR(Rk)) fails if Rk points to an atom (w/o making any changes). We can test the contents of the registers for atom-ness, and for succinctness, we can also perform tests like atom(CAR(Ri)) and atom(CDR(Ri)). So far, it is difficult to get into trouble. However, we have also crimped a bit on expressiveness. It would be very nice to allow rotate(Ri,CDR(Ri),Rj), for instance. Suppose Ri = (A . B), Rj = C. Then after rotate(Ri,CDR(Ri),Rj), we have Ri = B, Rj = (A . C). In effect, we have done a "simultaneous"/"non-interruptible"/"stomic" pop and push: we have popped A off Ri and pushed it onto Rj. The inverse of this operation is rotate(Rj,CDR(Rj),Ri). Such "pop-push" operations are extremely common when programming with these machines. For example, if Ri is the freelist, and Rj points to C, then rotate(freelist,CDR(freelist),Rj) performs a *CONS* operation and leaves the result (NIL . C) in the register Rj. (This CONS is somewhat analogous to Gosper's EXCH CONS hack.) Note that rotate(CDR(Ri),Ri,Rj) still "works", and still preserves reference counts, but the cell originally pointed to by Ri becomes inaccessible. Thus, one rule we need is that in any rotate operation, the sub-sequence ...,CAR(Ri),Ri,... cannot occur; neither can the sub-sequence ...,CDR(Ri),Ri,... If one starts to allow more deeply nested operations, then the rule(s) become far more complicated. The general issue is the same: we don't want to create cycles of length 1, 2, 3, ..., which will then become inaccessible. Thus, rotation sub-sequences like ...,C*R(Ri),Ri,..., where C*R stands for CAR, CAAR, CADR, CDR, CDDR, etc., will also fail. Q: Has anyone studied machines like these in any depth (i.e., other than for implementing DSW GC algorithms) ? Q: Is there a more elegant way to express the constraints required to keep all objects connected to the registers by means of a directed path from one of the registers ? Q: Are more complex operations need/wanted for programming? I've found a use for a permutation that converts ((A . B) . C) into (A . (B . C)) and its inverse operator, but perhaps there are other extremely useful permutations ? Q: Are non-cyclic permutations useful or expressive? Clearly, any permutation can be broken into its cycle structure, but what happens if CAR(Ri) appears in one cycle and Ri appears in the other? Q: What is an appropriate "high level" language for such a machine. I've come up with Linear Lisp, in which each argument to a function is *consumed* by the called function, so that it either becomes part of the output list structure, or gets recycled back to the freelist by the called function. Perhaps there are other models?

2 1

[math-fun] Stephen Hawking: Enter, but leave your info at the door
by Henry Baker 25 Aug '15

25 Aug '15

FYI -- A large number of people (including me) have been saying this for many years; indeed, the Bekenstein idea begs for this holographic solution: the information is painted on the surface of the black hole, and doesn't disappear after all. https://www.washingtonpost.com/news/speaking-of-science/wp/2015/08/25/steph… Stephen Hawking believes heÂs solved a huge mystery about black holes By Rachel Feltman August 25 at 5:58 AM Follow @rachelfeltman On Tuesday, famed physicist Stephen Hawking presented new theories on black holes to a crowd of esteemed scientists and members of the media at KTH Royal Institute of Technology in Stockholm. Hawking focused on something called the information paradox, which continues to puzzle scientists who study black holes. In a nutshell, the paradox involves the fact that information about the star that formed a black hole seems to be lost inside it, presumably disappearing when the black hole inevitably disappears. These things cannot be lost, according to the way we think the universe works, and physicists generally believe that they aren't really lost. But where does the information go when the black hole that's absorbed it goes kaput? It's brainy stuff, but without an explanation for the apparent paradox, some of the most basic laws we think exist in the universe are at stake. At a public lecture in Stockholm on Monday, Hawking implied that our concept of time itself could fall apart if black holes proved to be exempt from such laws. On Tuesday, he explained his new theory: "I propose that the information is stored not in the interior of the black hole as one might expect, but in its boundary, the event horizon," Hawking said. The event horizon is the sort of shell around a black hole, past which all matter will be drawn into the dense object's powerful embrace. According to Hawking's idea, the particles that enter a black hole leave traces of their information on the event horizon. When particles come back out Â in a phenomenon called Hawking Radiation Â they carry some of that information back out, preserving it. Technically, anyway. "The information is stored in a super translation of the horizon that the ingoing particles [from the source star] cause," he explained, for those of you who like a little more physics lingo. "The information about ingoing particles is returned, but in a chaotic and useless form. For all practical purposes the info is lost." At Monday's public lecture, he explained this jumbled return of information was like burning an encyclopedia: You wouldn't technically lose any information if you kept all of the ashes in one place, but you'd have a hard time looking up the capital of Minnesota. The translations that occur form a sort of hologram of the original particles, Hawking said Â a hologram in the sense that 3-D information is recorded on a 2-D surface. When radiation leaves the black hole, it carries some of that information preserved on the event horizon with it. Nobel laureate Gerard t'Hooft, who was present for the discussion, has been thinking about information loss in a similar way, and he cited several papers he has published on the subject. It will take more discussion Â and much comparing of math equations Â to establish what's new about Hawking's theories in relation to t'Hooft's, and whether Hawking has overcome some of the issues associated with earlier iterations of the idea. It's worth noting that Hawking Â who drew a large crowd of Swedish journalists on the morning of his announcement Â is not alone in presenting big new ideas on black holes this week. Hawking's presentation was part of a week-long conference on black holes organized by University of North Carolina at Chapel Hill physicist Laura Mersini-Houghton. Hawking and his colleagues Â some of the greatest minds in theoretical physics Â are hoping to answer some of science's most burning questions about how black holes work. You can read more about the conference here. http://www.washingtonpost.com/news/speaking-of-science/wp/2015/08/24/at-a-g…

1 0

Re: [math-fun] Another(?) stick length illusion
by Dan Asimov 25 Aug '15

25 Aug '15

Huh? At least to the nearest pixel, both lines are the same length. They are corresponding diagonals of congruent regular pentagons. I find this to be an impressive illusion. --Dan << << To me the stick that is in fact longer looks like it is in fact longer. If they're supposed to be the same length I think your image needs a bit of editing. >> On Thu, Aug 19, 2010 at 4:31 PM, Bill Gosper <billgosper(a)gmail.com> wrote: > While hacking the pentagon fill, tutor Julian found > www.tweedledum.com/rwg/6pents.png, which seems to work backwards: > The stick larger than its context appears smaller than the > stick smaller than its context. >> _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

5 4

[math-fun] "Mathiness" == how economists lie with math
by Henry Baker 25 Aug '15

25 Aug '15

Where I come from, P and (not P) == complete crap. [The C/C++ language has forever ruined the "=" symbol; a single "=" in a C/C++ expression is either a bug or an obfuscated code winner (which used to get you a job at Microsoft); only "==" is safe from side-effects.] http://blogs.wsj.com/economics/2015/08/17/qa-paul-romer-on-mathiness-and-th… Paul Romer: "Gene Fama at University of Chicago got [the Nobel Prize in Economics] for the efficient markets hypothesis. Robert Shiller from Yale got [the Nobel Prize in Economics] for his view that these markets are not efficient"

1 0

[math-fun] Reciprocal fib sum
by Bill Gosper 25 Aug '15

25 Aug '15

Borwein*2, Exercise 3.7.10 (at least my old edition): "A remarkable elementary result is Sum[1/(Fibonacci[1 + 2*k] + Fibonacci[1 + 2*n]), {n, 0, Infinity}] == (Sqrt[5]*(1 + 2*k))/ (2*Fibonacci[1 + 2*k]) [. . .] A related formula is [...]" which is just the k=3 case of the first formula, but with a different, and correct rhs! I.e., the first formula seems completely wrong, Empirically, I get Sum[1/(Fibonacci[1 + 2*k] + Fibonacci[1 + 2*n]), {n, 0, Infinity}] == ((1 + GoldenRatio^(2 + 4*k))* (1 + 2*k))/(2*(-1 + GoldenRatio^(2 + 4*k))* Fibonacci[1 + 2*k]) The rhs might have a slick reexpression in fibonaccis. --rwg (Recall our old sum 1/fib(n) saga, where B&B seem to cop out and give only a Lambert series, but reading between the lines, there's a hairy closed form in terms of d/dq log qpochhammers.)

3 4

[math-fun] The Planck Power
by Warren D Smith 24 Aug '15

24 Aug '15

c^5 / G = 3.6 * 10^52 watts. A black hole, in the final stage of its evaporation, lasting order one Planck time, would emit about this amount of power. Is it just an odd coincidence... that this amount of power, is roughly equal to the total luminosity of everything in the observable universe? (Actually, I think the universe currently is perhaps 10^5 times less powerful than the Planck power, but the universe was more powerful in the past.)

2 1

[math-fun] more on rotten-egg superconductivity
by Warren D Smith 23 Aug '15

23 Aug '15

http://www.nature.com/nature/journal/vaop/ncurrent/full/nature14964.html http://arxiv.org/abs/1506.08190 http://arxiv.org/abs/1412.0460 Now Tc=203 kelvin, allegedly, in H2S, but only at 90-150 GPa pressure achievable only in tiny samples inside a diamond anvil. Building confidence in their claim is observation of isotope shift to lower Tc when H is changed to deuterium, and the fact they've observed the superconductivity 2 ways: direct resistance and Meissner effect (but in different experiments). They speculate that other hydrogen-rich compounds converted to metals by pressure, might also be superconductive with high Tc. When they aren't experiencing cold fusion :)

1 1

[math-fun] Bekenstein
by Warren D Smith 22 Aug '15

22 Aug '15

Jacob Bekenstein just died; invented concept of black hole entropy as a grad student; then Hawking made everybody believe it.

1 0

[math-fun] half-life of Gordian's Knot puzzle
by Veit Elser 21 Aug '15

21 Aug '15

I spent a frustrating hour trying to solve the “Gordian’s Knot” puzzle, recently given to me by a friend. The principle of the puzzle is nice: six solid polyomino pieces, formed by making holes inside 1x5x7 rectangular slabs, arranged as pairs in three orthogonal planes and initially forming a very compact “nucleus”: http://www.amazon.com/Think-Fun-6820-ThinkFun-Gordians/dp/B000EGI4OO The goal is to completely remove one of the pieces. But it’s not a fun puzzle to solve because the pieces often jam and don’t slide very freely. It wasn’t too hard to write a short computer program that random-walks its way to the solution (at each step it picks at random one of the few legal moves). I’m sharing this with math-fun because it turns out to be a nice metaphor of radioactive decay. After a period of diffusive motion where all six pieces are “bound” together, an “alpha particle” is ejected, seemingly at a random moment. Unlike the Coulomb barrier that a real alpha particle has to tunnel through, the orange piece in this puzzle has to find its way through an entropic bottleneck. From the few decays I’ve observed up to now, I estimate the half-life to be several hundred moves. **************************************************************************************** Warning: exercise extreme caution when clicking the following link: https://www.dropbox.com/s/bxcc7h2am1e49ww/alphadecay.gif?dl=0 **************************************************************************************** -Veit

6 6

[math-fun] If you're looking for milepost 420, you won't find it in Idaho.
by Henry Baker 21 Aug '15

21 Aug '15

FYI -- I don't think this plan is going to work; the "419.9" signs are now all going to get stolen by engineers (& perhaps mathematicians, who will put a little overbar on the last "9"). In fact, the "419.9" signs are way cooler than the "420" signs ever were! "the mile marker has been replaced with 419.9 signs" http://news.yahoo.com/idaho-replaces-mile-marker-420-419-9-thwart-184700949… BOISE, Idaho (AP) Â If you're looking for milepost 420, you won't find it in Idaho. Idaho transportation officials say the mile marker has been replaced with 419.9 signs to curb thieves eager to own a number associated with marijuana enthusiasts. Turns out, Idaho isn't alone in this problem. States like Washington and Colorado have also replaced 420 signs with 419.9 after consistently having to replace them after thefts by supposed sticky-fingered stoners. Adam Rush of the Idaho Transportation Department says officials have replaced the old sign along U.S. Highway 95 with "MILE 419.9," just south of Coeur d'Alene. Rush added that this is the only 420 sign the department has replaced in Idaho, a state known for its strict anti-marijuana laws despite being nearly surrounded by states with relaxed pot regulations. Most highways in the country don't cover more than 400 miles. For example, Oregon has been spared the spike in sign thefts due to having no highways long enough to reach past a 400 milepost, even though it recently legalized marijuana. "Having a sign removed from a highway is pretty rare," Rush said. "In Idaho, people will shoot at them or write on them before stealing them completely. We spend more time mending signs than replacing them." Rush said that the department didn't want to leave the milepost empty because the signs can be valuable for drivers tracking their journey. The number "420" has long been associated with marijuana, though its origins as a shorthand for pot are murky. Washington has two highways long enough to have 420 mileposts that have both been plagued by thieves snatching the sign over the years, said Barbara LaBoe, spokeswoman for the Washington State Department of Transportation. That all stopped three years ago Â the same time voters legalizzed pot Â when officials replaced one of the signs with 419.9 along Highway 20 near the Idaho border. The other sign on U.S. Highway 12 remains missing, with no immediate plans to be replaced, LaBoe said. Sometimes a 420 milepost doesn't need to be stolen to make the news. In Montana, the state's largest pot busts occurred while pulling over a driver at milepost 420 along Interstate 90. Law enforcement officials found 115 pounds of marijuana hidden in the car

4 3