Algorithmic (aka Automatic) Differentiation is a wonderful technique for numerical computation of derivatives. I understand how it relates to the fact that we know how to deal with every elementary operation in a computer program, but I am not sure to get how this applies to every computer program.
To quote from this wikipedia page:
every computer program, no matter how complicated, executes a sequence of elementary arithmetic operations
.. which I totally agree with. However, it sounds then that the number $m$ of variables newly produced from any $n$ initial input is fixed and can be determined from static code analysis. But this is not straightforward to me since constructs like:
if x_1 > x_2: # branching
perform 4 elementary operations
else:
perform 84 elementary operations
endif
and:
while x_1 < x_2: # looping
perform 2 elementary operations
endwhile
do exist in so-called « complicated » computer programs. This make the number (and the type) of elementary operations not straightforward to compute in advance. And I even suspect it is impossible to gess that in general, right?
Does AD support such branching and looping programs?
Are there extensions of AD adapted to programs that are not just intricate closed-form expressions?
How does AD deal with Turing-completeness?