12 recent entries Archive:
Subtopics:
Comments disabled |
Fri, 21 Aug 2015
A message to the aliens, part 6/23 (chemistry)
Earlier articles: Introduction Common features Page 1 (numerals) Page 2 (arithmetic) Page 3 (exponents) Page 4 (algebra) Page 5 (geometry) This is page 6 of the Cosmic Call message. An explanation follows. The 10 digits again:
Page 6 discusses fundamental particles of matter, the structure of the hydrogen and helium atoms, and defines glyphs for the most important chemical elements. Depicted at top left is the hydrogen atom, with a proton in the center and an electron circulating around the outside. This diagram is equated to the glyph for hydrogen. The diagram for helium is similar but has two electrons, and its nucleus has two protons and also two neutrons.
The illustrations may puzzle the aliens, depending on how they think of atoms. (Feynman once said that this idea of atoms as little solar systems, with the elctrons traveling around the nucleus like planets, was a hundred years old and out of date.) But the accompanying mass and charge data should help clear things up. The first formula says
the mass of the proton is 1836 times the mass of the electron, and that 1836, independent of the units used and believed to be a universal and fundamental constant, ought to be a dead giveaway about what is being discussed here. If you want to communicate fundamental constants, you have a bit of a problem. You can't tell the aliens that the speed of light is !!1.8\cdot10^{12}!! furlongs per fortnight without first explaining furlongs and fortnights (as is actually done on a later page). But the proton-electron mass ratio is dimensionless; it's 1836 in every system of units. (Although the value is actually known to be 1836.15267; I don't know why a more accurate value wasn't given.) This is the first use of subscripts in the document. It also takes care of introducing the symbol for mass. The following formula does the same for charge : !!Q_p = -Q_e!!. The next two formulas, accompanying the illustration of the helium atom, describe the mass (1.00138 protons) and charge (zero) of the neutron. I wonder why the authors went for the number 1.00138 here instead of writing the neutron-electron mass ratio of 1838 for consistency with the previous ratio. I also worry that this won't be enough for the aliens to be sure about the meaning of . The 1836 is as clear as anything can be, but the 0 and -1 of the corresponding charge ratios could in principle be a lot of other things. Will the context be enough to make clear what is being discussed? I suppose it has to; charge, unlike mass, comes in discrete units and there is nothing like the 1836. The second half of the page reiterates the symbols for hydrogen and helium and defines symbols for eight other chemical elements. Some of these appear in organic compounds that will be discussed later; others are important constitutents of the Earth. It also introduces symbol for “union” or “and”: . For example, sodium is described as having 11 protons and 12 neutrons.
Most of these new glyphs are not especially mnemonic, except for hydrogen—and aluminium, which is spectacular. The blog is going on hiatus until early September. When it returns, the next article will discuss page 7, shown at right. It has three errors. Can you find them? (Click to enlarge.)[Other articles in category /aliens/dd] permanent link Wed, 19 Aug 2015
A message to the aliens, part 5/23 (geometry)
Earlier articles: Introduction Common features Page 1 (numerals) Page 2 (arithmetic) Page 3 (exponents) Page 4 (algebra) This is page 5 of the Cosmic Call message. An explanation follows. The 10 digits again:
Page 5 discusses two basic notions of geometry. The top half concerns circles and introduces !!\pi!!. There is a large circle with its radius labeled : The outer diameter is then which is !!2\cdot r!!. The perimeter is twice times the radius , and the area is times the square of the radius squared. What is ? It's !!\pi!! of course, as the next line explains, giving !!\pi = 3.1415926545697932…365698614212904!!, which gives enough digits on the front to make clear what is being comunicated. The trailing digits are around the 51 billionth places and communicate part of the state of our knowledge of !!\pi!!. I almost wish the authors had included a sequence of fifteen random digits at this point, just to keep the aliens wondering. The bottom half of the page is about the pythagorean theorem. Here there's a rather strange feature. Instead of using the three variables from the previous page, , the authors changed the second one and used instead. This new glyph does not appear anywhere else. A mistake, or did they do it on purpose? In any case, the pythagorean formula is repeated twice, once with exponents and once without, as both !!z^2=x^2+b^2!! and !!z\cdot z = x\cdot x + b\cdot b!!. I think they threw this in just in case the exponentiation on the previous pages wasn't sufficiently clear. I don't know why the authors chose to use an isosceles right triangle; why not a 3–4–5 or some other scalene triangle, for maximum generality? (What if the aliens think we think the pythagorean theorem applies only for isosceles triangles?) But perhaps they were worried about accurately representing any funny angles on their pixel grid. I wanted to see if it would fit, and it does. You have to make the diagram smaller, but I think it's still clear: (I made it smaller than it needed to be and then didn't want to redo it.) I hope this section will be sufficiently unmistakable that the aliens will see past the oddities. The next article will discuss page 6, shown at right. (Click to enlarge.) Try to figure it out before then.[Other articles in category /aliens/dd] permanent link Mon, 17 Aug 2015
A message to the aliens, part 4/23 (algebra)
Earlier articles: Introduction Common features Page 1 (numerals) Page 2 (arithmetic) Page 3 (exponents) This is page 4 of the Cosmic Call message. An explanation follows. Reminder: page 1 explained the ten digits:
And the equal sign . Page 2 explained the four basic arithmetic operations and some associated notions:
This page, headed with the glyph for “mathematics” , describes the solution of simple algebraic equations and defines glyphs for three variables, which we may as well call !!x,y,!! and !!z!!:
Each equation is introduced by the locution which means “solve for !!x!!”. This somewhat peculiar “solve” glyph will not appear again until page 23. For example the second equation is !!x+4=10!!:
The solution, 6, is given over on the right:
After the fourth line, the equations to be solved change from simple numerical equations in one variable to more abstract algebraic relations between three variables. For example, if
then
The next-to-last line uses a decimal fraction in the exponent, !!0.5!!: . On the previous page, the rational fraction !!1\div 2!! was used. Had the same style been followed, it would have looked like this: . Finally, the last line defines !!x=y^3!! and then, instead of an algebraic solution, gives a graph of the resulting relation, with axes labeled. The scale on the axes is not the same; the !!x!!-coordinate increases from 0 to 20 pixels, but the !!y!!-coordinate increases from 0 to 8000 pixels because !!20^3 = 8000!!. If axes were to the same scale, the curve would go up by 8,000 pixels. Notice that the curve does not peek above the !!x!!-axis until around !!x=8, y=512!! or so. The authors could have stated that this was the graph of !!y=x^3\div 400!!, but chose not to. I also wonder what the aliens will make of the arrows on the axes. I think the authors want to show that our coordinates increase going up and to the left, but this seems like a strange and opaque way to do that. A better choice would have been to use a function with an asymmetric graph, such as !!y=2^x!!. (After I wrote that I learned that similar concerns were voiced about the use of a directional arrow in the Pioneer plaque. (Wikipedia says: “An article in Scientific American criticized the use of an arrow because arrows are an artifact of hunter-gatherer societies like those on Earth; finders with a different cultural heritage may find the arrow symbol meaningless.”) The next article will discuss page 5, shown at right. (Click to enlarge.) Try to figure it out before then.[Other articles in category /aliens/dd] permanent link Sun, 16 Aug 2015My overall SE posting volume was down this month, and not only did I post relatively few interesting items, I've already written a whole article about the most interesting one. So this will be a short report.
[Other articles in category /math/se] permanent link Fri, 14 Aug 2015
A message to the aliens, part 3/23 (exponentiation)
Earlier articles: Introduction Common features Page 1 (numerals) Page 2 (arithmetic) This is page 3 of the Cosmic Call message. An explanation follows. Reminder: page 1 explained the ten digits:
And the equal sign . Page 2 explained the four basic arithmetic operations and some associated notions:
This page, headed with the glyph for “mathematics” , explains notations for exponentiation and scientific notation. (This notation was first used on page 1 in the mersenne prime .) Exponenentiation could be represented by an operator, but instead the authors have chosen to represent it by a superscripted position on the page, as is done in conventional mathematical notation. This saves space. The top section of the page has small examples of exponentiation, including for example !!5^3=125!!:
There is a section that follows with powers of 10: !!10^1=10, 10^2=100, 10^3=1000, !! and more interestingly !!10^{{}^-2} = 0.01!!:
This is a lead-in to the next section, which expresses various quantities in scientific notation, which will recur frequenly later on. For example, !!0.045!! can be written as !!45\times 10^{{}^-2}!!:
Finally, there is an offhend remark about the approximate value of the square root of 2:
[Other articles in category /aliens/dd] permanent link Thu, 13 Aug 2015
Another solution to Tuesday's git problem
On Tuesday I discussed an interesting solution to the problem of turning this:
into this:
Dave Du Cros has suggested an alternative solution: Make the changes required to turn off feature X, and commit them as B, as in my solution:
Then use
C' and C have identical trees. Then use
This has the benefit of not requiring anything strange. I think my solution is more general, but it's also weird, and it's not clear that the increased generality is useful. However, what if there were a
This last command would mean that the previous two commits, normally
into
one would use
I think [Other articles in category /prog] permanent link Wed, 12 Aug 2015
A message to the aliens, part 2/23 (arithmetic)
Earlier articles: Introduction Common features Page 1 (numerals) This is page 2 of the Cosmic Call message. An explanation follows. Reminder: the previous page explained the ten digits:
This page, headed with the glyph for “mathematics” , explains the arithmetic operations on numbers. The page is in five sections, three on top and two below. The subtraction sign actually appeared back on page 1 in the Mersenne prime !!2^{3021377}-1!! . The negative sign is introduced in connection with subtraction, since !!1-2={}^-1!!: Note that the negative-number sign is not the same as the subtraction sign. The decimal point is introduced in connection with division. For example, !!3\div 2 = 1.5!!: There is also an attempt to divide by zero: It's not clear what the authors mean by this; the mysterious glyph does not appear anywhere else in the document. What did they think it meant? Infinity? Indeterminate? Well, I found out later they published a cheat sheet, which assigns the meaning “undetermined” to this glyph. Not a great choice, in my opinion, because !!1÷0!! is not numerically equal to anything. For some reason, perhaps because of space limitations, the authors have stuck the equation !!0-1 = {}^-1!! at the bottom of the division section. The fifth section, at lower right, displays some nonterminating decimal fractions and introduces the ellipsis or ‘…’ symbol. For example, !!1\div 9 = 0.1111\ldots!!: I would have put !!2÷27 = 0.0740…!! here instead of !!2\div 3!!, which I think is too similar to the other examples. The next article, to appear 2015-08-14, will discuss page 3, shown at right. (Click to enlarge.) Try to figure it out before then.[Other articles in category /aliens/dd] permanent link
A message to the aliens, part 1/23 (numbers)
Earlier articles: Introduction Common features This is page 1 of the Cosmic Call message. An explanation follows. This page, headed with the glyph for “mathematics” , explains the numeral symbols that will be used throughout the rest of the document. I should warn you that these first few pages are a little dull, establishing basic mathematical notions. The good stuff comes a little later. The page is in three sections. The first section explains the individual digit symbols. A typical portion looks like this:
Here the number 7 is written in three ways: first, as seven dots, probably unmistakeable. Second, as a 4-bit binary number, using the same bit symbols that are used in the page numbers. The three forms are separated by the glyph , which means “equals”. The ten digits, in order from 0 to 9, are represented by the glyphs
The authors did a great job selecting glyphs that resemble the numerals they represent. All have some resemblance except for 4, which has 4 horizontal strokes. Watch out for 4; it's easy to confuse with 3. The second section serves two purposes. It confirms the meaning of the ten digits, and it also informs the aliens that the rest of the message will write numerals in base ten. For example, the number 14:
Again, there are 14 dots, an equal sign, and the numeral 14, this time written with the two glyphs (1) and (4). The base-2 version is omitted this time, to save space. The aliens know from this that we are using base 10; had it been, say, base 8, the glyphs would have been . People often ask why the numbers are written in base 10, rather than say in base 2. One good answer is: why not? We write numbers in base 10; is there a reason to hide that from the aliens? The whole point of the message is to tell the aliens a little bit about ourselves, so why disguise the fact that we use base-10 numerals? Another reason is that base-10 numbers are easier to proofread for the humans sending the message. The third section of the page is a list of prime numbers from 2 to 89:
and finally the number !!2^{3021377}-1!! , I often wonder what the aliens will think of the !!2^{3021377}-1!!. Will they laugh at how cute we are, boasting about the sweet little prime number we found? Or will they be astounded and wonder why we think we know that such a big number is prime? The next article, to appear 2015-08-12, will discuss page 2, shown at right. (Click to enlarge.) Try to figure it out before then.[Other articles in category /aliens/dd] permanent link Tue, 11 Aug 2015
Reordering git commits with git-commit-tree
I know, you want to say “Why didn't you just use Say I have commit A, in which feature X does not exist yet. Then in commit C, I implement feature X. But I realize what I really wanted was to have A, then B, in which feature X was implemented but disabled, and then C in which feature X was enabled. The C I want is just like the C that I have, but I don't have the intervening B. I have:
I want:
One way to do this is to use Now someone wants me to use
Now use interactive What I did instead was rather bizarre, using a plumbing command, but worked well. I wrote the code to disable X, and committed it as B, obtaining this:
Now B and C have the files I want in them, but their parents are wrong. That is, the history is in the wrong order, but if the parent of C was B and the parent of B was A, eveything would be perfect. But we can't just change the parents; we have to create a new commit, say B', which has the same files as B but whose parent is A instead of C, and we have to create a new commit C' which has the same files as C but whose parent is B' instead of A. This is what When we use So I did: % git checkout -b XX A Switched to a new branch 'XX' % git commit-tree -p HEAD B^{tree} 10ddf433039fd3cbc5bec0c64970a45add15482e % git reset --hard 10ddf433039fd3cbc5bec0c64970a45add15482e % git commit-tree -p HEAD C^{tree} ce46beb90d4aa4e2c9fe0e2e3d22eea256edceac % git reset --hard ce46beb90d4aa4e2c9fe0e2e3d22eea256edceac The first
says to make a commit whose tree is the same as B's, and whose parent
is the current Then I do the same thing with C:
makes a new commit whose tree is the same as C's, and whose parent is
the current head, which looks just like B. Again it reads a commit
message from standard input, and prints the SHA of the new commit on
the terminal, and again I use Now I have what I want and I only had to edit the files once. To
complete the task I just reset the head of my working branch to
wherever It seems to me that there have been a number of times in the past
when I wanted to do something like reordering commits, and
[ Thanks to Jeremy Leader for suggesting I write this up and to Jeremy Leader and Rik Signes for advance editing. ] [ Adendum 20150813: a followup article ] [Other articles in category /prog] permanent link Sun, 09 Aug 2015
A message to the aliens, part 0/23 (framing)
Earlier articles: Introduction (At left is page 1 of the Cosmic Call message. For an enlarged version of the image, click it.) First, some notes about the general format of each page. The Cosmic Call message was structured as 23 pages, each a 127×127 bitmap. The entire message was therefore 127×127×23 bits, and this would hopefully be suggestive to the aliens: they could try decoding it as 127 pages of 127×23-bit images, which would produce garbage, or as 23 pages of 127×127-bit images, which is correct. Or they might try decoding it as a single 127×2921-bit image, which would also work. But the choices are quite limited and it shouldn't take long to figure out which one makes sense.
Most of the message is encoded as a series of 5×7-pixel glyphs. The glyphs were generated at random and then subject to later filtering: candidate glyphs were discarded if they don't differ from previous glyphs in enough bit positions. This is to help the recipients reconstruct the glyphs if some of the bits are corrupted in transmission, as is likely. The experimenters then eyeballed the glyphs and tried to match glyphs with their meanings in a way that would be easy for humans to remember, to aid in proofreading. For example, the glyph they chose to represent the digit 7 was . People frequently ask why the message uses strange glyphs instead of standard hindu-arabic numerals. This is explained by the need to have the glyphs be as different as possible. Communication with other stars is very lossy. Imagine trying to see a tiny flickering light against the background of a star at a distance of several light years. In between you and the flickering light arevariable dist and gas clouds. Many of the pixels are likely to be corrupted in transmission. The message needs to survive this corruption. So glyphs are 35 bits each. Each one differs from the other glyphs in many positions, whereas a change of only a few pixels could change a standard 6 into an 8 or vice versa. A glyph is spread across multiple lines of the image, which makes it more resistant to burst errors: even if an entire line of pixels is destroyed in transit, no entire glyph will be lost. At the top left and top right of each page are page numbers. For example, page number 1: The page numbers are written in binary, most significant bit first, with representing a 1 bit and representing a 0 bit. These bit shapes were chosen to be resistant to data corruption; you can change any 4 of the 9 pixels in either shape and the recipient can still recover the entire bit unambiguously. There is an ambiguity about whether the numerals are written right to left or left to right—is the number 1 or the number 16?—but the aliens should be able to figure it out by comparing page numbers on consecutive pages; this in turn will help them when time comes for them to figure out the digit symbols. Every page has a topic header, in this case , which roughly means “mathematics”. The topics of the following pages are something like:
In the next article I'll explain the contents of page 1. Each following article will appear two or three days later and will explain another page. To follow the whole series of articles in your feed reader, subscribe to: RSS Atom (Next article, to appear 2015-08-10: page 1) [Other articles in category /aliens/dd] permanent link Tue, 04 Aug 2015
The list monad in Perl and Python
A few months ago I wrote an article about using Haskell's list monad to do exhaustive search, with the running example of solving this cryptarithm puzzle:
(This means that we want to map the letters At the end, I said:
I was specifically worried about Python's peculiar local variable binding. But I did receive the following quite clear solution from Peter De Wachter, who has kindly allowed me to reprint it:
after which the complete solution looks like:
I think this shows that my fears were unfounded. This code produces the correct answer in about 1.8 seconds on my laptop. Thus inspired, I tried doing it again in Perl, and it was not as bad as I remembered:
I opted to omit We don't need
After which the solution, although cluttered by Perl's verbose notation for lambda functions, is not too bad:
This runs in about 5.5 seconds on my laptop. I guess, but am not sure,
that An earlier version of this article claimed, incorrectly, that the Python version had lazy semantics. It does not; it is strict. [ Addendum: Aaron Crane has done some benchmarking of the Perl
version. A better implementation of HN user [Other articles in category /prog] permanent link Tue, 28 Jul 2015A few months ago I wrote an article here called an ounce of theory is worth a pound of search and I have a nice followup. When I went looking for that article I couldn't find it, because I thought it was about how an ounce of search is worth a pound of theory, and that I was writing a counterexample. I am quite surprised to discover that that I have several times discussed how a little theory can replace a lot of searching, and not vice versa, but perhaps that is because the search is my default. Anyway, the question came up on math StackExchange today:
OP opined no, but had no argument. The first answer that appeared was somewhat elaborate and outlined a computer search strategy which claimed to reduce the search space to only 14,553 items. (I think the analysis is wrong, but I agree that the search space is not too large.) I almost wrote the search program. I have a program around that is something like what would be needed, although it is optimized to deal with a few oddly-shaped tiles instead of many similar tiles, and would need some work. Fortunately, I paused to think a little before diving in to the programming.
For there is an easy answer. Suppose John solved the problem. Look at just one of the 7×11 faces of the big box. It is a 7×11 rectangle that is completely filled by 1×3 and 3×3 rectangles. But 7×11 is not a multiple of 3. So there can be no solution. Now how did I think of this? It was a very geometric line of reasoning. I imagined a 7×11×9 carton and imagined putting the small boxes into the carton. There can be no leftover space; every one of the 693 cells must be filled. So in particular, we must fill up the bottom 7×11 layer. I started considering how to pack the bottommost 7×11×1 slice with just the bottom parts of the small boxes and quickly realized it couldn't be done; there is always an empty cell left over somewhere, usually in the corner. The argument about considering just one face of the large box came later; I decided it was clearer than what I actually came up with. I think this is a nice example of the Pólya strategy “solve a simpler problem” from How to Solve It, but I was not thinking of that specifically when I came up with the solution. For a more interesting problem of the same sort, suppose you have six 2×2x1 slabs and three extra 1×1×1 cubes. Can you pack the nine pieces into a 3×3x3 box? (There will, of course, be some space left over.) [Other articles in category /math] permanent link |