Gilreath, William Fletcher
March 24, 2017
Church-Turing Thesis, computation model, computer architecture, computer organization, instruction set, instruction set completeness theorem, plural instruction set, processor architecture, one-instruction computer, one-instruction set computer
The Instruction Set Completeness Theorem is first formally defined and discussed in the seminal work on one-instruction set computing—the book Computer Architecture: A Minimalist Perspective.
Yet the original formalism of the Instruction Set Completeness Theorem did not provide a definitive, explicit mathematical proof of completeness, analyze both singular and plural instruction sets that were either complete or incomplete, nor examine the significance of the theorem to computer architecture instruction sets.
A mathematical proof of correctness shows the equivalence of the Instruction Set Completeness Theorem to a Turing machine, a hypothetical model of computation, and thereby establishes the mathematical truth of the Instruction Set Completeness Theorem. With a more detailed examination of the Instruction Set Completeness Theorem develops several surprising conclusions for both the instruction set completeness theorem, and the instruction sets for a computer architecture.