All environments are stateful, by necessity. A stateless system would have no input, no output, and consume no electricity. How much the programming requires thinking about that state is one technical dimension.
Abstract algorithms given in computer science could meet that condition, so long as they're defined on a turing machine.
Eg., you could have a gravitationally stable solar system whose planets, etc. you identified with terms (etc.) and observe that the whole thing runs at zero-energy.
This distinguishes abstract algorithms, which are just restatements of mathematics, from "programs" which are algorithms defined for electrical devices with relevant useful capacities.
Yes, I meant the latter, the actual execution. Kevlin Henney puts it well in his talks (paraphrase):
"Functional programming is great! You don't need to worry about the outside environment, it just works! Why, even if you unplug the computer, it just works—no, wait. These are all abstractions."
The execution environment is the invariant the webpage starts out with. The programming environment, and its relation to state, can be changed.
A 7400 NAND gate has no state, but it has inputs and outputs and consumes electricity to do useful work. Using lots of them you can build quite non-trivial systems.
