This is kind of nitpicky, but I'll say it anyway.

An algorithm that does the same thing given the same input is deterministic aka referentially transparent aka pure, not stateless.

Even this little snippet of Haskell is stateful:

    statefulFunction :: Int -> Int
    statefulFunction x =
        let y = x * x
        y + y

The binding 'y' is state. Even if it's implicit, as in ((x * x) + (x * x)), it's still state.

People seem to use "stateless" as a word for "doesn't mutate anything", which is kind of weird. Mutability has _nothing_ to do with having state.