Everything in your machine runs on a CPU which loads and stores memory words, and performs comparisons and goto-like branches.
Functional programming means that mutation is hidden under the rug, not that it goes away.
It is not feasible, with current technology, for a functional language to be implemented purely all the way down. This is because you cannot keep allocating new hardware. Functional programs generate garbage as they execute, and the implementation has to identify the garbage and then reuse its storage for new objects. That is a form of mutation.
If this mutation is not done, then it means you do not serially re-use memory.
If you do not reuse memory, you have to keep getting new memory from somewhere.
Also, you are not allowed to restart the computer. You must use a new one.
Its CPU has to keep allocating new registers, because you can't load a new value into an existing register. Et cetera.
As you can see, functional programming is a silly pipe dream that is only made possible by the pragmatism of mutation.
There is inherent mutation in functional programming itself (in the abstraction). It's just conveniently ignored.
Fact is that when you construct a new object, the world has changed: there was no such object before, and there is now. Same thing when a new variable binding comes into life.
You can pretend that a whole new universe was allocated which is just like the old one, except for the difference that a new element now exists in it, but that's not reality. (If the old "world" was not mutated/destroyed by the creation of a new object, show me where that old one is.)
Also, in functional programs, object are destroyed all the time! Variable bindings (which are not captured in some closure) go out of scope, and objects fall out of the reachability graph (if there is no mutation, how can something be in a graph in one moment, and be not in that graph the next moment?)
You know that the old copy of the world is not being preserved, because those unreachable objects are stomped over to make new ones.
In other words, the destructiveness of functional programming reveals itself by the inability to revisit all past states of computation and inspect every object that was ever created.
How do imperative interpreters still make guarantees about the functional program they are executing without being inherently functional themselves?
-- By properly implementing the language specification. @pst is right: your compiler implementation does not have to be functionally pure to guarantee a fully functional language.