Appendix C Allen Newell. "Heuristic Programming: Ill-Structured Problems," chapter 10, pp 361414, in Publications in Operations Research, Progress in Operations Research: Relationship Between Operations Research and the Computer, Volume III, edited by Julius S. Aronofsky, of Operations Research Society of America, Publications in Operations Research Number 16, David B. Hertz, editor, copyrighted 1969. Reprinted by permission of John Wiley & Sons, Inc., New York. Chapter 10 HEURISTIC PROGRAMMING: ILL-STRUCTURED PROBLEMS ALLEN NEWELL Reprinted from J. S. Aronofsky, (ed.) Progress in Operations Research, Volume III, We observe that on occasion expressions in some language are put forward that purport to state "a problem." In response a method (or algorithm) is advanced that claims to solve the problem. That is, if input data are given that meet all the specifications of the problem statement, the method produces another expression in the language that is the solution to the problem. If there is a chailenge as to whether the method actually provides a general solution to the problem (i.e., for all admissible inputs), a proof may be forthcoming that it does. If there is a challenge to whether the problem statement is well defined, additional formalization of the problem statement may occur. In the extreme this can reach tack to formalization of the language used to state the problem, until a formal logical calculus is used. We also observe that for other problems that people have and solve there seems to be no such formalized statement and formalized method. Although usually definite in some respects problems of this type seem incurably fuzzy in others. That there should be ill-defined problems around is not very surprising. That is, that there should be expressions that have some characteristics of problem statements but are fragmentary seems not surprising. However, that there should exist systems (i.e., men) that can solve these problems without the eventual intervention of formal statements and formal methods does pose an issue. Perhaps there are two domains of problems, the well structured and the ill structured. Formalization always implies the first. Men can deal with both kinds. By virtue of their capacity for working with ill-structured problems, they can transmute some of these into well-structured (or formalized) problems. But the study of formalized problems has nothing to say about the domain of ill-structured problems. In particular, there can never be a formalization of ill-structured problems, hence never a theory (in a strict sense) about them. All that is possible is the conversion of particular problems from ill structured to well structured via the one transducer that exists, namely, man. Perhaps an analog is useful: well-structured problems are to illstructured problems as linear systems are to nonlinear systems, or as I wish to acknowledge the help of J. Moore in clarifying the nature of the methods of artificial intelligence and also my discussions with my colleague H. A. Simon. The research was supported by the Advanced Research Projects Agency of the Office of the Secretary of Defense (SD-146). 363 |