Note- this has been edited on the basis of a negative comment.

The books in Borges's Library of Babel are a random distribution of unique character strings of equal length. One way to generate the Library would be to start with the book that consists entirely of the letter a, then the one which is entirely a except that its last letter is b and so forth. This would generate the lexical ordering of the Library in a time factorial to that of producing one book. The actual order of books is random and we don't know where the Library starts and finishes. Still, we can just arbitrarily choose an anchor book and say, this is in the right place and every other book must be moved to correspond to the lexical ordering. More generally, for any bibliothetic ordering, two variables arise for any given book- first, its vector distance from the anchor book, and second its vector distance from its assigned place- both of which have polynomial form.

Thus catalogs of the Library have existential Second Order Complexity which,by Fagin's theorem, is non deterministically computable. But, since we know the books have a lexical ordering such that there is a least fixed point, it follows that algorithmic orderings are deterministically computable in exponential time. Moreover, if the catalog of the Library must also be a book in the Library then, since we know that there is no 'sparse language' in the one case which is not in the other we have no grounds for hoping that some non deterministic computation would be shorter than exponential time.

The books in Borges's Library of Babel are a random distribution of unique character strings of equal length. One way to generate the Library would be to start with the book that consists entirely of the letter a, then the one which is entirely a except that its last letter is b and so forth. This would generate the lexical ordering of the Library in a time factorial to that of producing one book. The actual order of books is random and we don't know where the Library starts and finishes. Still, we can just arbitrarily choose an anchor book and say, this is in the right place and every other book must be moved to correspond to the lexical ordering. More generally, for any bibliothetic ordering, two variables arise for any given book- first, its vector distance from the anchor book, and second its vector distance from its assigned place- both of which have polynomial form.

Thus catalogs of the Library have existential Second Order Complexity which,by Fagin's theorem, is non deterministically computable. But, since we know the books have a lexical ordering such that there is a least fixed point, it follows that algorithmic orderings are deterministically computable in exponential time. Moreover, if the catalog of the Library must also be a book in the Library then, since we know that there is no 'sparse language' in the one case which is not in the other we have no grounds for hoping that some non deterministic computation would be shorter than exponential time.

This is one approach, a pessimistic one, to answering the question-

*'Could there be a specified bibliothetic order for Borges's library that you or I could create and describe in, say, a 100-page document? Not a complete cataloguing, obviously, but an algorithm that sensibly placed the books in an order explainable to a bright and interested human? I don't think so—at least I wasn't able to dream anything up!—but nor did I see any path to a proof that no such ordering could be possible. And maybe I'm being redundant, but it wouldn't need to specify hexagon and shelf for each possible book, but rather a compelling way that set the books so that were you to find yourself in a particular hexagon, you'd have a good sense of what might be in nearby hexagons. I got nuthin'.'*

What happens if we abandon the idea of a universal descriptive language and replace it by something arising out of the theory of co-evolution? Do we thereby escape the tyranny of Time hierarchy theorems?

One reason to hope so is that co-evolution is stochastic, not deterministic, and generates 'advice strings'.- i.e. an extra input becomes available- in a particularly useful manner. The Red Queen, in Lewis Caroll's 'Through the looking glass', manages to run just as fast as the scenery- which is in 'state space explosion'- thus staying in the same place.

How might this work in practice?

Suppose 'interesting books' in the Library of Babel are traded and used as a store of value and suppose preferences are epigenetically canalized to not-too-much, not-too-little diversity (Graciella Chichilnisky- an Argentine Mathematical Economist- did path-breaking work on this in the Seventies) then over infinite time we are likely to see all sorts of bibliothetic orderings corresponding to all possible Wealth distributions which would exhaust polynomial complexity. Now, if a steady state obtains at any point, then we know from a result by Axtell, that this is also a Walrasian equilibrium- which is an exponential time algorithm for fixed points. Under certain conditions- e.g. if we assume that the race of Librarians have homothetic preferences and thus the same satiation point- this corresponds to the notion that a bibliothetic ordering has been implemented.

