Communications of the ACM
Principles of Problem Solving
Our aim is to understand how to make the world a better place (despite worsening social and political actions) by exploring problem-solving principles in computer science and other disciplines. Changed modes of human thought are needed to match changes in the paradigm of computational problem solving caused by the Internet and other evolving forms of computing. We further explore the contrasting approaches of a priori rationalism and interactive empiricism in modeling new forms of computational technology that modify historical, philosophical, and mathematical forms of thought.
Problem solving carries different meanings in the domains of history and philosophy, along with a variety of interpretations in computer science. The word "problem" is defined in the Oxford English Dictionary as "a question proposed for solution or consideration" and in the Encyclopædia Britannica as "a kind of thinking that facilitates question answering." The concept of problem solving as a form of thinking that answers questions has been widely studied by many writers who believe that thinking is the primary mechanism for human understanding and improving the world.
However, this restriction of problem solving to thinking and question answering excludes interactive forms of problem solving that depend on the behavior of the world rather than on a priori human beliefs.
Mathematics was proposed by Pythagoras around 500 b.c. as a primary basis for problem solving. Political analysis of problem solving in Plato's Republic accepted and adapted Pythagorean principles, as did Aristotelian logic and Euclidean geometry. Mathematics was likewise a central feature of Newtonian physics and Cartesian philosophy, and continued to be central to modern science in the work of Einstein's relativity theory, Bohr's quantum theory, and Russell and Whitehead's Principia Mathematica.
Hilbert's assertion in 1900 that all mathematical theorems could be logically proved was widely supported by Russell and Whitehead but refuted by Gödel in 1930 and further disproved by Turing and Church in the mid-1930s. Turing's proof of the unsolvability of the halting problemby showing the impossibility of determining whether a given program will haltimplied computational unsolvability [4] and was acclaimed by Gödel and Church as a worthwhile extension of the limitations of problem solving from logical to computational models. The emergence of computer science from the 1930s to the 1950s focused on the role and status of problem solving in models of computation. Since then, computer science has extended the scope of problem solving to new levels that broaden earlier historical and philosophical perspectives.
Theoretical computer science (TCS) asserted in the 1960s that Turing machines (TMs)introduced by Turing [4] to help show the limitations of mathematical problem solvingprovide a complete model of computer problem solving by negating Turing's claim that TMs could solve only functional, algorithmic problems. The TCS view ignored Turing's assertion [4] that TMs have limited power and that choice machines, which extend TMs to interactive computation, represent a distinct form of computing not modeled by TMs.
In the 1960s theorists (such as Martin Davis of New York University) adopted the inaccurate assumptions that "TMs completely express computer problem solving" as a theoretical (mathematical) foundation of the computing discipline. The TCS model is inaccurate because TMs express only closed-box functional transformation of input to output. Computation is not entirely mathematical, since broader models of thinking and research are needed to express all possible scientific and engineering questions. Computational problem solving requires open testing of assertions about engineering problems beyond closed-box mathematical function evaluation.
People generally seem to prefer the closed arguments of rationalism based on a priori mental beliefs to the open arguments of empirical testing, which may negate closed a priori assumptions.
Problem solving is related to the notion of truth, since solutions are required to be true (correct). Truth is a central issue for all forms of reasoning but is incorrectly defined by many historians and philosophers. Truth is generally described in terms of beliefs and practices desired by the proponent rather than by provable assumptions and arguments about validity. Many scholars argue that Descartes' assertion "I think therefore I am" (cogito ergo sum) as a basis for true reasoning about the world is flawed, as are many assertions of Pythagoras, Plato, Newton, and Hilbert. Assertions by American politicians (whether Republican or Democrat), as well as by many others elsewhere, about the advantages of democracy or the justifiability of preemptive war are likewise based on a priori beliefs rather than on the accuracy (provability) of political arguments.
Even as scientists assert that truths are established more definitively by research than by political or religious arguments, the scientific assertions of Newton and Hilbert turn out to be based on a priori beliefs that are just as questionable as those of many politicians. The inaccuracy of assertions about truth and problem solving stems from faulty reasoning that persists in many diverse modes of thought. One such fault is the assumption that rationalist thinking justifies the correctness of our assertions. Pythagoras and Descartes focused on the rationalism of human thought as the foundation of correct reasoning, defining rationalism in terms of a priori predefined insight about the nature and substance of knowledge.
By contrast, empiricists (such as Locke, Berkeley, and Hume) believed that empirical testing of behavior predominates over rationalism as a measure of correctness of assertions about truth and problem solving. British empiricism contributed to the growth of the Industrial Revolution, as well as to the laws of British parliamentary politicians, the imperialism of the British Empire, and the scientific evolution of the Royal Society and the Cavendish Laboratory.
The negative effects of European rationalism in contributing to the French Revolution, as well as to the evolution of Communism and Fascism, suggest that British empiricism generated better political consequences for Western society than did European rationalism. However, in spite of the advantages of empiricism over rationalism, rationalism predominates over empiricism in contemporary democratic institutions and in reasoning about scientific and computational assumptions. People generally seem to prefer the closed arguments of rationalism based on a priori mental beliefs to the open arguments of empirical testing, which may negate closed a priori assumptions.
Hilbert's assertion that all theorems can be proved through logic was rationalist, while Turing's proof that unsolvability negated Hilbert's assumption was empiricist. The later TCS assertion that TMs express all computer problem solving was a rationalist reinterpretation of Turing's empirically based reasoning, exemplifying the historically frequent rationalist reinterpretation of empiricist arguments.
Our assumption that truth and problem solving encourage empiricist rather than rationalist argument suggests that Turing's original assumptions should be reestablished and that the rationalist reinterpretation of Turing's work by mathematical thinkers of the 1960s should be questioned and perhaps discarded. We have therefore proposed interactive computing as an empiricist model that expands computational problem solving from algorithmic TM models and functional input-output to broader concepts of interleaved dynamic streams and observable interaction with the environment.
Interactive models were advocated by Robin Milner of Edinburgh and Cambridge universities in his 1991 Turing lecture [2], as well as by advocates of artificial intelligence and object-oriented and agent-oriented programming, coordination, and concurrency. We proposed interaction as an alternative to the Japanese logical fifth-generation computing model during the early 1990s, and in [5] we argued that interaction is a more powerful tool than algorithms. More recently, we edited a book on interactive computing [1], with 18 articles by prominent researchers, including Milner, Broy, Vardi, and Van Leeuwen, describing their contributions to and opinions about interactive computing as a new paradigm of computing for the 21st century. Our article in a book on Turing's life and legacy [3] explored Turing's work on interactive computing.
The ongoing support for rationalist over empiricist modes of thought (despite repeated questioning by some philosophers) suggests that human thinking is inherently more concerned with the rationality of human desires than with the empirical truth of human reasoning. Our empirical analysis of interactive problem solving continues to be criticized by incorrect rationalist arguments about the strong problem-solving power of TMs, which are accepted as the proper form of valid reasoning, even though they were contradicted in 1936 by Turing himself.
We hope you accept that empirical (open) reasoning is often more correct than rationalist (closed) arguments, and that modes of thought about truth and problem solving should promote empiricist over rationalist reasoning, as well as definitive truth over questionable a priori value judgments.
Fundamental models of computer science evolved from the Greek modes of mathematical thought of Pythagoras and Euclid to the interactive 20th century models of computational problem solving of Gödel, Turing, and Milner. It is not surprising that changes in computing technology can determine changes in mathematical and political thinking. Computation emphasizes open processes involving interaction among machines and users, rather than the closed transformation of an input to an output.
We hope you will explore your own modes of thought, concluding that changes are needed to improve both our problem-solving paradigm and our social form of behavior and truth to make the world not only a better place in which to live but one in which to develop better scientific and political solutions as well.
References
1. Goldin, D., Smolka, S., and Wegner, P., Eds. Interactive Computing: A New Paradigm. Springer Verlag, Heidelberg, 2006.
2. Milner, R. Elements of interaction: 1991 Turing award lecture. Commun. ACM 36, 1 (Jan. 1993), 7889.
3. Teuscher, C., Ed. Alan Turing: Life and Legacy of a Great Thinker. Springer Verlag, Heidelberg, 2004.
4. Turing, A. On computable numbers with an application to the Entscheidungsproblem. In Proceedings of the London Math Society 42, 2 (1936), 230265.
5. Wegner, P. Why interaction is more powerful than algorithms. Commun. ACM 40, 5 (May 1997), 8091.
©2006 ACM 0001-0782/06/0700 $5.00
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2006 ACM, Inc.