REPERIENDI

Thursday, February 10, 2005

Mad orreries

The dried asparagus petal becomes the hood and cowl of a tiny gear-driven monk; the pushcart writes a message to its propulsion; and a tiny yellow chair dances above hovering bedrock.

http://www.arthurganson.com/pages/Sculptures.html

The Tale of n-Categories

The stuff my (day)dreams are made of.

http://math.ucr.edu/home/baez/week73.html

Surrational entymology

Scott Mutter meets Henri Fabre

http://www.worth1000.com/cache/gallery/contestcache.asp?contest_id=2536

Twisters

Earth, air, fire, water.

Sunday, February 13, 2005

Our Lady of the Scarab

Doug writes, "I liked the bugs. I had an idea about ordering dead beetles from a catalog and making buildings out of them, with wings for stained glass windows, antennae framing the vaults, iridescent scarabs for roof tiles... but I haven't gotten around to it yet. It's a little expensive. Here's the catalog, though: http://www.insect-sale.com/"

Monday, February 14, 2005

Justifying the Ansible

"It is argued that immense physical resources - for nonlocal communication, espionage, and exponentially-fast computation - are hidden from us by quantum noise, and that this noise is not fundamental but merely a property of an equilibrium state in which the universe happens to be at the present time. It is suggested that 'non-quantum' or nonequilibrium matter might exist today in the form of relic particles from the early universe. We describe how such matter could be detected and put to practical use. Nonequilibrium matter could be used to send instantaneous signals, to violate the uncertainty principle, to distinguish non-orthogonal quantum states without disturbing them, to eavesdrop on quantum key distribution, and to outpace quantum computation (solving NP-complete problems in polynomial time)."

http://www.arxiv.org/abs/quant-ph/0203049

Thursday, February 17, 2005

Genesis of / in print

Gutenberg's bible online

Auckland City Library's medieval manuscripts online

Strap on some Steve Austin

Legs: http://superdairyboy.com/poweriser.html
Eyes: http://www.angelfire.com/80s/sixmhz/infrared.html

Friday, February 18, 2005

Jorge Borges

The best story of his to begin with is Tlon, Uqbar, Orbis Tertius. More of Borges' surreality can be found at a site dedicated to his works. In the same vein, Ray Girvan tells the story of Udo of Aachen with a neat reference at the bottom to Hildegard of Bingen, including her Litterae Ignotae and Lingua Ignota.

Tuesday, February 22, 2005

Galloping Gertie

I remember watching this film (Not VHS!) about Galloping Gertie in a physics class on numerical analysis. Ross Spencer was illustrating how the wave equation was related to the simple harmonic oscillator. The approximation is only good insofar as the restoring force is linear. "And here it goes nonlinear..."

Time, time, time / See what's become of me...

SunSunday
MoonMonday, Lunes
MarsMartes
MercuryMiercoles
Jupiter (Jove)Jueves
VenusViernes
SaturnSaturday

Why this order? See week175 of This Week's Finds in Mathematical Physics and scroll down to the postscript.

Thursday, March 03, 2005

Way to go

Gizmag's got a feature showing the top 50 articles in Motorcycles. Cool stuff like the Bombardier Embrio and Tommy Forsgren's Hermes.

My favorite, though, wasn't directly featured. It's the RIOT Wheel. I would love to drive one of these to work.

Sunday, March 06, 2005

Am Ha-Aphar

The science of forecasting dust storms, with a really neat animation of how dust devils work.

Monday, March 07, 2005

Branding iron for your brain

Exposure to advertising alters your brain!

Mathematics as punishment in the New Testament

1 NOW about that time Herod the king stretched forth his hands to vex certain of the church.

2 And he killed James the brother of John with the sword.

3 And because he saw it pleased the Jews, he proceeded further to take Peter also. (Then were the days of unleavened bread.)

4 And when he had apprehended him, he put him in prison, and delivered him to four quaternions...