My feeling, however, is that there is more to this. Essentially, the Economic evolution of biblothetic ordering itself adds meaning and, what's more, the fitness landscape (assume guys more successful in the book trade live longer or have more progeny) for hermeneutics now has a sort of built in 'Red Queen' predator-prey type driver for complexity. I think this means that though any given bilateral trade is still only of complexity class P, the co-evolved complexity of the system is much greater. Indeed, Borges-the-writer-who-was-also-a-librarian's own sequential bibliothetic orderings of the books that simultaneously

My feeling, however, is that there is more to this. Essentially, the Economic evolution of biblothetic ordering itself adds meaning and, what's more, the fitness landscape (assume guys more successful in the book trade live longer or have more progeny) for hermeneutics now has a sort of built in 'Red Queen' predator-prey type driver for complexity. I think this means that though any given bilateral trade is still only of complexity class P, the co-evolved complexity of the system is much greater. Indeed, Borges-the-writer-who-was-also-a-librarian's own sequential bibliothetic orderings of the books that simultaneously

*his precursors - which corresponds to a non computable real- could have a representation. (This is because a few typos don't make much difference, so there can be a lot of book sequences corresponding to how specific works stood in relation to each other on Borges's mental book-case at different points of time)***created**
Elsewhere in the library, variorum editions of Schelling focal 'interesting books' might themselves end up with higher prices because of baked in hysteresis effects. Parallel to this is that 'important' book dealers have epigenetic canalisation- i.e. they behave like each other even though they have different origins and preferences. I think this means that a lot of the time we are going to see fractal patterns with provincial 'collections' mimicking (mutatis mutandis) those of the 'metropolitan' Merchant Princes. My guess, or particular brand of Economic Romanticism, is that this still wouldn't give us a substantive 'catalog' except as a degenerate state.

Still the co-evolved descriptive complexity I am attributing to the librarians could, of course, be a property of a discrete math simulation. We just need to tinker with the rules of the game till we get a sufficiently rich steady state fractal. But would the result be something we would find humanly cognizable or intuitive?

The problem is that, whereas librarians can have a canalised tropism to value 'interesting' books- a guy running a simulation doesn't have that ability to pick out 'interesting books' in the same way. I suppose one could breed genetic algorithms to do something which looks like Librarian Economics but the only way of knowing if what they produce is something interesting is to look inside the thing. But that's clearly illegitimate. I mean why not just put in a predator which goes through the lexical order and either quarantines or eats anything that looks meaningless when compared to the Google Books database?

Another approach, of whose legitimacy I'm not sure, is to appeal to Intutitionistic mathematics.

Suppose there is an ideal ordering such that the Expected value of the sum of randomly teleported visitor bewilderment is minimized (i.e. some visitors, by reason of their lucky location, can quickly work out the ideal order while some, who are stuck in low structure stacks, take a very long but finite time to do so). Suppose further that the visitors are of a specific mathematical race such that Total bewilderment is a function of the spread of choice sequences they construct in comparing adjacent books. Muth rationality is the notion that one's choices or expectations conform to the prediction of the correct theory. Since the best thing for the visitor race as a whole is that the library be ordered to minimize total bewilderment, it makes sense if their choice functions reflect this (i.e. they choose to be bewildered by any empirical deviation from the ideal order). So we know there is an ideal ordering (albeit only for ideal visitors).

We also know there are better than random orderings- e.g. the lexical.

I am tempted to say that by the Brouwer's continuity principle (an illegitimate use in this context?) this means there is a canonical bibliothetic ordering for all visitors who are the product of natural selection. In other words, there is some way to extract phenomenological information about us- on the assumption that we have evolved in a Darwinian manner- and make it available to Mathematics in the same way that the Anthropic principle might yield information for Physics.

I also think, because of the nature of choice sequences, one can keep changing the genotype of the visitors so that there is a trade-off between Total bewilderment minimization and other things we value- e.g. the chance for a lucky few to quickly get to a 'good' book-stack.

But, can Brouwer's principle be used in this way?

Neither books nor information about ordering poses a difficulty. Everything is well defined and therefore continuous. But is it legitimate to stipulate that choice sequences be constructively Muth rational?- doesn't that make them impredicative?

On one horn of the dilemma- the Kantian horn- we can have a priori Muth rationality but no intuitive idea of how the choice sequence is constructed, on the other horn- the Darwinian horn- we know that choices are epigenetically canalised and thus something like ex poste Muth rationality obtains only we can never be sure it is optimal, and therefore really 'rational', in any sense.

