New submitter mkwan writes "The open-source X Server for Android has hit beta and is now available for download through the Android Market. On Australian networks at least, smartphones are assigned publicly-accessible IP addresses, so it should be possible to display many Linux applications on an Android smartphone simply by setting the DISPLAY environment variable to the phone's IP address followed by :0"
The source is available under the MIT license
(or Apache; the project page and story disagree) over at Google Code. It doesn't support all of the X protocol and there's no Xlib implementation (i.e. no X11 apps on the device yet except via the NDK if you're lucky), but it is
a reimplementation of the X server in Java for Android. You can run remote applications at least.