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

It's just ONE instruction! here the proof

http://en.wikipedia.org/wiki/One_instruction_set_computer

Why? Just because "instruction" is a machine-dependent concept. You cannot define a small set of instructions just because there are no such universal/absolute/atomic instructions: it all depends on the underlying hardware: In fact the "real" turing machine is a methematical concept (a set of rules) not a physical machine

Answer 2

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.