Earlier quoted context omitted.
I think you can define it. You just need to be willing to pin down some definitions so there's something you can formally talk about. For example, let's say an "program" (in whatever abstract sense, whether you want to represent it as DAGs of function compositions or as a sequence of instructions or whatever else) takes, by definition, an infinite sequence of input symbols, and produces an infinite sequence of output…
I don't think that captures the aspects people care about most of the "program state" that people care about is unrelated to I/O - particularly in Haskell, people care about programs that are essentially "evaluate this large equation" where there's only one piece of output at the end, but might be a lot of intermediate computation. And the details of what's stored in memory aren't what matters - after all, Haskell ve…
The thing is though, the fact that you don't doesn't imply state is meaningless or useless. After all, you're still going to face the fundamental limits on computation that are out there, regardless of the model of computation. It's not like switching to Haskell and beta-reductions suddenly lets you solve every problem instantaneously, right? You're still going to have just as hard of a time (if not harder!) solving a problem like TSP efficiently in Haskell, as you would in Python or Prolog.
Look at it this way: the only reason you wouldn't "care" about state would be that you already know how things are going to turn out, not because the whole notion is itself meaningless. If tomorrow you wrote a Haskell program that factored integers in time & space linear to the input size, you wouldn't toss it into the trash thinking "whatever, time and space are meaningless concepts in FP". You'd absolutely care. Not only would you care, but you'd safely assume everyone else would too. You'd either find a way to profit off those results, or you'd publish them with formal definitions and tell everyone and their grandmother how awesome and meaningful they are. You'd find them as far from meaningless as anything could be. Of course, you're probably not going to get that lucky, but your lack of luck or care for the concepts doesn't render the concepts themselves meaningless.