Exploring an information-based approach to computation and computational complexity

ABSTRACT

We present the background and justification for a new approach to studying computation and computational complexity. We focus on categories of problems and categories of solutions which provide the logical definition on which to base an algorithm. Computational capability is introduced via a formalization of computation termed a model of computation. The concept of algorithm is formalized using the methods of Traub, Wasilkowski and Woźniakowski, from which we can formalize the differences between deterministic, non-deterministic, and heuristic algorithms. Finally, we introduce our measure of complexity: the Hartley entropy measure. We provide many examples to amplify the concepts introduced.

REFERENCES

• 1: H. P. Barendregt. Lambda Calculus: Syntax and Semantics, volume 103 of Studies in Logic and the Foundations of Mathematics. North Holland, 1981.
• 2: Carl B. Boyer. A History of Mathematics. Wiley, 1989.
• 3: Leon Brillouin. Science and Information Theory. Academic Press, 1962.
• 4: Gregory J. Chaitin. Algorithmic information theory. IBM J. of R & D, pages 350--359, 496, 1977. Reprinted in Information, Randomness, and Incompleteness.
• 5: Edsger W. Dijkstra , Carel S. Scholten, Predicate calculus and program semantics, Springer-Verlag New York, Inc., New York, NY, 1990
• 6: H. Ehrig , H. Herrlich , Hans-Jörg Kreowski , Gerhard Preuss, Categorical methods in computer science with aspects from topology, Springer-Verlag New York, Inc., New York, NY, 1989
• 7: Richard P. Feynman. The Character of Natural Law. MIT Press, 1965. QC28.F5 1968.
• 8: B. Roy Frieden. Physics from Fisher Information. Cambridge University Press, 1999.
• 9: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 10: R. Goldblatt. Topoi: The Categorical Analysis of Logic. North-Holland, New York, 1984.
• 11: Soloman Goldman. Information Theory. Prentice-Hall, 1953.
• 12: Silviu Guiaşu. Information Theory with Applications. McGraw-Hill, 1977.
• 13: Carl A. Gunter, Semantics of programming languages: structures and techniques, MIT Press, Cambridge, MA, 1992
• 14: R. V. L. Hartley. Transmission of information. Bell Sys. Tech. J., pages 535--563, 1928.
• 15: Fred C. Hennie, Introduction to Computability, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 16: C. A. R. Hoare and P. E. Lauer. Consistent and complementary formal theories of semantics in programming languages. Acta Informatica, 3:135--153, 1974.
• 17: Morris Kline. Mathematical Thought from Ancient to Modern Times. Oxford University Press, 1972.
• 18: Morris Kline. Mathematics: The loss of certainty. Oxford University Press, 1980.
• 19: A. N. Kolmogoroff. Exact title unknown at this time. Problems of Information Transmission, pages 1--7, 1900.
• 20: Soloman Kullback. Information and Statistics. Wiley, 1959.
• 21: Charles Perrow. Normal Accidents. Basic Books, 1984.
• 22: G. M. Reed , A. W. Roscoe , R. F. Wachter, Topology and category theory in computer science, Oxford University Press, Inc., New York, NY, 1991
• 23: H. L. Royden. Real Analysis. MacMillan, 2 edition, 1968.
• 24: R. J. Salmonoff. A title. Information and Control, pages 1--22, 224--254, 1964.
• 25: D. A. Schmidt. Denotational Semantics. Allyn and Bacon, 1986.
• 26: Claude E. Shannon , Warren Weaver, A Mathematical Theory of Communication, University of Illinois Press, Champaign, IL, 1963
• 27: Leo Szilard. On the decrease of entropy in a thermodynamic system by the intervention of intelligent beings. In John. Archibald Wheeler and Wojciech Hubert Zurek, editors, Quantum Theory and Measurement, chapter Irreversibility and Quantum Theory, pages 539--548. Princeton University Press, 1983.
• 28: J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski. Information, Uncertainty, Complexity. Addison-Wesley, 1983.
• 29: D. van Dalen. Logic and structure. Springer-Verlag, 1994.
• 30: Walter P. van Stigt. Brouwer's Intuitionism, chapter 2--4. Elsevier Science Publishing Company, Inc., 1990. QA29.B697S25.
• 31: Gordon J. Van Wylen and Richard E. Sonntag. Fundamentals of Classical Thermodynamics. John Wiley & Sons, 1985.