We have a perfect example of life on earth. This life, made up of DNA, has a physical existence due to molecules and structures which compose it. But, is physical existence a prerequisite of life? Can life exist as information only with no physical basis?
The answer to the question lies in our viewpoint. If we take life as an exclusive property of earth, then yes of course, life must have physical existence. But, if we consider to be a universal property (as much as gravity), then we can have interesting life forms (majority of which we may never detect).
The article TESTING DARWIN rekindled my interest in digital life. It is a form of life in which entities live solely as information. This kind of life can easily be implemented on a computer and an excellent example of this implementation is Avida. The basic premise is that the principles of evolution/life are universal and are not necessarily be restricted to earth-based life.
Avida is a system in which digital organisms (computer programs) compete with each other for computer resources. This is similar to competition between organisms for limited resources available in the environment. All the properties of life: adaptation, species, natural selection, etc. can be observed in Avida. I guess, it is a perfect tool for one to observe life’s struggle easily at home.
In the article I mentioned, the author draws parallel between the DNA based life and the digital organisms of Avida. Since, Avida can provide huge amounts of data in no time, we may easily study various aspects of life without having to wait for ages. He tries to answer few of the mysteries of life such as: Evolution of sex, co-operation, irreducible complexity, extra-terrestial life, etc.
P.S: My personal opinion is that life is what you describe and there is no reason why we should not consider strings of bit (which evolve) as entities of life.