One way to resolve the dilemma is to embrace a peculiar sort of monadology in which whatever is interstital is constantly populated by virtual particles which themselves spontaneously create choice sequence bridges. This, I suppose, is the Ibn Arabi's concept of the barzakh- the incompossible, phantasmal Limbo which unites what it separates- the world of the 'command', i.e. what is possible, and the world of 'creation'- i.e. what exists- which is also the pure virtuality represented by the 'superficies of the Mirror' in the Library of Babel of which Khwaja Mir Dard was surely speaking when he wrote-

On one horn of the dilemma- the Kantian horn- we can have a priori Muth rationality but no intuitive idea of how the choice sequence is constructed, on the other horn- the Darwinian horn- we know that choices are epigenetically canalised and thus something like ex poste Muth rationality obtains only we can never be sure it is optimal, and therefore really 'rational', in any sense.

One way to resolve the dilemma is to embrace a peculiar sort of monadology in which whatever is interstital is constantly populated by virtual particles which themselves spontaneously create choice sequence bridges. This, I suppose, is the Ibn Arabi's concept of the barzakh- the incompossible, phantasmal Limbo which unites what it separates- the world of the 'command', i.e. what is possible, and the world of 'creation'- i.e. what exists- which is also the pure virtuality represented by the 'superficies of the Mirror' in the Library of Babel of which Khwaja Mir Dard was surely speaking when he wrote-

A compound of errors and confusion

ReplyDeleteErrors

1) ' Moreover, if the catalogue of the Library must also be a book in the Library, then we know that there is no 'sparse language' in NP which is not in P which means that we have no grounds for hoping that some non deterministic computation would be shorter than exponential time.'

That's certainly not what the paper you link to says- I haven't read it but even from the abstract it is clear that this is a case of apples and oranges.

Anyway, what point are you trying to make?

This is totally confusing-

You appeal to 'Brouwer's continuity principle and ask if it is legitimate to do so. I'm not sure what you are getting at.

How does natural selection come into it?

Is this a spoof of some sort?

Thank you for your comment.

DeleteI think my error was different- it was a very stupid error- and I have edited my post accordingly.

I also deleted my reply to your comment- which I now realize I shouldn't have done. It was dishonest to do so. Still, I am a very stupid man and there is no paucity of evidence on this site to attest to this.

Essentially, what I'm saying is that the Catalog is Borges's unicorn- even if we met it we couldn't recognize it and even if we had an 'oracle' to recognize it we could never bookmark it to meet it again. La tarkrar fil tajalli- there is no repetition in God's theophany- as Ibn Arabi put it. This is because, the Unicorn has the property of being difficult to discriminate from its context, or 'relativize' within a formal language- i.e. it is difficult to index or well order whatever set of things it is which instantiates 'unicorn' such that a 'Lewis elite' language carves out unicorns while carving up Reality along its joints.

I accept that I have written in a confusing and confused manner but this isn't really a spoof- except of an unintentionally self-mocking sort.

Thank you again for pointing out my mistake.

I like the idea that a robust market could order a subset of the books. It's hard to visualise it on the scale of the Library, though, as 18 typos in all different spots of one book would fill a universe the size of ours with essentially the same book. But probably you meant something like: Conceptually, if the scale was irrelevant, the market approach could produce a kind of ordering on some of the books mediated by interest.

ReplyDeleteWhat I actually meant was that a bibliothetic ordering would continually evolve on the basis of purely bibliothetic preferences and so, though there would be steady states which look like 'Walrasian equilibria' - which can be shown to have a representation as computably enumerable reals and thus the kind of thing we are looking for- still, the fact is, there is no way of telling if it is a degenerate solution.or if the attractor is stable- and, in any case, there is no a priori reason to think a steady state is a good thing.

DeleteNow it may be that 'Muth Rationality'- i.e. work inspired by or following in the footsteps of John Muth- can 'add value' (essentially by making 'information asymmetry' do some useful work within a black box) but I don't know that any such work is being done. How I imagine it would work is if information asymmetry models used mathematical objects of different orders of complexity to model the problem.