All of your logic is sound, except that I think your understanding of functional programming is a bit too extreme. In the real world functional programming, just like object-oriented, or imperative programming is about mindset and how you approach the problem. You can still write programs in the spirit of functional programming while modifying application state.
In fact, you have to modify application state to actually do anything. The Haskell guys will tell you their programs are 'pure' because they wrap all of their state changes in a monad. However, their programs still do interact with the outside world. (Otherwise what is the point!)
Functional programming emphasis "no side effects" when it makes sense. However, to do real-world programming, like you said, you do need to modify the state of the world. (For example, responding to events, writing to disk, and so on.)
For more information on asynchronous programming in functional languages, I strongly urge you to look into F#'s Asynchronous Workflows programming model. It allows you to write functional programs while hiding all the messy details of thread transition within a library. (In a manner very similar to Haskell style monads.)
If the 'body' of the thread simply computes a value, then spawning multiple threads and having them compute values in parallel is still within the functional paradigm.
Exactly. See case class method copy, or the general concept of lenses.
In particular, if state needs changing, you'd use a State monad. Changes to that state monad can be made through lenses, which makes extracting information from "state" and changing it easy.
See also this question about the general problem that comes from a deep structure like "state" and making changes to it. The answers have good links on both lenses and zippers if you want to get deeper into that.
Best Answer
It's not a question of "smart enough". This is called Purity Analysis and is provably impossible in the general case: it is equivalent to solving the Halting Problem.
Now, of course, optimizers do provably impossible things all the time, "provably impossible in the general case" doesn't mean that it never works, it only means that it cannot work in all cases. So, there are in fact algorithms to check whether a function is pure or not, it's just that more often than not the result will be "I don't know", which means that for reasons of safety and correctness, you need to assume that this particular function might be impure.
And even in the cases where it does work, the algorithms are complex and expensive.
So, that is Problem #1: it only works for special cases.
Problem #2: Libraries. In order for a function to be pure, it can only ever call pure functions (and those functions can only call pure functions, and so on and so forth). Javac obviously only knows about Java, and it only knows about code it can see. So, if your function calls a function in another compilation unit, you cannot know whether it is pure or not. If it calls a function written in another language, you can't know. If it calls a function in a library which might not even be installed yet, you can't know. And so on.
This only works, when you have whole-program analysis, when the entire program is written in the same language, and all is compiled at once in one go. You can't use any libraries.
Problem #3: Scheduling. Once you have figured out which parts are pure, you still have to schedule them to separate threads. Or not. Starting and stopping threads is very expensive (especially in Java). Even if you keep a thread pool and don't start or stop them, thread context switching is also expensive. You need to be sure that the computation will run significantly longer than the time it takes to schedule and context switch, otherwise you will lose performance, not gain it.
As you probably guessed by now, figuring out how long a computation will take is provably impossible in the general case (we cannot even figure out whether it will take a finite amount of time, let alone how much time) and hard and expensive even in the special case.
Aside: Javac and optimizations. Note that most implementations of javac don't actually perform many optimizations. Oracle's implementation of javac, for example, relies on the underlying execution engine to do optimizations. This leads to another set of problems: say, javac decided that a particular function is pure and it is expensive enough, and so it compiles it to be executed on a different thread. Then, the platform's optimizer (for example, the HotSpot C2 JIT compiler) comes along and optimizes the entire function away. Now, you have an empty thread doing nothing. Or, imagine, again, javac decides to schedule a function on a different thread, and the platform optimizer could optimize it away completely, except it cannot perform inlining across thread boundaries, and so a function that could be optimized away completely is now needlessly executed.
So, doing something like this only really makes sense if you have a single compiler making most of the optimizations in one go, so that the compiler knows about and can exploit all the different optimizations at different levels and their interactions with each other.
Note that, for example, the HotSpot C2 JIT compiler actually does perform some auto-vectorization, which is also a form of auto-parallelization.