Turing Complete Alphanumeric x86 Instruction Set (Subset)

Question

I am looking to create a minimal, computationally universal subset of alphanumeric x86 opcodes. Eventually I want the subset to contain as few instructions as possible, and if there are multiple minimal subsets I want to know that as well. The subset should be able to simulate any program that could be written with the entire set of alphanumeric instructions. Instructions should only cover the instructions that correspond to the characters "A-Z", "a-z", and "0-9".

So far I think that a push, pop, inc, dec, cmp, and je would suffice, but I'm sure there is a smaller set. How could I go about proving that a set I generate is able to simulate any program using all of the alphanumeric instructions? How could I prove that such a set is minimal? Does anyone know if such an instruction subset exists?

Answer 1

I’m not sure I get your question, especially the part about “alphanumeric”, but I’d like to point out that it is well known that both mov and xor are Turing complete.