(Acts 12:1-4)

Tuesday, March 08, 2005

Chickenscratch

Omniglot has every abjad, alphabet, syllabic alphabet, and syllabary ever in common use; samples of logographic, ideographic, and semantic-phonetic compounds; alternative writing systems (generally phoenetic systems for English, but also includes ones used in TV & movies); and new ones made up by fans of the site.

Thursday, March 10, 2005

Pull a Ted Turner

Fast simple colorizer

Monday, March 14, 2005

Making multimiedia easy again

mov ax, 13h
int 10h

That's all you had to do to get a screen 320x200 with 256 colors on the PC under DOS. One big linear array, no color planes, pure and simple. I thought those days were gone forever until I found LibSDL:

Simple DirectMedia Layer is a cross-platform multimedia library designed to provide low level access to audio, keyboard, mouse, joystick, 3D hardware via OpenGL, and 2D video framebuffer. It is used by MPEG playback software, emulators, and many popular games, including the award winning Linux port of "Civilization: Call To Power."

Simple DirectMedia Layer supports Linux, Windows, BeOS, MacOS Classic, MacOS X, FreeBSD, OpenBSD, BSD/OS, Solaris, IRIX, and QNX. There is also code, but no official support, for Windows CE, AmigaOS, Dreamcast, Atari, NetBSD, AIX, OSF/Tru64, RISC OS, and SymbianOS.

SDL is written in C, but works with C++ natively, and has bindings to several other languages, including Ada, Eiffel, Java, Lua, ML, Perl, PHP, Pike, Python, and Ruby.

Thursday, March 17, 2005

Cryovolcanism

All too frequently do we fail to recognise ice as a mineral because it does not behave as we believe conventional rocks and minerals should. We are brought up from an early age with an almost magical awe of this substance, which forms sparkly icicles and glittering snowflakes, and is great fun to slide on. Yet water ice is among the most important rock forming minerals in the solar system. Its behaviour as a crystalline solid and as polycrystalline aggregates (i.e., rocks) are indistinguishable from the materials which we, as geologists, are familiar with; it is simply the case that, on Earth, it exists closer to its melting point than, for example, silicates. In the frigid outer solar system, however, ice finds its true home as a substance from which mountains and canyons are built and, perhaps, from which dunes, beaches, and deltas are constructed (e.g., Whalley, 1985).

By direct analogy with terrestrial igneous processes we would therefore refer to a melt of the native rocks as a magma. On icy satellites this magma will consist mainly of water, with admixtures of ammonia. Like terrestrial vents these fluids will construct volcanic edifices such as shields and domes, complete with flow fields, and also form intrusive bodies such as sills and dykes. The accepted term for these fluids is cryomagma and the eruptive process, cryovolcanism.

A useful virus the size of a fridge

http://staff.bath.ac.uk/ensab/replicator/

Saturday, March 26, 2005

Solids passing thhrough each other without friction

[Article begins with discussion about superfluid helium and BECs.]

... What about solids? Can they "flow" without friction? Last year Moses Chan (Penn State) announced the results of an experiment in which solid helium-4 was revolved like a merry-go-round. It appeared that when the bulk was revolved at least part of the solid remained stationary. In effect part of the solid was passing through the rest of the solid without friction...


http://www.aip.org/pnu/2005/724.html

Saturday, April 09, 2005

Try to see things my way...

The genes for red and green color vision are right next to each other on the X chromosome. The gene for blue is on a different chromosome. Sometimes, during meiosis, the genes don't go to the right places. The possible combinations are (), (r), (rr), (g), (gg), (rg). If (rg) doesn't occur, and the child is male, then he'll be colorblind (or perhaps an anomalous trichromat). If (rr) or (gg) occurs, and the child is female, she'll inherit (rg) from the other X and will have a good chance of becoming a tetrachromat. The peak sensitivity of the two needs to differ enough that the brain perceives them as separate colors.

