So I had a thought about elements turing completeness, and I posted it in the simple questions thread.
The idea behind turing completeness is that it can compute anything a turing machine can. The most powerful computation model we have is the turing machine, so basically it can compute anything that can be computed (which is not every problem). MTG is turing complete.
So could ETG be made turing complete with CIA card ideas?
First, the tape: There are very few things in EtG that are theoretically infinite. The only things that don't have clear bounds are permanent stacks, poison/purify counters, SoSac counters, and decks. I suggest using the decks for the tape. Moving left through the tape would be represented by drawing a card from your deck, putting it in a head area, and putting the current head card in the opponents deck. Vice versa for moving the head the other way.
Second, making sure the thing doesn't come to a halt: This is not the tricky part. The tricky part comes later. Anyway, my current thoughts are to use a creature that forces other creatures to use their skills, paired with a load of trusts, to make a system where all the creatures are forced to use their abilities. The self-sustaining comes from the skill-forcing creatures using their skills on each other ad infinitum.