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.

You can get some way towards the secret

Coleridge’s “Metrical Feet: Lessons for a Boy” (1834), written for his sons:

Trochee trips from long to short;
From long to long in solemn sort
Slow Spondee stalks; strong foot! yet ill able
Ever to come up with Dactyl’s trisyllable.
Iambics march from short to long;—
With a leap and a bound the swift Anapests throng.
One syllable long, with one short at each side,
Amphibrachys hastes with a stately stride;—
First and last being long, middle short, Amphimacer
Strikes his thundering hoofs like a proud high-bred racer.

A taxonomy of metrical feet from George Sainsbury’s A History of English Prose Rhythm (1912):

From Sainsbury’s preface, a little too tortured by classical learning, in the manner of Shaw:

As I approach, contemplating it still from whatever distance, the end of these studies of metre and rhythm which I may never reach, that sense of the unending endless quest,” which I suppose all but very self-satisfied and self-sufficient persons feel, impresses itself more and more upon me. An, I suppose, youthful reviewer of some different but kindred work of mine not very long ago, reproached me with ignorance or neglect of the fact that he and his generation had quite given up positive deliverances in criticism. They regarded it (I think he said) as hopeless and wrong and to “pin” something or other “to the rainbow beauty of what was really a miracle of incrustation.” The proceeding appeared to me to be difficult, if not impossible, and the phrase to be really a miracle of galimatias. But, as a fact, I hope that almost all who have read me will acquit me of the impudence or the folly of thinking that I could say even an interim last word on the secrets of rhythmical charm, whether in the slightly more tangible form of verse, or the far more intangible one of prose. Here, as everywhere, and almost more than anywhere, beauty incipit in mysterio as well as exit in mysterium. Here, and almost more also, it is as when you see a face and say to it with Browning—

Lie back; could thought of mine improve you?

and decide that, if improvement is possible, the interpretation of the actual charm is equally so. You can get some way towards the secret. The spring of the wing of the nostril; the plunge into the clear pool of the eyes, with its impenetrable background of agate or lapis lazuli, of chrysoprase or avanturine; the sweep of the cheek-edge from ear to chin; the straight descent, or curved and recurved wave, of the profile; the azure net-work of the closed eyelids; “the fringed curtains” at their juncture; the infinite intricacies of the mouth and hair,—ask yourself about any one of these, and you cannot tell why it is beautiful, why the combination of the whole makes a beautiful face. But you can, to some extent, fix for yourself the character of those parts and the composition of that whole, and, so far at least, you are ahead of the mere gaper who stares and “likes grossly.”

So it is with literature. You can never get at the final entelechy which differentiates Shelley and Shakespeare from the average versifier, Cluvienus and myself from Pater or from Browne. But you can attend to the feature-composition of the beautiful face, to the quality of the beautiful features, in each of these masters, and so you can dignify and intensify your appreciation of them. That this is best to be done in prose, as in verse, by the application of the foot-system—that is to say, by studying the combinations of the two great sound-qualities which, for my part, I call, as my fathers called them from the beginning, “long” and “short,” but which you may call anything you like, so long as you observe the difference and respect the grouping—I may almost say I know; having observed the utter practical failure of all other systems in verse, and the absence even of any attempt to apply any other to prose.

With this I may leave the present essay to its chances; only repeating my acquaintance with two quotations which I made thirty-six years ago when touching, for the first time, the subject of Prose Style generally. One was Nicholas Breton’s warning “not to talk too much of it, having so little of it,” and the other, Diderot’s epigram on Beccaria’s ouvrage sur le style où il n’y a point de style. These are, of course, “palpable hits” enough. But you may criticise without being able to create, and you may love beauty, and to the possible extent understand it, without being beautiful.

from Paul Fussell’s Poetic Meter and Poetic Form (1965):

