[awei]

But is it maybe the difference between complicated, which indecipherable definitely is, and complex, in the sense of composed of many things?

[immibis]

You don't think a pure functional program can be composed of many things?

[awei]

Right, a pure functional program can be composed of many things, so it can be complex even without side effects. Only a program with side effects is necessarily complex, as it includes at least two components if not more. Another interesting thought is that you can always encapsulate a purely functional program in a black box with an input and an output. Doing so with a program with side effects that themselves might be programs with side effects and their own interface is probably much more difficult.