Just think of the word function for a moment, in an algebraic context. A function is a a relation (ie, a mapping from a set of things to another set of things) where each element of the domain maps to at most one element of the range. Now, the inverse does not hold: any given output might have several inputs that lead to it.
For example, f(x) = x^2 is a function because f(2) is always 4, no matter what end of story. f(-2) is also always 4, and that's okay.
In most languages where you use "functions" you can modify state as part of the function doing its thing. Modifying external state opens up the possibility that, if we are writing a function `func`, `func(A)` might somethings return B or sometimes return C. That violates the definition of a function.
This could happen if our `func` example mutates a variable that it relies on, alters a database, etc. If that variable, or that database, is used elsewhere in the program, you open the door for non-determinism. In other words, bringing in external state could very well mean that your function isn't a function at all, in a mathematical sense.
Sticking with mathematical functions means that your program is more deterministic. It means you can reason about the correctness of your program more easily. It means that you can write a series of reusable components which can be composed any which way without too much trouble, and thus refactoring and creating libraries is much easier.
Only at the "edge" of your program, where it absolutely must mutate the outside world in some way, should you violate this.