The most amazing fact

A charming discussion of what should be called the fundamental theorem of computation theory, in Epstein and Carnielli, Computability: Computable Functions, Logic, and the Foundations of Mathematics (2008):

We have studied one formalization of the notion of computability. In succeeding chapters we will study two more: recursive functions and functions representable in a formal system.

The Most Amazing Fact
All the attempts at formalizing the intuitive notion of computable function yield exactly the same class of functions.

So if a function is Turing machine computable, it can also be computed in any of the other systems described in Chapter 8.E. This is a mathematical fact which requires a proof. […] Odifreddi, 1989 establishes all the equivalences. […]

The Most Amazing Fact is stated about an extensional class of functions, but it can be stated constructively: Any computation procedure for any of the attempts at formalizing the intuitive notion of computable function can be translated into any other formalization in such a way that the two formalizations have the same outputs for the same inputs.

In 1936, even before these equivalences were established, Church said,

We now define the notion, already discussed, of an effectively calculable function of positive integers by identifying it with the notion of a recursive function of positive integers (or of a lambda-definable function of positive integers). This definition is thought to be justified by the considerations which follow, so far as positive justification can ever be obtained for the selection of a formal definition to correspond to an intuitive notion.

So we have

Church’s Thesis: A function is computable iff it is lambda-definable.

This is a nonmathematical thesis: it equates an intuitive notion (computability) with a precise, formal one (lambda-definability). By our amazing fact this thesis is equivalent to

A function is computable iff it is Turing machine computable.

Turing devised his machines in a conscious attempt to capture in simplest terms what computability is. That his model turned out to give the same class of functions as Church’s (as established by Turing in the paper cited above) was strong evidence that it was the “right” class. Later we will consider some criticisms of Church’s Thesis in that the notion of computability should coincide with either a larger or a small class than the Turing machine computable ones.

Where the appearance of disorder reigned

Poincaré, “The Future of Mathematics,” 1908, in Science and Method, translated by Francis Maitland:

The importance of a fact is measured by the return it gives—that is, by the amount of thought it enables us to economize.

In physics, the facts which give a large return are those which take their place in a very general law, because they enable us to foresee a very large number of others, and it is exactly the same in mathematics. Suppose I apply myself to a complicated calculation and with much difficulty arrive at a result, I shall have gained nothing by my trouble if it has not enabled me to foresee the results of other analogous calculations, and to direct them with certainty, avoiding the blind groping with which I had to be contented the first time. On the contrary, my time will not have been lost if this very groping has succeeded in revealing to me the profound analogy between the problem just dealt with and a much more extensive class of other problems; if it has shown me at once their resemblances and their differences; if, in a word, it has enabled me to perceive the possibility of a generalization. Then it will not be merely a new result that I have acquired, but a new force.

An algebraical formula which gives us the solution of a type of numerical problems, if we finally replace the letters by numbers, is the simple example which occurs to one’s mind at once. Thanks to the formula, a single algebraical calculation saves us the trouble of a constant repetition of numerical calculations. But this is only a rough example; every one feels that there are analogies which cannot be expressed by a formula, and that they are the most valuable.

If a new result is to have any value, it must unite elements long since known, but till then scattered and seemingly foreign to each other, and suddenly introduce order where the appearance of disorder reigned. Then it enables us to see at a glance each of these elements in the place it occupies in the whole. Not only is the new fact valuable on its own account, but it alone gives a value to the old facts it unites. Our mind is frail as our senses are; it would lose itself in the complexity of the world if that complexity were not harmonious; like the short-sighted, it would only see the details, and would be obliged to forget each of these details before examining the next, because it would be incapable of taking in the whole. The only facts worthy of our attention are those which introduce order into this complexity and so make it accessible to us.

Mathematicians attach a great importance to the elegance of their methods and of their results, and this is not mere dilettantism. What is it that gives us the feeling of elegance in a solution or a demonstration? It is the harmony of the different parts, their symmetry, and their happy adjustment; it is, in a word, all that introduces order, all that gives them unity, that enables us to obtain a clear comprehension of the whole as well as of the parts. But that is also precisely what causes it to give a large return; and in fact the more we see this whole clearly and at a single glance, the better we shall perceive the analogies with other neighbouring objects, and consequently the better chance we shall have of guessing the possible generalizations. Elegance may result from the feeling of surprise caused by the un-looked-for occurrence together of objects not habitually associated. In this, again, it is fruitful, since it thus discloses relations till then unrecognized. It is also fruitful even when it only results from the contrast between the simplicity of the means and the complexity of the problem presented, for it then causes us to reflect on the reason for this contrast, and generally shows us that this reason is not chance, but is to be found in some unsuspected law. Briefly stated, the sentiment of mathematical elegance is nothing but the satisfaction due to some conformity between the solution we wish to discover and the necessities of our mind, and it is on account of this very conformity that the solution can be an instrument for us. This aesthetic satisfaction is consequently connected with the economy of thought. Again the comparison with the Erechtheum occurs to me, but I do not wish to serve it up too often.

