Here I am discussing hypothetical (primarily) medical application nano-robots of approximately the size of a human blood cell(57-101 cubic nanometers). There would also be potentially various industrial uses.
Firstly we must realize that the very existence of life, particularly the CELL, is proof that such a highly complex nano-scale machine is theoretically both plausible and possible to construct. Even at this tiny scale, the cell, depending on what type it is, has locomotion, it has energy supplies, it has "programming" in the form of DNA, it has mitochondria, Ribosomes, the nucleous, transport mechanisms for water and electrons, etc. All of these are analogous in some way to systems we might expect to find in both a microscopic and macroscopic robot.
Now something I began to consider as I thought more and more about the concept of medical nano-robots is the idea that it would be very nice for the nano-robot to get its energy from the biology of the patient, rather than any sort of battery or whatever. While this technically makes them parasitic, they are designed for a very short lifetime and used only for simple diagnostics or specific cell, tissue, and organ repair, or for the killing of invading pathogens(virus, bacteria, cancerous cells, etc.)