Because the concept of the foot is an abstraction, we will never encounter a pure example of any of the standard feet. “For that matter,” as Hugh Kenner says, “you will never encounter a round face, though the term is helpful; and if the idea of a circle had never been defined for you, you might not be clearly aware of how a round face differs from a long one, even though the existence of some sort of difference is evident to the eye. The term ‘iambic foot’ has the same sort of status as the term ’round face.'” Although we will probably never meet a really pure spondee or pyrrhic, in which the two syllables are of exactly the same weight, there would seem to be no need for such over scrupulous formulations as the terms “pseudo-spondee” or “false spondee,” which suggest that our work as scansionists and critics ought to be more objective and accurate than of course it ever can be. The goal of what we are doing is enjoyment: an excessive refinement of terms and categories may impress others but it will probably not help us very much to appreciate English poetic rhythms.

Sainsbury’s remark on “the combinations of the two great sound-qualities” reminds me of Quine, “Universal Library,” in Quiddities (1987):

There is a melancholy fantasy, propounded a century and more ago by the psychologist Theodor Fechner and taken up by Kurt Lassiwitz, Theodor Wolff, Jorge Luis Borges, George Gamow, and Willy Ley, of a complete library. The library is strictly complete, boasting as it does all possible books within certain rather reasonable limits. It admits no books in alien alphabets, nor any beyond the reasonable length say of the one you are now reading, but within those restrictions it boasts all possible books. There are books in all languages, transliterated where necessary. There are coherent books and incoherent, predominantly the latter. The principle of accession is simple, if uneconomical: every combinatorially possible sequence of letters, punctuation, and spaces, up to the prescribed book length, uniformly bound in half calf.

Other writers have sufficiently belabored the numbing combinatorial statistics. At 2,000 characters to the page we get 500,000 to the 250-page volume, so with say eighty capitals and smalls and other marks to choose from we arrive at the 500,000th power of eighty as the number of books in the library. I gather that there is not room in the present phase of our expanding universe, on present estimates, for more than a negligible fraction of the collection. Numbers are cheap.

It is interesting, still, that the collection is finite. The entire and ultimate truth about everything is printed in full in that library, after all, insofar as it can be put in words at all. The limited size of each volume is no restriction, for there is always another volume that takes up the tale—any tale, true or false—where any other volume leaves off. In seeking the truth we have no way of knowing which volume to pick up nor which to follow it with, but it is all right there.

We could narrow down the choice by weeding out the gibberish, which makes up the bulk of the library. We could insist on English, and we could program a computer with English syntax and lexicon to do the scanning and discarding. The residue would be an infinitesimal fraction of the original, but still hyperastronomic.

There is an easier and cheaper way of cutting down. Some of us first learned from Samuel Finley Breese Morse what others of more mathematical bent knew before this time: that a font of two characters, dot and dash, can do all the work of our font of eighty. Morse actually used three characters, namely dot, dash and space; but two will suffice. We could use two dots for the space and then admit no initial or consecutive dots in encoding any of the other old characters.
If we retain the old format and page count for our volumes, this move reduces the size of the library’s collection to the 500,000th power of two. It is still a big number. Written out it would fill a hundred pages in standard digits, or two volumes in dots and dashes. The volumes are skimpier in thought content than before, taken one by one, because our new Morse is more than six times as long-winded as our old eighty-character font of type; but there is no loss in content over all, since for each cliff-hanging volume there is still every conceivable sequel on some shelf or other.

This last reflection—that a diminution in the coverage of each single volume does not affect the cosmic completeness of the collection—points the way to the ultimate economy: a cutback in the size of the volumes. Instead of admitting 500,000 occurrences of characters to each volume, we might settle for say seventeen. We have no longer to do with volumes, but with two-inch strips of text, and no call for half-calf bindings. In our two-character code the number of strips is 2^17, or 131,072. The totality of truth is now reduced to a manageable compass. Getting a substantial account of anything will require extensive concatenation of out two-inch strips, and re-use of strips here and there. But we have everything to work with.

The ultimate absurdity is now staring us in the face: a universal library of two volumes, one containing a single dot and the other a dash. Persistent repetition and alternation of the two is sufficient, we well know, for spelling out any and every truth. The miracle of the finite but universal library is a mere inflation of the miracle of binary notation: everything worth saying, and everything else as well, can be said with two characters. It is a letdown befitting the Wizard of Oz, but it has been a boon to computers.

in notebook