William Stark had a lens removed from one eye at age 12, at which point he realized that he could see near-UV light in the 300-400 nm range. It turns out that the lens is opaque to that frequency of light. He went on to study UV perception in Drosophila and published the seminal paper on UV perception in humans. He perceives UV light as pale blue; his hypothesis is that all color receptors are somewhat sensitive in the UV range, but blue slightly moreso.

One researcher, however, believes that humans actually have four receptors, including one for UV, and that all humans could potentially be tetrachromats if not for the lens. If this is true, then akaphic humans might potentially perceive near-UV as a separate color if they learn to see with all four colors rather than getting a fourth color after the brain has learned to see with only three. What colors will the blind see when they get bionic eyes? What if the spectrum differs between eyes?

Synesthesia is a condition that affects the perception of color in humans. It's well-known that the brain preprocesses sensory information far earlier than we become consciously aware of it. Synesthetics have distinct sensory perceptions associated with ideas. Often, these come in the form of color, but may be touch, smell, sound, or even spacial perception ("the number sixteen is to my right"). Ramachandran was the first to use pop-out tests to show that synesthesia was not just the result of an overactive imagination.

Ramachandran reported that one colorblind synesthetic subject perceived "Martian colors" that he had never seen with his eyes: his visual brain was being stimulated nonoptically. Could someone whose visual brain was being stimulated in a way correlated to a video camera perceive "Martian colors," too? Sony just got a patent on some technology that may allow direct non-invasive neural stimulation with better resolution than transcranial magnetic stimulation.

I think the nearest thing to sensory wierdness that I've experienced was a slight disruption of my proprioceptive system. When I approach conditions of sensory deprivation--while laying in a warm bed half-asleep, for instance--I sometimes begin to feel like my limbs can't decide whether they are toothpick-thin or fat and sausage shaped. The qualium of switching between the perceptions is almost identical to that of looking at certain optical illusions, like deciding what side is the top of a 2-d projection of a wireframe cube. My sister Karen reports having felt the same thing.

Benham's Top and Fechner's colors produce a subjective color illusion; no one knows for certain how it works, but it appears that the response rates of cones differs; thus colorblind people should not experience the effect. It also seems to have something to do with motion: I masked off all but a thin strip of the Fechner colors demo, perpendicular to the motion, to see if it was just the flashing that caused it. The colors all disappeared for me.

The vOICe is an application that converts images to sound. The vertical axis becomes pitch, while the horizontal becomes time; intensity becomes volume. Users consistently report the sound-as-sight becoming unconscious, and one late-blind person reports that her brain reconnected the input with her visual cortex. She perceives the sound as sight, and even experiences depth due to perspective! I think that if there were two cameras directing different input to each ear, the brain might even do a comparative depth perception.

Haidinger's brush is a yellow-vs-blue cross due to the concentric circles of the dichroic molecule Lutein around the fovea. Almost anyone can learn to see polarized light with a little practice. I've seen it on my LCD screen at work. I haven't seen it in the sky yet, though.

The latest DNRC newsletter has a bit on sensory wierdness:

"Alert readers have noticed that Dilbert looks different lately, almost as if someone else is drawing it. Well, it's still me, but here's what's happening: I lost the use of my right hand for drawing, thanks to overuse. Technically, it's called a focal dystonia. It's essentially a brain-mapping problem caused by overusing the hand. The hand is structurally healthy and perfectly fine for every possible use EXCEPT drawing. It's very specific. My brain essentially removed from me the ability to do the thing that was hurting it.

One way I can confirm that it's a brain issue is that when I try to draw with my LEFT hand, my RIGHT hand spasms immediately. Some part of my brain doesn't want me drawing because that's what caused all the discomfort.

For a few weeks I worked left-handed. I'm not quite ambidextrous, but if I work slowly, it looks about the same. Some of the lefty ones have a "L.H." on them to tip you off.

