There are a number of different theories of free will (R. Jones, 2002 annual meeting of the Kansas Academy of Science, Fort Hays State University):
Theory #1: Free will is a self-contradictory notion (Richard Double).
Theory #2: Free will, though conceivable, doesn't exist (Marvin Minsky).
#3: Some behavior randomization is used in order to make us unpredictable to adversaries/predators/competitors.
#4: "Free will" is simply a denial that CERTAIN SPECIFIC sorts of influences were operating.
#5: Cognitive system nonlinearity allows multiple responses to identical external stimuli.
#6: Decisions are based on history/path dependent (and approximate) processes.
#7: Different decisions can result under identical conditions if the agent deliberates for different lengths of time. ("Delay libertarian theory." "Anytime algorithms.")
#8: Quantum mechanics makes it impossible for the same decision to be made again under exactly identical conditions.
#9: An agent (using genetic algorithm or other unpatterned generator) creates rules for how it should decide on actions and tests them in its daily life. Such a random algorithm could just as well have created different rules. (We are most free when we are creative, doing something truly original/unique.)
#10: Everett-like multiple worlds, your decision determines which world you enter. (A strong "free will" requires extreme assumptions about physics.)
With our current knowledge I do not see how a strong free will (like that assumed in religion and the justice system) is possible. On the other hand, a weak free will (like #3 above, for instance) is certainly reasonable.
I think what passes for free will in humans is a combination of a number of processes like #4, #5, #6, #7, #8, and #9 above. Complex machines would be subject to the same principles.