This is an important distinction, as I've found that the optimal strategies in Magic are very rarely the most intricate ones or the ones involving recursive constructs. Occasionally a trivial infinite loop becomes part of a top deck, but you definitely aren't going to see someone doing the equivalent of calculating pi to win.
I think the Turing completeness is definitely still part of the appeal of Magic, because the bizarre edge cases and complexity occasionally do creep in to even serious play and add a lot of interest, but the complexity is of the iceberg variety, where most of it rarely makes itself visible most of the time.