Mathesis Universalis No.7 - Summer 1998
When using any part of this text - by Witold Marciszewski - refer, please, to the URL listed at the bottom
Post's Problem of Creativity
and `Nature as Infinite Intelligence'
The phrase quoted in the title is found in Emil L. Post's Diary which under the title ``Time Accounts'' was begun in the spring of 1916 and continued to the spring of 1922. That time interval embraces the most productive time in Post's life when he prepared his doctoral dissertation (1920) ``Introduction to a general theory of elementary propositions'' (The American Journal of Mathematics, 43, 1931, 163-185) - that so seminal work which (i) introduced the truth table method, (ii) with generalizing that method put algebraic foundations of multi-valued logic, and (iii) provided a general framewok for systems of logic as means of deriving theorems through finitary symbol manipulation.Like great predecessors being both mathematicians and philosophers (notably Pascal), Post carefully distinguished scientific results, to be made public, from incomplete projects and philosophical intuitions to be entertained in privacy until they mature enough. This in why in the time he wrote the dissertation he made notes of his problems and dawning ideas, somehow related to his `public' research. Those thoughts did not come to light until Martin Davis as the editor of The Collected Works of Emil L. Post put them as Appendix to Post's paper on absolutely unsolvable problems.
Post contributed to grasping the essence of finitary mechanical operations on equal footing with Turing and Hilbert.
It someone asks how is Hilbert involved in mechanization research, this can be answered by quoting Turing's description of what he calls paper machines. It amounts to what Hilbert called formalization. This description runs as follows. "It is possible to produce the effect of computing machine by writing down a set of rules of procedure and asking a man to carry them out. Such a combination of a man with written instructions will be called a `Paper Machine'. A man provided with paper, pencil, and rubber, and subject to strict discipline, is in effect a universal machine. The expression `paper machine' will be often used below."However, Post was not fully satisfied with his theory of such operations, since it did not explain the riddle of mathematical creativity. It was the phenomenon which astonished and intrigued him (like Pascal who wondered that our reason before starts a precise proof has to trust a `feeling' that there are numbers, space, time, motion, etc).
A.Turing, `Intelligent Machinery' in Collected works of A.M. Turing. Mechanical Intelligence, ed. D.C. Ince, North-Holland 1992. See p.113.The problem of creativity was seen by Post as closely tied to that of solvability. There are problems which can be solved by mere manipulating symbols in a finite chain of steps; these do not require a creative thought. However, people successfully deal with problems which are not solvable in that way. How is it possible? How to describe the mechanism being behind such processes? What kind of logic could render and guide them?
When reading Post's Diary, we find no definite answer to such questions. His notes express rather a dim anxiety than a conclusive line of thought. However, they should be appreciated as witnessing the struggles of a great mind at the peak of his creative powers. His helplessnes gives us a measure of the degree of objective difficulties in that part of philosophy of science which so much absorbed Post.
Is there any chance in attacking the problem some tens of years later? The answer seems to be in the affirmative since we had a lot of discussions on the issues raised by Post (a great deal of them due to Gödel and Turing). Moreover, we have some experiences with computing and reasonig machines, and with computational power of Nature, which were not available to Post (he died in 1954). A totality of such discussions may be covered by what nowadays is called cognitive science. The objective of this essay is to confront Post's questions with some ideas belonging to this new field.
1. Two Concepts of Solvability There is a remarkable difference between the lexical meaning of the word solvability and its technical meaning which is in the focus of logic, philosophy of science, computer science, and cognitive science. To wit, the lexical meaning as defined, eg, by Webster's Third New International Dictionary, is as follows:
solve -- to find an answer, explanation or remedy for; arrive at a clear, definite and satisfying answer.
solution -- the fact or state of a problem's being solved.
solvable - suceptible of solution.
solvability -- the quality or state of being solvable.
Obviously, in this context `answer' means a true answer.Now, take the famous Gödel sentence, G for short, and put the problem:
[PG] Is G true?
Provided that G has number N at a list of propositions of a formalized system S, the sentence G, roughly, runs as follows.
[N] The sentence no.N is not provable in S, provided that S is consistent.The answer YES to PG results from the following consideration. The denial of G is to the effect that G is provable in S, and this means that a sentence which predicates non-provability about itself is provable. This is a contradiction. Since the denial of G implies contradiction, this denial must be false, hence G itself is true.
The answer we arrive at is clear, definite and satisfying, as required with Webster. Thus the problem answered by it enjoys the quality of being solvable, in the ordinary lexical meaning of this word.
However, in the technical meaning which holds in logic and in philosophy of science, the problem PG is not solvable, since there is no mechanical procedure, such as a formalized proof, to check the truth of G.
Now, one may ask: Which concept of solvability should be endorsed by cognitive science? That being in use in ordinary English, or that defined in logic, philosophy of science and computer science? The latter option is highly plausible because of yielding a precise definition. On the other hand, cognitive science deals with the functioning of human intelligence in the conditions of everyday life, and its features are best rendered by our everyday language.
2. Solvability as the point
where cognitive science meets philosophy of scienceThe science-philosophical term Entscheidungsproblem can be rendered as the problem of solvability as well as decision problem. The transitive verbs `to solve' and `do decide' enter a grammatical structure with different objects: it is a problem which is said to be solvable, while it is a proposition (or a set of them, as a theory) which is said to be decidable. This usage can be exemplified by the title Post's study referred to in this discussion.
Thus, a problem is said to be solvable if the answer, either in the affirmative or in the negative, is decidable. A part of the technical sense of `solvability' appears in Post's usage of the term finiteness as the property of a mechanical procedure which consists in reaching a solution in a finite number of steps.
At the same time, this term enters the definition of intelligence to mean the ability of problem solving. Since any procedures of representing and processing information by minds and organisms (the subject-matter of cognitive science) serve solving problems, the concept of solvability is as crucial for cognitive science as is for philosophy of science.
To solve problems was always the goal of science, and thus the subject of philosophical reflexion on science. However, there was no problem of solvability in the modern sense until Hilbert in 1900 announced his great programme, and then Gödel - precursed by Post - has demonstrated its limitations.In modern philosophy of science, the problem of solvability emerged with dramatic strengthening of the rigour of proof. This new rigour is what is called formalization, and it amounts to a mechanical procedure in proving. It was Frege, Peano and Russell who paved the way to this new notion in their axiomatic approaches, while Hilbert was the one who put it into an explicit methodological doctrine. Now, to solve a problem means to support the answer with a formalized proof (or, at least, a proof liable to such enhancement).Should the term mechanical be seen as a metaphor or be taken literally? Since the latter is the case - as shown by Turing, Post, and others - the theory of logic, branching into philosophy of science, meets both the theory of problem solving machines (computer science) and that of problem solving organisms (cognitive science).
It would be advantageous to have a more comprehensive concept to cover both computer science and cognitive science. The term `informatics' seems to be a suitable candidate for that role, though sometimes it is used in a narrower sense, which amounts to that of `computer science' (this terminological issue deserves a careful consideration).The great problem of cognitive science is as follows. In the present state of research on information processing - as a procedure of solving problems - we have to distinguish between two kinds of systems, to wit mechanical and creative systems. Should this difference become less and less, as we shall gain ever more knowlwedge on the both kinds of systems? Or, is it fundamental, that is, not being likely to disappear?
Turing believed that the producing of creative machines was just a matter of time; thus the mentioned disparity should disappear with the progress of our knowledge and technology. In spite of obtaining similar technical results, Post entertained a much diferent feeling. He saw the phenomenon of mental creativity as something that hardly could be reduced to operations of machine, even a highly advanced one.
Obviously, such contrasting approaches produce two divergent perspectives on cognitive science (including a theory of mind) as well as philosophy of science. In that of Turing, both disciplines would tend to become parts of a general theory of machines. In that of Post, they will ever preserve their specific problem and methods, the theory of mind being concerned with the solving of problems by creative non-mechanical minds.
3. Post's engagement in the problem of creativity Emil Post's concern with what we nowadays call cognitive science was greater than it can be judged when one reads his published metamathematical results. We learn about it owing to a certain coincidence of facts (partly reported by Roman Murawski in his contribution to this issue, Section `Canonical systems').
To wit, Post anticipated Gödel's results on incompleteness in his unpublished
Diary. He did not publish those notes for his having been aware that they needed a more detailed elaboration (moreover, he imagined how shocking such a highly unorthodox point would have been in the academic atmosphere of the twenties). However, after Gödel's results had been published, Post desired to let people know about his own approach - as a methodological alternative worth to be discussed. To certify these claims, he was ready to make publicly available a diary and notes where his ideas were sketched. The full text of them has been edited by his pupil M. Davis in the Collected Works, and so we got a look into those private records. There we encounter remarks on human creativity, much to the point for cognitive science. These comments form the Appendix to the paper in question where Post wrote in Introduction with emphasis. (p.378)
But perhaps the greatest service the present account could render would stem from its stressing of its final conclusion that mathematical thinking is, and must be, essentially creative. It is to the writer's continuing amazement that ten years after Gödel's remarkable achievement current views on the nature of mathematics are thereby affected only to the point of seeing the need of many formal systems, instead of a universal one. Rather has it seemed to us to be inevitable that these developments will result in a reversal of the entire axiomatic trend of the late 19th and early 20th centuries, with a return to meaning and truth. Postulational thinking will then remain as but one phase of mathematical thinking.In the above passage, the italicized part is accompanied by the following footnote (no.12).Yet, as this account emphasises, the creativeness of human mathematics has a counterpart inescapable limitations thereof - witness the absolutly unsolvable (combinatory) problems. Indeed, with the bubble of symbolic logic as universal logical machine finally burst, a new future dawns for it as the indispensable means for revealing and developing those limitations. For, in the spirit of the Appendix, Symbolic Logic may be said to be Mathematics self-conscious. [Aactually, the old dream of symbolic logic is finding partial realization in Tarski's recent positive work on decision problems.]Let us notice the expressive metaphor that ,,the bubble of symbolic logic as universal logical machine finally burst''. On the basis of that conviction, Post claims the restatement of the goal of logic towards its becoming just self-consciousness of mathematics (instead of being its universal tool). When compared with the contention (of some cognitive scientists) that nothing essentially changed with discoveries of Gödel, Turing, Church, and Post himself, this attitude should draw close attention. Post may have been wrong, nevertheless his intellectual quests are worth to be traced.In what follows those introductory comments, Post develops his ideas and results in two parts. Part I, entitled Formal Transformations, gives us an account of his theory of canonical forms (A, B, C), ie normal forms to which propositions of a logical system, namely Principia Mathematica, can be reduced. Part II The Anticipation serves the purpose mentioned in the title of his account, namely, to show how the results reported in Part I anticipated those of Gödel; these points are extensively disussed in Sections 2 and 3, respectively, of Roman Murawski's paper (this issue).
Part II concludes with the following statement:
A complete symbolic logic is impossible. It follows from two previously proved theorems (whose content is hinted at in the footnote quoted below), and is commented as being in line with ideas of other authors, as Russell, C.I.Lewis, and (unexpectedly enough) Bergson as the author of "Creative Evolution". The latter may prove an important hint in interpreting Post's attitude. This final statement is provided with an extensive footnote (no.101, p.428); it deserves to be cited as a whole, being related to the distinction of two concepts of solvability discussed above (Section 1).Mere incompleteness, as in the first of the two ``Theorems'' preceding, might not rule out the logic being as complete as it ever could be made. Fundamental, then, is the added effect of the second theorem, which rules out the posibility of a completed symbolic logic. That is, any symbolic logic can be made more complete. [Post, as seen from the context, means logic in the sense of such an extensive system as Principia, which in the sequel he calls `upper reaches of symbolic logic''] It is doubtful if the writer ever paused note the mere incompleteness of a symbolic logic in the sense of existence of some undecidable propositions therein, for experience with Zermelo's axiom, the axiom of infinity, and the theory of types clearly leads one expect incompleteness in the upper reaches of symbolic logic. Rather was the emphasis placed on the stronger concept of incompleteness with respect to a fixed subject matter, in the present instance the propositions stating whether a given sequence is or not is generated by the productions in a given normal systems from its initial sequence. Likewise, Gödel would stress, for example, the incompleteness of any symbolic logic with respect to the class of arithmetical propositions. Where we say ``symbolic logic'' the tendency is now to say ``finitary symbolic logic''. However, it seems to the writer that logic should be considered essentially a human enterprise, and that when this is departed from, it is then incumbent on such a writer to add a qualifying ``non-finitary''.After having so explained the concluding maxim that a complete symbolic logic is impossible, Post gives this though still another formulation, when saying: Better still, we may writeThe Logical Process is essentially Creative.
This conclusion [...] makes of the mathematician much more than a kind of clever being who can do quickly what a machine could do ultimately. We see that a machine would never give a complete logic; for once the machine is made we could prove a theorem it does not prove.This is the last passage of the study in question. Then follows Appendix including the Diary. In it various observations are recorded to explain the fact stated in the above conclusion (the pages below refer to Collected Works).
Post notices that in the mental process of proof creative and non-creative parts are intermingled (p.433). Those creative ones are found in a stream of consciousness extended in time while the non-creative parts consist of symbols manipulated which are extended in space (p.431). The creative parts are not expressed in symbols, and therefore the mind may be unaware of them (p.434).
There are in the text comments on a connexion between the creative side in the process of proof and transfinite ordinals. For scarcity of a context such utterances are not easy for interpretation. They may mean that the discovery of transfinite induction, following the discovery of tranfinite ordinals, provides a most striking example of creativity which consists in a good vision of infinitude of elements which possess stateable properties. This, Post says (p.56), cannot be unravelled by our logical process of syllogism etc. (if logical then mechanical or combinatory, for logic is meant here as finitary logic).
Whatever this should mean, there arises the question concerning a source of that capability of `seeing the infinitude' which transdends the abilities of a machine. There is a clue to a tentative answer if we take into account the phrase quoted in the title, but only when we accept an assumption which is by Post never mentioned (at the same time, there no evidence that he would question it).
To wit, let us take literally his maxim that nature is (or possesses) an infinite intelligence. The brain or a human (or even a non-human animal) is a part of nature (unlike a machine made by humans), and so may participate in its infinite intelligence.
If someone feels this conjecture as a crazy metaphysics, let him take its weaker form. That there are giant computational powers in living beings is no crazy claim nowadays (though this fact was less conspicuous in Post's times). At the same time, owing to our experiences with computers, we know the enormous role of miniaturization for obtaining ever higher computational powers. This is why a vision of quantum computer is so promising for the increase of computational powers available to us. Now suppose that the human body, or mind (seen also as part of nature) has computational power even greater than quantum computer.
To put the thing in a nutshell, the greater is the complexity of computing, the greater complexity is demanded from the computing device, and in the existing physical conditions the latter is being increased through ever deeper miniaturization. This, in turn, is incomparably greater with minds than with machines.
Now the crucial issue is whether the complexity of nature can be ever matched by human technology. There is no ready answer yet. However, those who believe - as do some quantum physicists (eg, Louis de Broglie, David Bohm, Basil Hiley), some mathematicians (eg, Georg Cantor, Stanisław Ulam) and some classics of metaphysics (eg, Pascal and Leibniz) - in the infinitude of levels with increasing degrees of complexity in the physical world, should be ready to assume that the mind may be located at a level of complexity not to be matched by human technology. Owing to that, an internal mental code (a notion that should have been enjoyed by Post, had he learned it), if recorded at a sufficiently deep level of complexity (possibly in a continuous structure) might prove unsurpassable by any discrete symbolic code of a machine.
No one can now prove things like those, but no one can disprove either; this is an open option to be investigated. Those who would try to investigate, may find encouragement in Post's belief in the infinite intelligence of nature which inspired his vision of human creativity.