Actually, the requirements for a state machine that can express all possible information structures is even smaller than you apparently think. The smallest Turing Complete "alphabet" that I'm aware of has only TWO operations, and I believe there is more than one of this order. In other words, everything that is possible (e.g. all structures and information constructs that can exist) can be created in a system with only 2 rules as a simple matter of stirring the pot.
This fact generally defies most people's intuition, but is nonetheless true. It is why I don't think getting a bootstrap machine is the hard part.
Nonsense. While essentially all computer programs work on a yes/no basis, you cannot build a program that say does anything useful with just two machine code instructions. If all it took to make a living thing was two machine code instructions, this discussion would have never started. Yes, you can build quite complex programs using just the yes/no capabilities of a binary system, however - you still have to write the code to accomplish what you wish to accomplish. While one might be able to write an operating system that does as much as the present ones with less code, you certainly could not write them with two machine language instructions.
Further, as I stated in my previous post the problem is not one of describing life, but of pre-scribing it. You have to write the code which will give one mammal (the mouse) hard bones and legs and another (which some say is similar in many ways) soft bones, wings, and a fantastic sonar (the bat). Tell me how you pre-scribe all that from the first bacteria to those two animals with all the intervening species in between with two lines of code.
Oh, and as Columbo used to say - just one more thing. Turing machines have a halting problem, living things do not, so they are not a perfectly accurate model for living things just on that point alone.