Left-hand drawing was too slow, so I looked for, and found, a technical solution. Wacom has a product that allows you to draw directly onto a special flat computer screen that tilts and turns just like paper on a drawing board. It's called the Cintiq 21UX, and I've been using it for the past several weeks, with much success. It will take a while for my characters to look the same as old, but I'm closing in on it.

The reason I can draw on the computer, but not on paper, is because now I work at a different scale (larger), and the feel of the stylus on the screen is so different from pen-on-paper that my brain doesn't think I'm drawing, so it doesn't trigger the hand spasms.

Brains are funny."

Monday, April 25, 2005

When "they" is a singular pronoun

http://tinyurl.com/avw7g

Wednesday, April 27, 2005

Pyrofusion

"We can build a tinyself-contained handheld object which, when plunged into ice water, creates fusion," Putterman says.
http://rodan.physics.ucla.edu/pyrofusion

Monday, May 09, 2005

Mathematical artists

Bathsheba Grossman, George Hart, and Helaman Ferguson, who's a Mormon and was the inventor of the PSLQ algorithm, named one of the top ten algorithms of the century. This algorithm found the spigot algorithm for $\pi$.

Sunday, June 05, 2005

Get your own crystal ball

http://www.actualitysystems.com/site/content/perspecta_display1-9.html#
or seerstone
http://www.rickgrunder.com/treasurespast.htm

Monday, June 06, 2005

Mechanical gills

Crack open a can of soda and you hear the distinctive "pfft!" of gas coming out of solution when the pressure drops. Strap a pump on your back that can reduce the pressure in a tank of water, and you get oxygen out. Dump the waste water, suck in some fresh, and cycle.
http://www.isracast.com/Articles/Article.aspx?ID=63

One step closer to digital immortality

IBM to begin brain simulation project:
http://www.newscientist.com/article.ns?id=dn7470

Friday, June 17, 2005

Fortify your frontroom

BIG Lego castles:
http://www.minifig.co.uk

Sunday, July 03, 2005

Fun stuff to get you maimed

http://www.dangerouslaboratories.org/

Monday, July 04, 2005

Time

Reveal watch and pin clock

Monday, July 11, 2005

More about seerstones

http://incider.byu.edu/vwb/symbol/all%20seeing%20eye.htm (google cache)

A better solution than taping an upside-down milkjug to the back of the bike

http://mnt.is-a-geek.org/tron/
For more biking fun: http://dclxvi.org/chunk/operations/chunk/image/hires/joust150.jpg
But if you're really serious, you're gonna need one of these.

Thursday, July 14, 2005

Star Wars toys that never were

http://www.cincitoymuseum.com/conceptualmodel.html

Be sure to check out the rest of the museum, too.

Time

http://www.artlebedev.com/portfolio/sxaginta/movement/

Wednesday, July 20, 2005

Polage, Time

Some things I thought of that others thought of first and have done properly:

This lady does "paintings" in polarization of cellulose. (Yet another use for a laser etcher: draw the stuff in Adobe Illustrator and cut the cellulose with the etcher.)

http://www.austine.com/

I wrote a note on making a polarimeter out of blue sky and water, and also thought of a polarization clock to hang in a north/south-facing window. Here's a combination of both ideas.

http://www.sjolander.com/viking/essays/sunstone/psundial.htm

Thursday, July 21, 2005

Frederic William

Friedrich Wilhelm Herschel, better known as Sir William Herschel, is best known for discovering Uranus; however, he went to England to further his career as a musician.

His son, John Frederick William Herschel was even more famous as a scientist.

Friedrich Wilhelm Bessel was a great astronomer and mathematician. He was the first to demonstrate the parallax of a star; John Herschel said it was "the greatest and most glorious triumph which practical astronomy has ever witnessed."

This article tries to show something good about Friedrich Wilhem Nietzsche's philosophy.

