Author:
Gilreath, William Fletcher
Category:
Research Papers
Sub-Category:
Miscellaneous
Date Published:
March 24, 2017
Keywords:
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
Abstract:
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.
<<< Back