When it has spontaneous feelings that aren't pre-programmed into it, I expect. Also, when it displays creativity and the ability to literally create mathematic algorithms, not just regurgitate what it's been programmed to know/learn.
Generally, though, I fall along the line of Naskapi thought. Naskapi beliefs are such that the entire world is full of soul, so everything, animate and inanimate, are enshrined with spirit.
This is not without backing. Everything physical is made out of light. Light has been shown, in studies ("The Double-Slit Experiment"...and I checked with my Astronomy teacher [Astronomy relies heavily on physics]; the study has held up since it was done and has even been backed by others), to have...they hesitate to call it "consciousness" or "sentiency", but at least some form of awareness, an intra-photon instantaneous communication telling it where to go when presented with a choice. Light, we also now, is infinite.
So if we believe that the soul is an immortal animating force aware of what its accompanying body is doing, then everything already has a soul simply by virtue of being made out of light. Think about that the next time you slam a door ;)
Music: "Wonder" from the Lord of the Rings musical
