> Combining pure functions to create pure functions does not introduce any state, in this sense.
Yes, but that's not the same as state in the TLA+ sense. You cannot have computation without state in the TLA+ sense, whether you call your functions pure or not. In TLA+, an algorithm that "purely" computes quicksort and one that outputs an interim result after each recursive step is the same algorithm. TLA+ doesn't talk about visible state, but state in the most fundamental way, without which there is no computation whatsoever.
In part 3 I ask whether Euclid's algorithm or Quicksort are imperative or pure-functional. There is no way to answer that question, as their descriptions are at an abstraction level above where this distinction can be made. TLA+ can work at that level. You just can't look at Euclid's algorithm (or quicksort) in TLA+, and tell whether it's imperative or functional. It's an abstract mathematical description.
> We have lambda calculus
Lambda calculus is a state machine (or, more precisely, it is naturally described as a state machine).
> You don't need a state machine to prove QuickSort works in a purely mathematical way, either, just statements about the equivalence of functions.
What you're calling state and what TLA+ calls state is not the same thing. Whichever way you prove Quicksort works is the way you'd do it in TLA+ with state. You just don't call it state. I would, however, be very much interested to see how you prove Quicksort works using category theory. AFAIK, all approaches to verify QS work the same way, using an inductive invariant, namely an invariant on state.
> that seemed to support the idea that FP and TLA+ have strengths for different kinds of programs
I was talking about synchronous programming languages inspired by TLA+, and I agree. I would rather write a compiler in a pure-functional language than in a synchronous one, and an interactive program in a synchronous language than a pure-functional one. But that is a separate discussion from that about mathematical reasoning. I would agree that if one day there would be a FP-based verification tool that is aimed at engineers rather than researchers, then for ergonomics/syntax reasons, it's possible that it would be more convenient for reasoning about compilers. But there's nothing in the theory of TLA+ that makes it less convenient.
I do, however, admit that there are tradeoffs between working in "pure math" as in TLA+, or within a programming language. There are often patterns that are specific to certain programming styles, and reasoning within a similar formalism may reduce effort. In other words, sometimes you may want to reason about a specific expression of an algorithm rather than about the algorithm in its pure abstract sense, and a formalism that shares the same expression style may make it easier. But I don't know how much of this is purely hypothetical. Most algorithms that are interesting or subtle, are essentially interesting or subtle, and verifying them in all formalisms is very similar (and usually involves the same proof technique: inductive invariants).