Isn't this trivial? Since AND and NOT can together be composed to represent any logic function, and a logic function can be interpreted as a function from some number of bits (the truth values of the variable propositions) to one result bit, it follows that we can write programs with AND and NOT that make any bits in our computer an arbitrary function of any of the other bits. Is there some complication I'm missing?

You can use NAND to implement any algorithm that has a finite upper time bound, but not "any computer program", since a logical formula can't express recursion.