How to prove that work is done without actually knowing the payload Is there a way for an algorithm to run securely on one end, whilst the other end is able to be notified and also verify that it has run and done the work without knowing what the actual payload is?

For example, $A$ provides an algorithm that adds $1$ to any number.

$B$ takes this algorithm and performs it $N$ number of times. $A$ can then verify that $B$ has performed it $N$-times without knowing what $N$ is.
The answers to these questions depend heavily on the threat model.  Starting from the most pathological, and working our way back:


If the software has to be run on the remote machine, and $A$ cannot know anything about the data, and $B$ is willing to take full advantage of physical access to the remote machine, there's really nothing you can do.  Physical access is really hard to beat.
If $A$ can know a little of what $B$ needs, $A$ might be able to provide the algorithm encrypted in pieces, such that $B$ only gets enough of the algorithm to solve that one problem, but has to go back to $A$ to solve the next.  However, this requires knowing a little about $B$'s data and is very algorithm specific.
If the algorithm doesn't have to be run remotely, there's the relatively new field of homomorphic encryption.  This would let $A$ run the algorithm locally on an encrypted copy of $B$'s data without konwing anything about it.  However, this field is in its infancy, and practical examples are hard to find.
If we can reasonably trust $B$ to not reverse engineer the code, new options form.  At some point this trust becomes a legal question, which can get complicated.


In the last case, there is actually a solvable answer.  $B$ runs the program, which takes the inputs and outputs an encrypted form of the outputs (typically with asymmetric encryption).  This key is derived from the hash of all of the inputs.  This hash is then provided to $A$, who looks at that hash, and provides the correct decryption key.

It can also be done in the reverse order: $B$ hashes the inputs, $A$ looks at the hash, and signs them.  $B$ takes that signature and the inputs, and passes it into the algorithm, which confirms that the inputs are signed.