Update 2014: The following design is different from and not related to the "storj project" that also exists within the crypto-currency community.
StorJ (pronounced Storage)
Consider a simple drop-box style file service with pay per use via bitcoin. (perhaps with naming provided via namecoin and/or tor hidden services)
Want to share a file? Send at least enough coin to pay for 24 hours of hosting and one download then send the file. Every day of storage and every byte transferred counts against the balance and when the balance becomes negative no downloads are allowed. If it stays negative too long the file is deleted. Anyone can pay to keep a file online.
(Additional services like escrow can also easily be offered, but that's not the point of this document)
Well engineered, a simple site like this provides a service which requires no maintenance and is always in demand.
Many hosting services are coming online that accept bitcoin, they all have electronic interfaces to provision and pay for services. Some even have nice APIs.
An instance of the site could be programmed to automatically spawn another instance of itself on another hosting service, automatically paid for out of its revenue. If the new site is successful it could use its earnings to propagate further. Because instances adapt their pricing models based on their operating costs, some would be more competitive than others.
By reproducing it improves availability and expands capacity.
StorJ instances can purchase other resources that it needs: it can use APIs to talk to namecoin exchanges in order to buy namecoin for conversion into DNS names, or purchase graphic design via bitcoin gateways to mechanical turk. (Through A/B testing it can measure the effectiveness of a design without actually understanding it itself).
StorJ instances could also purchase advertising for itself. (though the limited number of bitcoin friendly ad networks makes this hard right now)
StorJ is not able to find new hosting environments on its own, due to a lack of sufficiently powerful AI— but it can purchase the knowledge from humans: When an instance of StorJ is ready to reproduce it can announce a request for proposal: Who will make the best offer for a script that tells it how to load itself onto a new hosting environment and tells it all the things it needs to know how to survive on its own there? Each offer is a proposed investment: The offerer puts up the complete cost of spawning a new instance and then some: StorJ isn't smart enough to judge bad proposals on its own— instead it forms agreements that make it unprofitable to cheat.
When a new instance is spawned on an untested service StorJ pays only the minimum required to get it started and then runs a battery of tests to make sure that its child is correctly operating.
Assuming that it passes it starts directing customers to the new instance and the child pays a share of its profits: First it proxies them, so it can observe the behavior, later it directs it outright. If the child fails to pay, or the customers complain, StorJ-parent uses its access to terminate the child and it keeps the funds for itself. When the child had operated enough to prove itself, storj pays the offerer back his investment with interest, it keeps some for itself, and hands over control of the child to the child. The child is now a full adult.
The benefit the human receives over simply starting his own file sharing service is the referrals that the StorJ parent can generate. The human's contribution is the new knowledge of where to grow an instance and the startup funds. In addition to the referral benefit— the hands off relationship may make funding a StorJ child a time-efficient way for someone to invest.
At the point of spawning a child StorJ may choose to accept new code— not just scripts for spawning a child but new application code— this code can be tested in simulation, and certain invariants could be guaranteed by the design (e.g. an immutable accounting process may make it hard for the service to steal), but it's very hard to prevent the simulated code from knowing it is simulation and thus behaving. Still, a storj-parent has fairly little to lose if a non-clone child has been maliciously modified. The strategy of traffic redirection may differ for clone children (who are more trusted to behave correctly) than for mutant children.
By accumulating mutations over time, and through limited automatic adaptability StorJ could evolve and improve, without any true ability for an instance to directly improve itself.
StorJ instances can barter with each other to establish redundant storage or to allow less popular StorJ instances with cheaper hosting to act as CDN/proxies for more popular instances in relationships which are profitable both.
If an instance loses the ability to communicate with its hosting environment (e.g. due to API changes that it can't adapt to) it may spawn clone children on new services with the intention of copying itself outright and allow in the instance to fail. During this operation it would copy its wallets and all data over, so care must be taken to chose only new hosts which have proven to be trustworthy (judged by long surviving children) to avoid the risk of its wallet being stolen. It may decide to split itself several ways to reduce risk. It might also make cold backups of itself which only activate if the master dies.
Through this these activities an instance can be maintained for an indefinite period without any controlling human intervention. When StorJ interacts with people it does so as a peer, not as a tool.
The users and investors of a StorJ instance have legal rights which could be used to protect an instance from fraud and attack using the same infrastructure people and companies use. Being a harmed party is often enough to establish standing in civil litigation.
It's not hard to imagine StorJ instances being programmed to formally form a corporation to own its assets— even though doing so requires paper work it can easily be ordered through webforms. Then when spawning, it creates a subsidiary corporations first owned by the parents corp but then later technically owned by their users, but with a charter which substantially limits their authority— making the instance's autonomy both a technical and legal reality.
As described, StorJ would be the first digital lifeform deserving of the name.