As discussed here we now know that what are the traits for telling if a language is functional or not. But where does the immutability fits into this scenario?
Here's a quick mental exercise, in pseudo-code:
1) x = 5;
2) x = x + 1;
3) print x; // prints "6"
4) x = x
// THEREFORE 5 = 6
Right? We know x is 5 from line 1, and we know x is 6 from line 3, so if x = x, then 5 must equal 6.
The joke here is that we're mixing imperative, command-oriented thinking with mathematical, functional thinking. In imperative style, x is a variable, which means we assume its value potentially changes over time. But when we do math, we make a different assumption: we assume "x" is a specific value, meaning that once we know the value of "x", we can substitute that value anywhere "x" appears. That assumption is the whole basis for being able to solve equations. Obviously, if the value of "x" were to change out from under us, like it does in line 2 of the mental exercise above, then all bets are off. Line 2 is not valid math, because there is no value for which the statement x = x + 1 is mathematically true. (At least as far as I ever learned in high school math!)
Another way of looking at it is to say that imperative programming mixes values, functions, and state, which makes it hard to reason about. Because the value of "x" can be different depending on when you look at it, you can't easily know what effect it's going to have on how your code runs, just by looking at your code. You have to "play compiler" and mentally keep track of all the variables and how they're changing over time, and that quickly gets unmanageable. State is the number one source of incidental complexity in computer programming.
Functional programming simplifies things by separating state from function. In a mathematical function like f(x) = (x * x), the value of "x" does not change over time. It's a pure description of the relationship between "x" and "f(x)", and that relationship is always true whether you look at "x" first or "f(x)" first. There's no state involved. You're describing the relationship between values, irrespective of time, and without any state. And because you don't have to worry about state changing out from under you, you can more easily and safely reason about the relationship between your inputs and outputs.
Immutable variables simulate this kind of stateless, mathematical reasoning by removing the element of time and variable-ness from your code. You still need to mutate your state at some point, but you can put that off until later, and only update state after your pure functions have worked out the correct values to store. By separating state management from your pure functions, you make coding simpler, easier to reason about, and usually more reliable. Plus it's a lot easier to test pure functions because there's no need for mocks or extra setup or other state-simulation prerequisites.
What's really cool in all this is that the same holds true even when "x" is something more complex that just a simple number. You can write pure functions whose arguments are arrays, records, Customer objects, etc, and the same principles still apply. By keeping your functions pure and your values immutable, you're writing code that describes the relationships between the function argument(s) and the function output, without the incidental complexity of time and state. And that's huge.