Friedrich Wilhelm Murnau made the classic horror film Nosferatu (really Dracula) in 1922.

Frederic William Goudy was a prolific early typeface designer.

Frederick William MacMonnies' most famous sculpture is that of Nathan Hale.

Thursday, August 04, 2005

Sidewalk art

http://users.skynet.be/J.Beever/pave.htm

Saturday, August 13, 2005

Respirocytes

Dreaming about artificial red blood cells.

Sunday, August 14, 2005

Captain Nemo's Lightsaber

http://www.kropserkel.com/propguns.htm

Thursday, September 01, 2005

Wow.

Organ and limb regrowth in mice. Wow.

Wednesday, October 26, 2005

Mantis preys on hummingbirds

http://tinyurl.com/8nxtm

Thursday, October 27, 2005

Los Alamos Bug

Los Alamos' approach to creating life

Tuesday, November 22, 2005

Light saber

http://www.redferret.net/?p=5809

Friday, November 25, 2005

Colored Bubbles

The chemistry of the new Zubbles

Monday, December 05, 2005

Clayton Merrell

I looked at the reviews of Clay's work that my cousin Valerie sent a while ago and figured that Clay probably had some work online. Here are a few of the sites I found:

Clay's homepage: http://artscool.cfa.cmu.edu:16080/~merrell/index.html

Others:
http://www.rair.org/MarshellGallery-Merrell.htm http://www.larsonweb.com/art/merrell.htm http://www.larsonweb.com/art/merrell2.htm http://www.conceptgallery.com/merrellpentak.htm http://www.washingtoncountyarts.com/artistDetail.php?ID=22

I think this is really cool--Clay helped create a class for chemistry students and artists on the chemistry of pigments:
http://www.carnegiemellontoday.com/article.asp?Aid=254

LQG for non-experts

Ashtekar gives it a go: http://xxx.lanl.gov/PS_cache/gr-qc/pdf/0410/0410054.pdf

Wednesday, December 07, 2005

Physics News Update 757

From: physnews@aip.org <physnews@aip.org>
Date: Dec 7, 2005 8:51 AM
Subject: Physics News Update 757


PHYSICS NEWS UPDATE
The American Institute of Physics Bulletin of Physics News
Number 757  December 7, 2005  by Phillip F. Schewe, Ben Stein

