I recently mentioned the fact that some (actually, almost all) functions (and real numbers) are not computable by a Turing machine. I gave some very familiar examples: the Busy Beaver function, the Entscheidungsproblem or halting problem, and Chaitin's omega.
One thing that bothers me is that all of these examples construct an uncomputable function or constant by reference to the properties of activities of Turing machines themselves: that is, they are all functions describing the (hypothetical) behavior of other computers or programs. All of these uncomputable things relate to attempts to summarize or predict the behavior of other computations or sets of computations.
There is a sense in which this feels like a gimmick, like these problems were devised or mentioned only in order to set up the diagonalization arguments, like these problems would be relatively unlikely to arise "naturally" in an area of mathematics or thought other than the problem of computability itself. Does anyone know an example of a function or number that is known to be formally uncomputable by a Turing machine but whose definition or at least motivation doesn't involve computation or computability?
"We're still evaluating and determining what the most appropriate course of action is," said Michael Ayers.
How about selling movies in cleartext?
On Saturday, I took the new Third Street Light Rail from the 4th and King Caltrain station to Bayshore. It was basically like riding any other Muni Metro line, but I was amazed at how much of San Francisco I've never seen. The southeastern part of the city is mysteriously invisible to those who don't live there; much of it is impoverished, it has much less economic activity than elsewhere in the city, portions have been polluted by a power plant and an abandoned naval station, there are few or no tourist attractions, and the region doesn't even appear on some tourist maps. For me, the City usually seems to be bordered by the freeways: I pretty much never venture southeast of the 280, or into the triangle bounded by the 280, the 101, and Cesar Chavez.
The Third Street rail line is still gleaming and new and takes thirty to forty minutes between Caltrain and Bayshore. It runs right past the new UCSF Mission Bay campus, which is going to have a major effect on southeastern San Francisco. If you like mass transit tourism, you have until April to take a preview ride on the weekend; board the T Third at any K, L, or M stop between Castro and Embarcadero, or at any former N stop between Embarcadero and 4th and King, or at any new T stop south of 4th and King. In the latter case, your ride is free until regularly scheduled service begins.
The notion of a cryptographic key was created by analogy to physical locks and keys, but it looks like the cryptographers may have had the deeper insight: the authorizing function of any "key" (a PGP key, a door key, a voting machine key) is really a relatively tiny amount of information (usually digital information, even in the case of pin-and-tumbler locks, since there are typically explicit digital descriptions of any key: note that "[a]ll lock makers assign [integer] values to each pin depth so that keys can be replicated by number rather than requiring the physical key", per Marc Tobias's explanation of bump keys, which includes a nice diagram of the fact that door keys are really physical analog approximations of what their manufacturers conceive of as small digital secrets).
The neat new example of this: a photograph of a pin-and-tumbler lock key is equivalent to the key itself. Not only can you make photographs from keys, you can make keys from photographs.
My roommate pointed out that the ubiquitous farewell "ciao" (known to Brazilians, for instance, as "tchau") actually means "slave".
Wikipedia agrees that the word comes from an abbreviation of a phrase akin to Italian "sono vostro schiavo" ("I am your slave"). This sounds less bizarre in the context of ancient letter closings like "I beg to remain / your most humble and obedient servant", but it's still pretty weird to modern ears.
"Schiavo" is still the modern Italian term for "slave" (that's what Terri Schiavo's last name means, as far as I can tell); compare Portuguese "escravo" and Spanish "esclavo". (I think that the name of the city and river Escravos in Nigeria is a reference to the Portuguese Atlantic slave trade. Nigeria lay along what was formerly known as the "Slave Coast", akin to the Gold Coast and Ivory Coast. The Slave Coast is no longer so called, yet Nigeria still has a city whose name means Slaves.)
The other bizarre thing is that, if we believe Wikipedia, all of these words -- "Escravos" as well as "ciao" as well as the English word "slave" -- actually derive from the name of the Slavs because of their propensity to be enslaved as prisoners of war in classical antiquity.
When I was in Germany I admired some posters that read "Die moderne Frau / kocht ohne Sau" so much that I bought one from the vegan store in Berlin where I went shopping. The poster wouldn't fit into my luggage, so I carefully carried it by hand on various trains, busses, and planes, and through several airports, and then promptly lost it on the Boston subway.
Fortunately, I was able to order some replacements from emu Verlag, and they arrived today.
This gives rise to three obvious questions:
- Are these posters sexist?
- How would you translate the sense of the slogan into other languages so that it still rhymes? (I remember when a classicist at Berkeley, probably Jed Parsons, had assembled a remarkable set of translations of the traditional anti-poison ivy mnemonic rhyme "Leaves of three / let them be" into a huge number of other languages -- for example "Herba trifola / fac ut sit sola". Who can do the same for this jingle?)
- I have one spare copy. Who would like it? (It seems natural somehow to give women higher priority than men...)
In my opinion, the franchise that's really crying out to be made into a movie is Raymond Smullyan's work. Especially the various islands and countries with vampires, sorcerers, knights, knaves, and so on. They would be a picturesque backdrop for a movie and I don't think it could help but be the ultimate geek thriller.
[Main]
Contact: Seth David Schoen
