To answer it to my own satisfaction, I eventually arrived at a form of predicate logic so I could directly experience how cumbersome it was to try to express everything that way. I liken it to trying to speak in a language that lacks a definite article: doable, but way more verbose.
What you're describing are regular functions. If those functions hold a state, they're not functional; they're procedural. For example, a function that holds onto a counter and increments it by some value that is passed in cannot be functional because the counter exists in a hidden state, unknown to anyone else and unpredictable until runtime. This is what Backus was trying to fix.
A functional version of that same function would need two parameters, one for the amount to increment by and a second one for the counter's current value. Often, a function can be rewritten in the functional style and thereby eliminate state (at least from that function).
Whew!
> when your program is (tail-)recursive you can carry the "current" value along without ever really mutating it
main :: IO ()
main = loop (0 :: Int) where
loop n = do
putStrLn $ "The counter is currently " <> show n <> ". Increase it by how much?"
increase <- readLn
loop $ n + increase
The lambda calculus is a way to define math in the functional style. Guess what? It needs state passed in to work. The names and orders of the integers must be passed in and held in a "state" in order to do anything useful. Since functional programming is centered around the concepts from the lambda calculus, this implies that all functional programs must have some "state" somewhere in order to start or do useful work.
Only components or individual functions can be functional in style, the goal being to have as many of those as practical so that you don't touch state often and hopefully, only in a few places and using methods which set the state (rather than letting individual components "reach in" and set it themselves).