THE TOP PHYSICS STORIES FOR 2005.  At the Relativistic Heavy Ion
Collider (RHIC) on Long Island, the four large detector groups
agreed, for the first time, on a consensus interpretation of several
year's worth of high-energy ion collisions: the fireball made in
these collisions---a sort of stand-in for the primordial universe
only a few microseconds after the big bang---was not a gas of weakly
interacting quarks and gluons as earlier expected, but something
more like a liquid of strongly interacting quarks and gluons
(www.aip.org/pnu/2005/split/728-1.html ).  Other top physics stories
for 2005 include, in general chronological order of their appearance
throughout the year, the following: the arrival of the Cassini
spacecraft at Saturn and the successful landing of the Huygens probe
on the moon Titan (http://www.aip.org/pnu/2005/split/716-1.html );
the development of lasing in silicon (Nature, 17 February); the
biggest burst of light ever recorded from outside the solar system,
from a soft gamma  repeater
(http://www.aip.org/pnu/2005/split/721-1.html ); further evidence
for superfluid behavior in a solid
( http://www.aip.org/pnu/2005/split/724-2.html ); detection of
infrared radiation directly from an exoplanet
(http://www.aip.org/pnu/2005/split/724-1.html ); zeptogram mass
sensitivity in a cantilever sensor
(http://www.aip.org/pnu/2005/split/725-1.html ); spashless impact of
droplets at low pressures
( http://www.aip.org/pnu/2005/split/725-3.html ); the demonstration
of pyrofusion, fusion reactions created with a pyroelectric crystal
( http://www.aip.org/pnu/2005/split/729-1.html ); the best yet
prediction of hadron masses using lattice QCD
(http://www.aip.org/pnu/2005/split/731-1.html ); the best
measurement yet of the weak nuclear force
(http://www.aip.org/pnu/2005/split/736-1.html ); superfluidity
directly observed in a sample of ultracold fermi atoms
(http://www.aip.org/pnu/2005/split/734-1.html ); extension of the
"comb" technique for measuring frequency (a topic pertaining to the
2005 Nobel prize in physics) into the ultraviolet
(http://www.aip.org/pnu/2005/split/735-2.html ); geoneutrinos
observed ( http://www.aip.org/pnu/2005/split/739-3.html ); hybrid
atom-molecule dark states
(http://www.aip.org/pnu/2005/split/744-1.html ); using statistical
mechanics to predict the effectiveness of flu vaccines
(http://www.aip.org/pnu/2005/split/724-3.html ); hydrophobic water
(http://www.aip.org/pnu/2005/split/747-2.html ); 2005 Nobel Prize
(http://www.aip.org/pnu/2005/split/748-1.html ); molecules that walk
(http://www.aip.org/pnu/2005/split/751-2.html ); phonon Hall effect
(http://www.aip.org/pnu/2005/split/750-1.html ); short gamma ray
bursts identified as coming from in-spiraling neutron stars (Nature
6 October); hyperentangled states
(http://www.aip.org/pnu/2005/split/754-1.html ); further progress in
research concerning left-handed or negative-refraction materials,
including perfect lensing (Science 22 April), almost perfect lensing
in the mid-infrared (http://www.aip.org/pnu/2005/split/750-3.html ),
and extension of negative-index behavior into the near-infrared
region (http://www.aip.org/pnu/2005/split/756-1.html).

FRACTAL-DOMINATED CHEMISTRY.  Why does cream poured into coffee
swirl the way it does?  A new study of how chemical reactions
proceed establishes new equations for reaction rates by taking
mixing abnormalities more into account.  Many existing equations
assume efficient mixing of ingredients, but this is far from the
case.  Before reactions can take place, proper mixing has to occur,
and as two Hungarian physicists now discover in their simulations of
mixing under more realistic fluid flow conditions, reactions often
occur along a fractal frontier.  Indeed, much real-world fluid
chemistry is chaotic in nature and takes place not in general
solution but along a many-filamented fractal surface. Some previous
studies of the steady time-independent fracticality of chemical
reactions occurring in open flows, those in which fluid continuously
flows into and out of a container.  According to Gyorgy Karolyi
(Budapest University of Technology and Economics) and Tamas Tel
(Eotvos University), their new study is the first to address the
tougher problem of a closed flow, one in which the fluid remains in
the container; in this case, the resultant filamentary fractal is
not steady but instead evolves through time, gradually filling up
more and more of the container volume.  They derive the relation
between reaction rate and fractal dimensionality (the extent to
which surface of the filaments lies between that of a two
dimensional and three dimensional object).  Fractal mixing is
suspected in the disposition of several natural systems, such as
plankton in the ocean, sea ice floating in the ocean, and cloud
patterns ( http://earthasart.gsfc.nasa.gov/vortices.html).  Karolyi
(karolyi@tas.me.bme.hu) suggests that the new equations might
provide new insights for those who design microfluidic devices such
as micromixers used in printing and medical equipment.  (Karolyi and
Tel, Physical Review Letters, upcoming article)

***********
PHYSICS NEWS UPDATE is a digest of physics news items arising
from physics meetings, physics journals, newspapers and
magazines, and other news sources.  It is provided free of charge
as a way of broadly disseminating information about physics and
physicists. For that reason, you are free to post it, if you like,
where others can read it, providing only that you credit AIP.
Physics News Update appears approximately once a week.

Friday, December 09, 2005

"Splash" from marble dropped into sand behaves like an ultracold gas

http://www.livescience.com/forcesofnature/051206_new_matter.html

Thursday, January 12, 2006

Green eggs and ham

http://news.bbc.co.uk/2/hi/asia-pacific/4605202.stm

Wednesday, January 25, 2006

Javascript OOP done right

http://mckoss.com/jscript/object.htm

Wednesday, February 08, 2006

Power-law vs Bell-curve: homeless, bad cops, etc.

http://www.newyorker.com/fact/content/articles/060213fa_fact

Thursday, February 09, 2006

Classic Kids' Books for Free

http://www.pagebypagebooks.com/

Friday, February 10, 2006

If Babbage had had Legos, ...

http://acarol.woz.org/

Dumb people don't know they're dumb

http://www.phule.net/mirrors/unskilled-and-unaware.html

Tuesday, February 14, 2006

Huge multi-touch screen does cool stuff

http://www.badacetechshow.com/video/multitouchreel.mpg

Wednesday, February 15, 2006

How to turn digital camera jpegs into a stop-action movie

http://howardtayler.livejournal.com/151112.html

Saturday, March 04, 2006

Electronics in the basement

While Dad fixed lots of toys, this is what he ought to do with all the stuff that descended into the basement and never came back:
http://www.casperelectronics.com/
 

Tuesday, March 07, 2006

(Re-)Constructed languages

Viginia Algonquin, for the movie Jamestown:
http://www.nytimes.com/2006/03/07/science/07lang.html?8hpib

Tuesday, March 14, 2006

Time

http://flickr.com/photos/ioerror/sets/1208905/

Tuesday, March 21, 2006

Exceptions in C

http://ldeniau.home.cern.ch/ldeniau/html/exception/exception.html

Thursday, April 06, 2006

Site that will be relevant to my thesis

http://thatlogicblog.blogspot.com/

Monday, July 17, 2006

Singing dune movies

http://www.lps.ens.fr/~douady/SongofDunesIndex.html

Monday, July 24, 2006

3D weaving, polyhedra, tensegrity, magnetostatics, & more

http://www.kennethsnelson.net/new_structure/structure1.htm

Origami Tesselations

http://www.origamitessellations.com/

Tuesday, August 22, 2006

CCCs and lambda calculus

I finally got it through my thick skull what the connection is between lambda theories and cartesian closed categories.

The lambda theory of a set has a single type, with no extra terms or axioms. This gives rise to a CCC where the objects are generated by products and exponentials of a distinguished object, the free CCC on one object. For example, from a type $X$ we generate objects $1, X, XX, (X^X)^{(X^X)} = X^{XX^X}$, etc. The morphisms are all the programs we can make out of the appropriately-typed S and K combinators. A product-exponential-preserving functor from this CCC to the category Set (which is also a CCC) picks out a set $S_X$ for $X$, and because it preserves the structure, maps the product $AB$ to $S_AS_B$ and the exponential $A^B$ to $S_A^{S_B}$. The functions on the sets have to satisfy beta-eta-equivalence.

The functor itself, however, can be uncomputable: one could have $S_X$ be the set of halting programs for some universal Turing machine. This set is only computably enumerable, not computable.

When we have types and axioms involved, then we add structure to the set, constraints that the sets and functions on them have to satisfy. For instance, in the lambda theory of groups, we have:
  • a type $G$
  • terms
    • $m:X\rightarrow X\rightarrow X$
    • $inv:X\rightarrow X$
    • $e:1\rightarrow X$
  • axioms for right- and left-unit laws, right-and left-inverses, and associativity, like \[m(\rho)=1_G=m(\lambda),\] where $\rho$ (resp. $\lambda$) are isomorphisms between $G$ and $G \times 1$ (resp. $1 \times G$).
The CCC arising from this theory has all the morphisms from the free CCC on one object and extra morphisms arising from products and compositions of the terms. A structure-preserving functor to Set assigns $G$ to a set and $m$, $inv$, and $e$ to functions satisfying the axioms. These functions needn't be computable, either—they only have to satisfy the group axioms.

So in terminology programmers are more familiar with, the terms and axioms define an abstract data type in C++, a Java interface. The functor gives a class implementing the interface. But this implementation doesn't need to be computable! Here's another example: we start with a lambda theory with a data type $N$, along with a term $succ:N\rightarrow N$ and the axioms of Peano arithmetic; a functor from this lambda theory to Set will give us an implementation of natural numbers. Now we add a term $f:N\rightarrow N$ to the theory, with no other constraints. One model of this theory is Peano arithmetic with an oracle to $\Omega$: it assigns $f$ to the function that returns the $n$th bit of the Omega number for a universal prefix-free Turing machine.

I think that in order to get a computable model, we have to use a "computability functor" (my term). If I'm right, this means that instead of taking a functor directly into Set, we have to take a functor into a CCC with no extra terms to get a "computable theory" (again, my term), and then another from there into Set. This way, since all the morphisms in the category arising from the computable theory are built out of S and K combinators, the functor has to pick an explicit program for the implementation, not just an arbitrary function. From there, whether the implementation of the S and K combinators is computable or not really doesn't matter; we can't get at anything uncomputable from within the language.

Now, changing gears and looking at the "programs as proofs" aspect of all this: morphisms in the free CCC on one object are proofs in a minimal intuitionistic logic, where \rightarrow now means implication rather than exponentiation. The only two axioms are the ones from S and K. Adding a term of a given type to the theory adds a new axiom to the logic, while adding an axiom to the theory defines an equivalence of proofs in the logic.

A computable theory wouldn't add any axioms, just assign names to proofs so they can be called as subproofs. And because the programs already satisfy the axioms of the computable theory, asserting the equivalence of two proofs is redundant: they're already equivalent.

Quantum lambda calculus, symmetric monoidal closed categories, and TQFTs

The last post was all about stuff that's already known. I'll be working in my thesis on describing the syntax of what I'll call simply-typed quantum lambda calculus. Symmetric monoidal closed categories (SMCCs) are a generalization of CCCs; they have tensor products instead of products. One of the immediate effects is the lack of built-in projection morphisms $\pi_1$ and $\pi_2$ for extracting the first and second element of a pair. And without these, there's no duplication morphism $\Delta :A\rightarrow A\otimes A$; morphisms of this type can exist, but there's no way to express the notion that it should make a copy of the input! The no-cloning theorem is built in.

The typical CCC in which models of a lambda theory are interpreted is Set. The typical SMCC in which models of a quantum lambda theory will be interpreted is Hilb, the category of Hilbert spaces and linear transformations between them. Models of lambda theories correspond to functors from the CCC arising from the theory into Set. Similarly, models of a quantum lambda theory should be functors from a SMCC to Hilb.

Two-dimensional topological quantum field theories (TQFTs) are close to being a model of a quantum lambda theory, but not quite.

There's a simpler syntax than the simply-typed lambda calculus, called universal algebra, in which one writes algebraic theories. These give rise to categories with finite products (no exponentials), and product-preserving functors from these categories to Set pick out sets with the given structure. There's an algebraic theory of groups, and the functors pick out sets with functions that behave like unit, inverse, and multiplication. So our "programs" consist solely of operations on our data type.

TQFTs are functors from 2Cob, the theory of a commutative Frobenius algebra, to Hilb. We can look at 2Cob as defining a data type and a TQFT as a quantum implementation of the type. When we take the free SMCC over 2Cob, we ought to get a full-fledged quantum programming language with a commutative Frobenius algebra data type. A TQFT would be part of the implementation of the language.

(There's a big discussion about all this here.)

Thursday, August 31, 2006

Another publication

My paper "Bit Commitment Blues" was accepted for publication in the Journal of Craptology!