It is for the same reason that, when a somewhat lengthy calculation has conducted us to some simple and striking result, we are not satisfied until we have shown that we might have foreseen, if not the whole result, at least its most characteristic features. Why is this? What is it that prevents our being contented with a calculation which has taught us apparently all that we wished to know? The reason is that, in analogous cases, the lengthy calculation might not be able to be used again, while this is not true of the reasoning, often semi-intuitive, which might have enabled us to foresee the result. This reasoning being short, we can see all the parts at a single glance, so that we perceive immediately what must be changed to adapt it to all the problems of a similar nature that may be presented. And since it enables us to foresee whether the solution of these problems will be simple, it shows us at least whether the calculation is worth undertaking.

What I have just said is sufficient to show how vain it would be to attempt to replace the mathematician’s free initiative by a mechanical process of any kind. In order to obtain a result having any real value, it is not enough to grind out calculations, or to have a machine for putting things in order: it is not order only, but unexpected order, that has a value. A machine can take hold of the bare fact, but the soul of the fact will always escape it.

Since the middle of last century, mathematicians have become more and more anxious to attain to absolute exactness. They are quite right, and this tendency will become more and more marked. In mathematics, exactness is not everything, but without it there is nothing: a demonstration which lacks exactness is nothing at all. This is a truth that I think no one will dispute, but if it is taken too literally it leads us to the conclusion that before 1820, for instance, there was no such thing as mathematics, and this is clearly an exaggeration. The geometricians of that day were willing to assume what we explain by prolix dissertations. This does not mean that they did not see it at all, but they passed it over too hastily, and, in order to see it clearly, they would have had to take the trouble to state it.

Only, is it always necessary to state it so many times? Those who were the first to pay special attention to exactness have given us reasonings that we may attempt to imitate; but if the demonstrations of the future are to be constructed on this model, mathematical works will become exceedingly long, and if I dread length, it is not only because I am afraid of the congestion of our libraries, but because I fear that as they grow in length our demonstrations will lose that appearance of harmony which plays such a useful part, as I have just explained.

It is economy of thought that we should aim at, and therefore it is not sufficient to give models to be copied. We must enable those that come after us to do without the models, and not to repeat a previous reasoning, but summarize it in a few lines. And this has already been done successfully in certain cases. For instance, there was a whole class of reasonings that resembled each other, and were found everywhere; they were perfectly exact, but they were long. One day some one thought of the term “uniformity of convergence,” and this term alone made them useless; it was no longer necessary to repeat them, since they could now be assumed. Thus the hair-splitters can render us a double service, first by teaching us to do as they do if necessary, but more especially by enabling us as often as possible not to do as they do, and yet make no sacrifice of exactness.

One example has just shown us the importance of terms in mathematics; but I could quote many others. It is hardly possible to believe what economy of thought, as Mach used to say, can be effected by a well-chosen term. I think I have already said somewhere that mathematics is the art of giving the same name to different things. It is enough that these things, though differing in matter, should be similar in form, to permit of their being, so to speak, run in the same mould. When language has been well chosen, one is astonished to find that all demonstrations made for a known object apply immediately to many new objects: nothing requires to be changed, not even the terms, since the names have become the same.

A well-chosen term is very often sufficient to remove the exceptions permitted by the rules as stated in the old phraseology. This accounts for the invention of negative quantities, imaginary quantities, decimals to infinity, and I know not what else. And we must never forget that exceptions are pernicious, because they conceal laws.

This is one of the characteristics by which we recognize facts which give a great return: they are the facts which permit of these happy innovations of language. The bare fact, then, has sometimes no great interest: it may have been noted many times without rendering any great service to science; it only acquires a value when some more careful thinker perceives the connexion it brings out, and symbolizes it by a term.

AI as CogSci

Douglas Stewart in conversation with Herbert Simon, Omni, 1994:

OMNI:

What is the main goal of AI?

SIMON:

AI can have two purposes. One is to use the power of computers to augment human thinking, just as we use motors to augment human or horse power. Robotics and expert systems are major branches of that. The other is to use a computer’s artificial intelligence to understand how humans think. In a humanoid way. If you test your programs not merely by what they can accomplish, but how they accomplish it, they you’re really doing cognitive science; you’re using AI to understand the human mind.