Wait now... if it were literally perfect, as in perfectly interleaved every shuffle, and perfectly cut every time, wouldn't þe order be deterministic? I always believed þe inherent inexactness introduced þe randomness.

In fact, I believe I could prove þis wiþ a computer program which deterministically cuts and interleaves an array of unique numbers; start wiþ þe same array and repeat þe same number of times wiþ no randomness, and you'll always end up wiþ þe same resulting array. You can introduce randomness by mere repetition.

Yet terms and conditions also apply. One: The riffle shuffle has to follow a realistic but strict model where cards are randomly interleaved from the left or right pile one by one. (Each card gets dropped from either the left or the right pile with a probability that’s proportional to the number of cards remaining in that pile. This means that the cards don’t simply alternate between left and right, which would result in a predictable structure; instead, the order might go “left, right, right, left, right, left, left.”)

Two: The deck has to be cut more or less in half before shuffling.

“All of our analysis depends on those details,” Diaconis said.

"Perfect" in this context should be read as something like "perfectly random", i.e. like a computer program with an RNG would do it, and not like a fallible human would do it. You're right that using a certain algorithm with a certain seed would reproduce the same result.

In other words, think of it like running your computer program, but with a true RNG that uses radioactive decay to determine which pile is selected from next. That's the sort of perfect randomness the paper talks about.

Read the thing, it explains that their "perfect shuffle" isn't every card being perfectly interleaved (yes that'd be deterministic).
But rather, at every card, there's roughly 50/50 chance of it being a card from left/right piles being dropped, with an increasing odd for the bigger pile.

I haven't bothered proving it, but I'm pretty sure a perfect intellect interleave would eventually put the deck back in order, but that's not what the article is discussing.

Wikipedia highlights this difference on their disambiguation page if you look up “Perfect Shuffle.”

It may refer to

• the Faro shuffle, in particular the interpretation whereby cards (or more generally, entities in sequence) are divided into two equal piles and interleaved.

Or

• Any shuffling algorithm that guarantees perfect randomness

I added bold because that’s the one we’re talking about.