Magic is played by taking a card from the top of your pile and following the instructions on it, then your opponent does the same. In normal games the decks are shuffled, but for this to work you have to be able to program the order of the cards in both decks. In this paper they program the game by constructing the decks using a subset of cards that all have mandatory effects.

I think what they do is set up a sequence of cards that 'initialises' the game state with various creatures and resources. These together with the game rules form the Turing machine. Then they have a sequence of cards that correspond to the 'paper tape' of symbols a Turing machine operates on.