Theory of computation and computing machines
- UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
- Cecil Seigler Carpenter (Creator)
- Institution
- The University of North Carolina at Greensboro (UNCG )
- Web Site: http://library.uncg.edu/
- Advisor
- Michael Willett
Abstract: At the turn of the century, David Hilbert, a famous mathematician and leader of the formalist school, was convinced of the existence of an algorithm for establishing the consistency or inconsistency of any mathematical system. Kurt Gödel [2] showed in 1931 that the consistency of any system which included the natural numbers could not be established. This result was a corollary to his more startling "incompleteness theorem" which states that if any formal system which contains the natural numbers is consistent, then that system is necessarily incomplete. More directly, there is a statement P in the system such that neither P nor not-P is a theorem of the system. Since either P or not-P must be true, then there is a true statement in the theory which is not provable. Thus the algorithm which Hilbert believed existed, in fact did not exist. The formal notion of algorithm - or "effective" procedure as it is often called - had concerned mathematicians before the result of Godel. How was an algorithm to be defined? When an algorithm was constructed, could it be determined whether or not it was meaningful? These and other questions now appeared more ominous than ever. Logicians turned their efforts toward establishing some type of approach which would enable them to categorize those procedures which were meaningful as opposed to those which were not.
Theory of computation and computing machines
PDF (Portable Document Format)
3613 KB
Created on 1/1/1974
Views: 146
Additional Information
- Publication
- Thesis
- Language: English
- Date: 1974
- Subjects
- Computers
- Computable functions
- Algorithms