Malicious Machine Learnings? Privacy Preservation and Computational Correctness Across Parties. Note Quote/Didactics.

Multi-Party Computation deals with the following problem: There are n ≥ 2 parties P₁, . . ., P_n where party P_i holds input t_i, 1 ≤ i ≤ n, and they wish to compute together a functions = f (t₁, . . . , t_n) on their inputs. The goal is that each party will learn the output of the function, s, yet with the restriction that P_i will not learn any additional information about the input of the other parties aside from what can be deduced from the pair (t_i, s). Clearly it is the secrecy restriction that adds complexity to the problem, as without it each party could announce its input to all other parties, and each party would locally compute the value of the function. Thus, the goal of Multi-Party Computation is to achieve the following two properties at the same time: correctness of the computation and privacy preservation of the inputs.

The following two generalizations are often useful:

(i) Probabilistic functions. Here the value of the function depends on some random string r chosen according to some distribution: s = f (t₁, . . . , t_n; r). An example of this is the coin-flipping functionality, which takes no inputs, and outputs an unbiased random bit. It is crucial that the value r is not controlled by any of the parties, but is somehow jointly generated during the computation.

(ii) Multioutput functions. It is not mandatory that there be a single output of the function. More generally there could be a unique output for each party, i.e., (s₁, . . . , s_n) = f(t₁,…, t_n). In this case, only party P_i learns the output s_i, and no other party learns any information about the other parties’ input and outputs aside from what can be derived from its own input and output.

One of the most interesting aspects of Multi-Party Computation is to reach the objective of computing the function value, but under the assumption that some of the parties may deviate from the protocol. In cryptography, the parties are usually divided into two types: honest and faulty. An honest party follows the protocol without any deviation. Otherwise, the party is considered to be faulty. The faulty behavior can exemplify itself in a wide range of possibilities. The most benign faulty behavior is where the parties follow the protocol, yet try to learn as much as possible about the inputs of the other parties. These parties are called honest-but-curious (or semihonest). At the other end of the spectrum, the parties may deviate from the prescribed protocol in any way that they desire, with the goal of either influencing the computed output value in some way, or of learning as much as possible about the inputs of the other parties. These parties are called malicious.

We envision an adversary A, who controls all the faulty parties and can coordinate their actions. Thus, in a sense we assume that the faulty parties are working together and can exert the most knowledge and influence over the computation out of this collusion. The adversary can corrupt any number of parties out of the n participating parties. Yet, in order to be able to achieve a solution to the problem, in many cases we would need to limit the number of corrupted parties. This limit is called the threshold k, indicating that the protocol remains secure as long as the number of corrupted parties is at most k.

Assume that there exists a trusted party who privately receives the inputs of all the participating parties, calculates the output value s, and then transmits this value to each one of the parties. This process clearly computes the correct output of f, and also does not enable the participating parties to learn any additional information about the inputs of others. We call this model the ideal model. The security of Multi-Party Computation then states that a protocol is secure if its execution satisfies the following: (1) the honest parties compute the same (correct) outputs as they would in the ideal model; and (2) the protocol does not expose more information than a comparable execution with the trusted party, in the ideal model.

Intuitively, the adversary’s interaction with the parties (on a vector of inputs) in the protocol generates a transcript. This transcript is a random variable that includes the outputs of all the honest parties, which is needed to ensure correctness, and the output of the adversary A. The latter output, without loss of generality, includes all the information that the adversary learned, including its inputs, private state, all the messages sent by the honest parties to A, and, depending on the model, maybe even include more information, such as public messages that the honest parties exchanged. If we show that exactly the same transcript distribution can be generated when interacting with the trusted party in the ideal model, then we are guaranteed that no information is leaked from the computation via the execution of the protocol, as we know that the ideal process does not expose any information about the inputs. More formally,

Let f be a function on n inputs and let π be a protocol that computes the function f. Given an adversary A, which controls some set of parties, we define REAL_A,π(t) to be the sequence of outputs of honest parties resulting from the execution of π on input vector t under the attack of A, in addition to the output of A. Similarly, given an adversary A′ which controls a set of parties, we define IDEAL_A′,f(t) to be the sequence of outputs of honest parties computed by the trusted party in the ideal model on input vector t, in addition to the output of A′. We say that π securely computes f if, for every adversary A as above, ∃ an adversary A′, which controls the same parties in the ideal model, such that, on any input vector t, we have that the distribution of REAL_A,π(t) is “indistinguishable” from the distribution of IDEAL_A′,f(t).

Intuitively, the task of the ideal adversary A′ is to generate (almost) the same output as A generates in the real execution or the real model. Thus, the attacker A′ is often called the simulator of A. The transcript value generated in the ideal model, IDEAL_A′,f(t), also includes the outputs of the honest parties (even though we do not give these outputs to A′), which we know were correctly computed by the trusted party. Thus, the real transcript REAL_A,π(t) should also include correct outputs of the honest parties in the real model.

We assumed that every party P_i has an input t_i, which it enters into the computation. However, if P_i is faulty, nothing stops P_i from changing t_i into some t_i′. Thus, the notion of a “correct” input is defined only for honest parties. However, the “effective” input of a faulty party P_i could be defined as the value t_i′ that the simulator A′ gives to the trusted party in the ideal model. Indeed, since the outputs of honest parties look the same in both models, for all effective purposes P_i must have “contributed” the same input t_i′ in the real model.

Another possible misbehavior of P_i, even in the ideal model, might be a refusal to give any input at all to the trusted party. This can be handled in a variety of ways, ranging from aborting the entire computation to simply assigning t_i some “default value.” For concreteness, we assume that the domain of f includes a special symbol ⊥ indicating this refusal to give the input, so that it is well defined how f should be computed on such missing inputs. What this requires is that in any real protocol we detect when a party does not enter its input and deal with it exactly in the same manner as if the party would input ⊥ in the ideal model.

As regards security, it is implicitly assumed that all honest parties receive the output of the computation. This is achieved by stating that IDEAL_A′,f(t) includes the outputs of all honest parties. We therefore say that our currency guarantees output delivery. A more relaxed property than output delivery is fairness. If fairness is achieved, then this means that if at least one (even faulty) party learns its outputs, then all (honest) parties eventually do too. A bit more formally, we allow the ideal model adversary A′ to instruct the trusted party not to compute any of the outputs. In this case, in the ideal model either all the parties learn the output, or none do. Since A’s transcript is indistinguishable from A′’s this guarantees that the same fairness guarantee must hold in the real model as well.

A further relaxation of the definition of security is to provide only correctness and privacy. This means that faulty parties can learn their outputs, and prevent the honest parties from learning theirs. Yet, at the same time the protocol will still guarantee that (1) if an honest party receives an output, then this is the correct value, and (2) the privacy of the inputs and outputs of the honest parties is preserved.

The basic security notions are universal and model-independent. However, specific implementations crucially depend on spelling out precisely the model where the computation will be carried out. In particular, the following issues must be specified:

1. The faulty parties could be honest-but-curious or malicious, and there is usually an upper bound k on the number of parties that the adversary can corrupt.
2. Distinguishing between the computational setting and the information theoretic setting, in the latter, the adversary is unlimited in its computing powers. Thus, the term “indistinguishable” is formalized by requiring the two transcript distributions to be either identical (so-called perfect security) or, at least, statistically close in their variation distance (so-called statistical security). On the other hand, in the computational, the power of the adversary (as well as that of the honest parties) is restricted. A bit more precisely, Multi-Party Computation problem is parameterized by the security parameter λ, in which case (a) all the computation and communication shall be done in time polynomial in λ; and (b) the misbehavior strategies of the faulty parties are also restricted to be run in time polynomial in λ. Furthermore, the term “indistinguishability” is formalized by computational indistinguishability: two distribution ensembles {X_λ}_λ and {Y_λ}_λ are said to be computationally indistinguishable, if for any polynomial-time distinguisher D, the quantity ε, defined as |Pr[D(X_λ) = 1] − Pr[D(Y_λ) = 1]|, is a “negligible” function of λ. This means that for any j > 0 and all sufficiently large λ, ε eventually becomes smaller than λ − j. This modeling helps us to build secure Multi-Party Computational protocols depending on plausible computational assumptions, such as the hardness of factoring large integers.
3. The two common communication assumptions are the existence of a secure channel and the existence of a broadcast channel. Secure channels assume that every pair of parties P_i and P_j are connected via an authenticated, private channel. A broadcast channel is a channel with the following properties: if a party P_i (honest or faulty) broadcasts a message m, then m is correctly received by all the parties (who are also sure the message came from P_i). In particular, if an honest party receives m, then it knows that every other honest party also received m. A different communication assumption is the existence of envelopes. An envelope guarantees the following properties: a value m can be stored inside the envelope, it will be held without exposure for a given period of time, and then the value m will be revealed without modification. A ballot box is an enhancement of the envelope setting that also provides a random shuffling mechanism of the envelopes. These are, of course, idealized assumptions that allow for a clean description of a protocol, as they separate the communication issues from the computational ones. These idealized assumptions may be realized by a physical mechanisms, but in some settings such mechanisms may not be available. Then it is important to address the question if and under what circumstances we can remove a given communication assumption. For example, we know that the assumption of a secure channel can be substituted with a protocol, but under the introduction of a computational assumption and a public key infrastructure.

Advertisement

Fascism’s Incognito – Conjuncted

“Being asked to define fascism is probably the scariest moment for any expert of fascism,” Montague said.

Brecht’s circular circuitry is here.

Allow me to make cross-sectional (both historically and geographically) references. I start with Mussolini, who talked of what use fascism could be put to by stating that capitalism throws itself into the protection of the state when it is in crisis, and he illustrated this point by referring to the Great Depression as a failure of laissez-faire capitalism and thus creating an opportunity for fascist state to provide an alternative to this failure. This in a way points to the fact that fascism springs to life economically in the event of capitalism’s deterioration. To highlight this point of fascism springing to life as a reaction to capitalism’s failure, let me take recourse to Samir Amin, who calls the fascist choice for managing a capitalist society in crisis as a categorial rejection of democracy, despite having reached that stage democratically. The masses are subjected to values of submission to a unity of socio-economic, political and/or religious ideological discourses. This is one reason why I call fascism not as a derivative category of capitalism in the sense of former being the historic phase of the latter, but rather as a coterminous tendency waiting in dormancy for capitalism to deteriorate, so that fascism could then detonate. But, are fascism and capitalism related in a multiple of ways is as good as how socialism is related with fascism, albeit only differently categorically.

It is imperative for me to add by way of what I perceive as financial capitalism and bureaucracy and where exactly art gets sandwiched in between the two, for more than anything else, I would firmly believe in Brecht as continuing the artistic practices of Marxian sociology and political-economy.

The financial capitalism combined with the impersonal bureaucracy has inverted the traditional schematic forcing us to live in a totalitarian system of financial governance divorced from democratic polity. It’s not even fascism in the older sense of the term, by being a collusion of state and corporate power, since the political is bankrupt and has become a mediatainment system of control and buffer against the fact of Plutocracies. The state will remain only as long as the police systems are needed to fend off people claiming rights to their rights. Politicians are dramaturgists and media personalities rather than workers in law.  If one were to just study the literature and paintings of the last 3-4 decades, it is fathomable where it is all going. Arts still continue to speak what we do not want to hear. Most of our academics are idiots clinging on to the ideological culture of the left that has put on its blinkers and has only one enemy, which is the right (whatever the hell that is). Instead of moving outside their straightjackets and embracing the world of the present, they still seem to be ensconced in 19th century utopianism with the only addition to their arsenal being the dramatic affects of mass media. Remember Thomas Pynchon of Gravity’s Rainbow fame (I prefer calling him the illegitimate cousin of James Joyce for his craftiness and smoothly sailing contrite plots: there goes off my first of paroxysms!!), who likened the system of techno-politics as an extension of our inhuman core, at best autonomous, intelligent and ever willing to exist outside the control of politics altogether. This befits the operational closure and echoing time and time again that technology isn’t an alien thing, but rather a manifestation of our inhuman core, a mutation of our shared fragments sieved together in ungodly ways. This is alien technologies in gratitude.

We have never been natural, and purportedly so by building defence systems against the natural both intrinsically and extrinsically. Take for example, Civilisation, the most artificial construct of all humans had busied themselves building and now busying themselves upholding. what is it? A Human Security System staving off entropy of existence through the self-perpetuation of a cultural complex of temporal immortalisation, if nothing less and vulnerable to editions by scores of pundits claiming to a larger schemata often overlooked by parochiality. Haven’t we become accustomed to hibernating in an artificial time now exposed by inhabiting the infosphere, creating dividualities by reckoning to data we intake, partake and outtake. Isn’t analysing the part/whole dividuality really scoring our worthiness? I know the answer is yes, but merely refusing to jump off the tongue. Democracies have made us indolent with extremities ever so flirting with electronic knowledge waiting to be turned to digital ash when confronted with the existential threat to our locus standi.

But, we always think of a secret cabal conspiring to dehumanise us. But we also forget the impersonality of the dataverse, the infosphere, the carnival we simply cannot avoid being a part of. Our mistaken beliefs lie in reductionism, and this is a serious detriment to causes created ex nihilo, for a fight is inevitably diluted if we pay insignificance to the global meshwork of complex systems of economics and control, for these far outstrip our ability to pin down to a critical apparatus. This apparatus needs to be different from ones based on criticism, for the latter is prone to sciolist tendencies. Maybe, one needs to admit allegiance to perils of our position and go along in a Socratic irony before turning in against the admittance at opportune times. Right deserves tackling through the Socratic irony, lest taking offences become platitudinous. Let us not forget that the modern state is nothing but a PR firm to keep the children asleep and unthinking and believing in the dramaturgy of the political as real. And this is where Brecht comes right back in, for he considered creation of bureaucracies as affronting not just fascist states, but even communist ones. The above aside, or digression is just a reality check on how much complex capitalism has become and with it, its derivatives of fascism as these are too intertwined within bureaucratic spaces. Even when Brecht was writing in his heydays, he took a deviation from his culinary-as-ever epic theatre to found a new form of what he called theatre as learning to play that resembled his political seminars modeled on the rejection of the concept of bureaucratic elitism in partisan politics where the theorists and functionaries issued directives and controlled activities on behalf of the masses to the point of submission of the latter to the former. This point is highlighted not just for fascist states, but equally well for socialist/communist regimes reiterating the fact that fascism is potent enough to develop in societies other than capitalistic ones.

Moving on to the point when mentions of democracy as bourgeois democracy is done in the same breath as regards equality only for those who are holders of capital are turning platitudinous. Well, structurally yes, this is what it seems like, but reality goes a bit deeper and thereafter fissures itself into looking at if capital indeed is what it is perceived as in general, or is there more to it than meets the eye. I quip this to confront two theorists of equality with one another: Piketty and Sally Goerner. Piketty misses a great opportunity to tie the “r > g” idea (after tax returns on capital r > growth rate of economy g) to the “limits to growth”. With a careful look at history, there are several quite important choice points along the path from the initial hope it won’t work out that way… to the inevitable distressing end he describes, and sees, and regrets. It’s what seduces us into so foolishly believing we can maintain “g > r”, despite the very clear and hard evidence of that faiIing all the time… that sometimes it doesn’t. The real “central contradiction of capitalism” then, is that it promises “g > r”, and then we inevitably find it is only temporary. Growth is actually nature’s universal start-up process, used to initially build every life, including the lives of every business, and the lives of every society. Nature begins building things with growth. She’s then also happy to destroy them with more of the same, those lives that began with healthy growth that make the fateful choice of continuing to devote their resources to driving their internal and external strains to the breaking point, trying to make g > r perpetual. It can’t be. So the secret to the puzzle seems to be: Once you’ve taken growth from “g > r” to spoiling its promise in its “r > g” you’ve missed the real opportunity it presented. Sally Goerner writes about how systems need to find new ways to grow through a process of rising intricacy that literally reorganizes the system into a higher level of complexity. Systems that fail to do that collapse. So smart growth is possible (a cell divides into multiple cells that then form an organ of higher complexity and greater intricacy through working cooperatively). Such smart growth is regenerative in that it manifests new potential. How different that feels than conventional scaling up of a business, often at the expense of intricacy (in order to achieve so called economies of scale). Leaps of complexity do satisfy growing demands for productivity, but only temporarily, as continually rising demands of productivity inevitably require ever bigger leaps of complexity. Reorganizing the system by adopting ever higher levels of intricacy eventually makes things ever more unmanageable, naturally becoming organizationally unstable, to collapse for that reason. So seeking the rise in productivity in exchange for a rising risk of disorderly collapse is like jumping out of the fry pan right into the fire! As a path to system longevity, then, it is tempting but risky, indeed appearing to be regenerative temporarily, until the same impossible challenge of keeping up with ever increasing demands for new productivity drives to abandon the next level of complexity too! The more intricacy (tight, small-scale weave) grows horizontally, the more unmanageable it becomes. That’s why all sorts of systems develop what we would call hierarchical structures. Here, however, hierarchal structures serve primarily as connective tissue that helps coordinate, facilitate and communicate across scales. One of the reasons human societies are falling apart is because many of our hierarchical structures no longer serve this connective tissue role, but rather fuel processes of draining and self-destruction by creating sinks where refuse could be regenerated. Capitalism, in its present financial form is precisely this sink, whereas capitalism wedded to fascism as an historical alliance doesn’t fit the purpose and thus proving once more that the collateral damage would be lent out to fascist states if that were to be the case, which would indeed materialize that way.

That democracy is bourgeois democracy is an idea associated with Swedish political theorist Goran Therborn, who as recent as the 2016 US elections proved his point by questioning the whole edifice of inclusive-exclusive aspects of democracy, when he said,

Even if capitalist markets do have an inclusive aspect, open to exchange with anyone…as long as it is profitable, capitalism as a whole is predominantly and inherently a system of social exclusion, dividing people by property and excluding the non-profitable. a system of this kind is, of course, incapable of allowing the capabilities of all humankind to be realized. and currently the the system looks well fortified, even though new critical currents are hitting against it.

Democracy did take on a positive meaning, and ironically enough, it was through rise of nation-states, consolidation of popular sovereignty championed by the west that it met its two most vociferous challenges in the form of communism and fascism, of which the latter was a reactionary response to the discontents of capitalist modernity. Its radically lay in racism and populism. A degree of deference toward the privileged and propertied, rather than radical opposition as in populism, went along with elite concessions affecting the welfare, social security, and improvement of the working masses. This was countered by, even in the programs of moderate and conservative parties by using state power to curtail the most malign effects of unfettered market dynamics. It was only in the works of Hayek that such interventions were beginning to represent the road to serfdom thus paving way to modern-day right-wing economies, of which state had absolutely no role to play as regards markets fundamentals and dynamics. The counter to bourgeois democracy was rooted in social democratic movements and is still is, one that is based on negotiation, compromise, give and take a a grudgingly given respect for the others (whether ideologically or individually). The point again is just to reiterate that fascism, in my opinion is not to be seen as a nakedest form of capitalism, but is generally seen to be floundering on the shoals of an economic slowdown or crisis of stagflation.

On ideal categories, I am not a Weberian at heart. I am a bit ambiguous or even ambivalent to the role of social science as a discipline that could draft a resolution to ideal types and interactions between those generating efficacies of real life. Though, it does form one aspect of it. My ontologies would lie in classificatory and constructive forms from more logical grounds that leave ample room for deviations and order-disorder dichotomies. Complexity is basically an offspring of entropy.

And here is where my student-days of philosophical pessimism surface, or were they ever dead, as the real way out is a dark path through the world we too long pretended did not exist.

Symmetrical – Asymmetrical Dialectics Within Catastrophical Dynamics. Thought of the Day 148.0

Catastrophe theory has been developed as a deterministic theory for systems that may respond to continuous changes in control variables by a discontinuous change from one equilibrium state to another. A key idea is that system under study is driven towards an equilibrium state. The behavior of the dynamical systems under study is completely determined by a so-called potential function, which depends on behavioral and control variables. The behavioral, or state variable describes the state of the system, while control variables determine the behavior of the system. The dynamics under catastrophe models can become extremely complex, and according to the classification theory of Thom, there are seven different families based on the number of control and dependent variables.

Let us suppose that the process y_t evolves over t = 1,…, T as

dy_t = -dV(y_t; α, β)dt/dy_t —– (1)

where V (y_t; α, β) is the potential function describing the dynamics of the state variable y_t controlled by parameters α and β determining the system. When the right-hand side of (1) equals zero, −dV (y_t; α, β)/dy_t = 0, the system is in equilibrium. If the system is at a non-equilibrium point, it will move back to its equilibrium where the potential function takes the minimum values with respect to y_t. While the concept of potential function is very general, i.e. it can be quadratic yielding equilibrium of a simple flat response surface, one of the most applied potential functions in behavioral sciences, a cusp potential function is defined as

−V(y_t; α, β) = −1/4y_t⁴ + 1/2βy_t² + αy_t —– (2)

with equilibria at

-dV(y_t; α, β)dt/dy_t = -y_t³ + βy_t + α —– (3)

being equal to zero. The two dimensions of the control space, α and β, further depend on realizations from i = 1 . . . , n independent variables x_i,t. Thus it is convenient to think about them as functions

α_x = α₀ +α₁x_1,t +…+ α_nx_n,t —– (4)

β_x = β₀ + β₁x_1,t +…+ β_nx_n,t —– (5)

The control functions α_x and β_x are called normal and splitting factors, or asymmetry and bifurcation factors, respectively and they determine the predicted values of y_t given x_i,t. This means that for each combination of values of independent variables there might be up to three predicted values of the state variable given by roots of

-dV(y_t; α_x, β_x)dt/dy_t = -y_t³ + βy_t + α = 0 —– (6)

This equation has one solution if

δ_x = 1/4α_x² − 1/27β_x³ —– (7)

is greater than zero, δ_x > 0 and three solutions if δ_x < 0. This construction can serve as a statistic for bimodality, one of the catastrophe flags. The set of values for which the discriminant is equal to zero, δ_x = 0 is the bifurcation set which determines the set of singularity points in the system. In the case of three roots, the central root is called an “anti-prediction” and is least probable state of the system. Inside the bifurcation, when δ_x < 0, the surface predicts two possible values of the state variable which means that the state variable is bimodal in this case.

Most of the systems in behavioral sciences are subject to noise stemming from measurement errors or inherent stochastic nature of the system under study. Thus for a real-world applications, it is necessary to add non-deterministic behavior into the system. As catastrophe theory has primarily been developed to describe deterministic systems, it may not be obvious how to extend the theory to stochastic systems. An important bridge has been provided by the Itô stochastic differential equations to establish a link between the potential function of a deterministic catastrophe system and the stationary probability density function of the corresponding stochastic process. Adding a stochastic Gaussian white noise term to the system

dy_t = -dV(y_t; α_x, β_x)dt/dy_t + σ_ytdW_t —– (8)

where -dV(y_t; α_x, β_x)dt/dy_t is the deterministic term, or drift function representing the equilibrium state of the cusp catastrophe, σ_yt is the diffusion function and W_t is a Wiener process. When the diffusion function is constant, σ_yt = σ, and the current measurement scale is not to be nonlinearly transformed, the stochastic potential function is proportional to deterministic potential function and probability distribution function corresponding to the solution from (8) converges to a probability distribution function of a limiting stationary stochastic process as dynamics of y_t are assumed to be much faster than changes in x_i,t. The probability density that describes the distribution of the system’s states at any t is then

f_s(y|x) = ψ exp((−1/4)y⁴ + (β_x/2)y² + α_xy)/σ —– (9)

The constant ψ normalizes the probability distribution function so its integral over the entire range equals to one. As bifurcation factor β_x changes from negative to positive, the f_s(y|x) changes its shape from unimodal to bimodal. On the other hand, α_x causes asymmetry in f_s(y|x).

Knowledge Limited for Dummies….Didactics.

Bertrand Russell with Alfred North Whitehead, in the Principia Mathematica aimed to demonstrate that “all pure mathematics follows from purely logical premises and uses only concepts defined in logical terms.” Its goal was to provide a formalized logic for all mathematics, to develop the full structure of mathematics where every premise could be proved from a clear set of initial axioms.

Russell observed of the dense and demanding work, “I used to know of only six people who had read the later parts of the book. Three of those were Poles, subsequently (I believe) liquidated by Hitler. The other three were Texans, subsequently successfully assimilated.” The complex mathematical symbols of the manuscript required it to be written by hand, and its sheer size – when it was finally ready for the publisher, Russell had to hire a panel truck to send it off – made it impossible to copy. Russell recounted that “every time that I went out for a walk I used to be afraid that the house would catch fire and the manuscript get burnt up.”

Momentous though it was, the greatest achievement of Principia Mathematica was realized two decades after its completion when it provided the fodder for the metamathematical enterprises of an Austrian, Kurt Gödel. Although Gödel did face the risk of being liquidated by Hitler (therefore fleeing to the Institute of Advanced Studies at Princeton), he was neither a Pole nor a Texan. In 1931, he wrote a treatise entitled On Formally Undecidable Propositions of Principia Mathematica and Related Systems, which demonstrated that the goal Russell and Whitehead had so single-mindedly pursued was unattainable.

The flavor of Gödel’s basic argument can be captured in the contradictions contained in a schoolboy’s brainteaser. A sheet of paper has the words “The statement on the other side of this paper is true” written on one side and “The statement on the other side of this paper is false” on the reverse. The conflict isn’t resolvable. Or, even more trivially, a statement like; “This statement is unprovable.” You cannot prove the statement is true, because doing so would contradict it. If you prove the statement is false, then that means its converse is true – it is provable – which again is a contradiction.

The key point of contradiction for these two examples is that they are self-referential. This same sort of self-referentiality is the keystone of Gödel’s proof, where he uses statements that imbed other statements within them. This problem did not totally escape Russell and Whitehead. By the end of 1901, Russell had completed the first round of writing Principia Mathematica and thought he was in the homestretch, but was increasingly beset by these sorts of apparently simple-minded contradictions falling in the path of his goal. He wrote that “it seemed unworthy of a grown man to spend his time on such trivialities, but . . . trivial or not, the matter was a challenge.” Attempts to address the challenge extended the development of Principia Mathematica by nearly a decade.

Yet Russell and Whitehead had, after all that effort, missed the central point. Like granite outcroppings piercing through a bed of moss, these apparently trivial contradictions were rooted in the core of mathematics and logic, and were only the most readily manifest examples of a limit to our ability to structure formal mathematical systems. Just four years before Gödel had defined the limits of our ability to conquer the intellectual world of mathematics and logic with the publication of his Undecidability Theorem, the German physicist Werner Heisenberg’s celebrated Uncertainty Principle had delineated the limits of inquiry into the physical world, thereby undoing the efforts of another celebrated intellect, the great mathematician Pierre-Simon Laplace. In the early 1800s Laplace had worked extensively to demonstrate the purely mechanical and predictable nature of planetary motion. He later extended this theory to the interaction of molecules. In the Laplacean view, molecules are just as subject to the laws of physical mechanics as the planets are. In theory, if we knew the position and velocity of each molecule, we could trace its path as it interacted with other molecules, and trace the course of the physical universe at the most fundamental level. Laplace envisioned a world of ever more precise prediction, where the laws of physical mechanics would be able to forecast nature in increasing detail and ever further into the future, a world where “the phenomena of nature can be reduced in the last analysis to actions at a distance between molecule and molecule.”

What Gödel did to the work of Russell and Whitehead, Heisenberg did to Laplace’s concept of causality. The Uncertainty Principle, though broadly applied and draped in metaphysical context, is a well-defined and elegantly simple statement of physical reality – namely, the combined accuracy of a measurement of an electron’s location and its momentum cannot vary far from a fixed value. The reason for this, viewed from the standpoint of classical physics, is that accurately measuring the position of an electron requires illuminating the electron with light of a very short wavelength. But the shorter the wavelength the greater the amount of energy that hits the electron, and the greater the energy hitting the electron the greater the impact on its velocity.

What is true in the subatomic sphere ends up being true – though with rapidly diminishing significance – for the macroscopic. Nothing can be measured with complete precision as to both location and velocity because the act of measuring alters the physical properties. The idea that if we know the present we can calculate the future was proven invalid – not because of a shortcoming in our knowledge of mechanics, but because the premise that we can perfectly know the present was proven wrong. These limits to measurement imply limits to prediction. After all, if we cannot know even the present with complete certainty, we cannot unfailingly predict the future. It was with this in mind that Heisenberg, ecstatic about his yet-to-be-published paper, exclaimed, “I think I have refuted the law of causality.”

The epistemological extrapolation of Heisenberg’s work was that the root of the problem was man – or, more precisely, man’s examination of nature, which inevitably impacts the natural phenomena under examination so that the phenomena cannot be objectively understood. Heisenberg’s principle was not something that was inherent in nature; it came from man’s examination of nature, from man becoming part of the experiment. (So in a way the Uncertainty Principle, like Gödel’s Undecidability Proposition, rested on self-referentiality.) While it did not directly refute Einstein’s assertion against the statistical nature of the predictions of quantum mechanics that “God does not play dice with the universe,” it did show that if there were a law of causality in nature, no one but God would ever be able to apply it. The implications of Heisenberg’s Uncertainty Principle were recognized immediately, and it became a simple metaphor reaching beyond quantum mechanics to the broader world.

This metaphor extends neatly into the world of financial markets. In the purely mechanistic universe of classical physics, we could apply Newtonian laws to project the future course of nature, if only we knew the location and velocity of every particle. In the world of finance, the elementary particles are the financial assets. In a purely mechanistic financial world, if we knew the position each investor has in each asset and the ability and willingness of liquidity providers to take on those assets in the event of a forced liquidation, we would be able to understand the market’s vulnerability. We would have an early-warning system for crises. We would know which firms are subject to a liquidity cycle, and which events might trigger that cycle. We would know which markets are being overrun by speculative traders, and thereby anticipate tactical correlations and shifts in the financial habitat. The randomness of nature and economic cycles might remain beyond our grasp, but the primary cause of market crisis, and the part of market crisis that is of our own making, would be firmly in hand.

The first step toward the Laplacean goal of complete knowledge is the advocacy by certain financial market regulators to increase the transparency of positions. Politically, that would be a difficult sell – as would any kind of increase in regulatory control. Practically, it wouldn’t work. Just as the atomic world turned out to be more complex than Laplace conceived, the financial world may be similarly complex and not reducible to a simple causality. The problems with position disclosure are many. Some financial instruments are complex and difficult to price, so it is impossible to measure precisely the risk exposure. Similarly, in hedge positions a slight error in the transmission of one part, or asynchronous pricing of the various legs of the strategy, will grossly misstate the total exposure. Indeed, the problems and inaccuracies in using position information to assess risk are exemplified by the fact that major investment banking firms choose to use summary statistics rather than position-by-position analysis for their firmwide risk management despite having enormous resources and computational power at their disposal.

Perhaps more importantly, position transparency also has implications for the efficient functioning of the financial markets beyond the practical problems involved in its implementation. The problems in the examination of elementary particles in the financial world are the same as in the physical world: Beyond the inherent randomness and complexity of the systems, there are simply limits to what we can know. To say that we do not know something is as much a challenge as it is a statement of the state of our knowledge. If we do not know something, that presumes that either it is not worth knowing or it is something that will be studied and eventually revealed. It is the hubris of man that all things are discoverable. But for all the progress that has been made, perhaps even more exciting than the rolling back of the boundaries of our knowledge is the identification of realms that can never be explored. A sign in Einstein’s Princeton office read, “Not everything that counts can be counted, and not everything that can be counted counts.”

The behavioral analogue to the Uncertainty Principle is obvious. There are many psychological inhibitions that lead people to behave differently when they are observed than when they are not. For traders it is a simple matter of dollars and cents that will lead them to behave differently when their trades are open to scrutiny. Beneficial though it may be for the liquidity demander and the investor, for the liquidity supplier trans- parency is bad. The liquidity supplier does not intend to hold the position for a long time, like the typical liquidity demander might. Like a market maker, the liquidity supplier will come back to the market to sell off the position – ideally when there is another investor who needs liquidity on the other side of the market. If other traders know the liquidity supplier’s positions, they will logically infer that there is a good likelihood these positions shortly will be put into the market. The other traders will be loath to be the first ones on the other side of these trades, or will demand more of a price concession if they do trade, knowing the overhang that remains in the market.

This means that increased transparency will reduce the amount of liquidity provided for any given change in prices. This is by no means a hypothetical argument. Frequently, even in the most liquid markets, broker-dealer market makers (liquidity providers) use brokers to enter their market bids rather than entering the market directly in order to preserve their anonymity.

The more information we extract to divine the behavior of traders and the resulting implications for the markets, the more the traders will alter their behavior. The paradox is that to understand and anticipate market crises, we must know positions, but knowing and acting on positions will itself generate a feedback into the market. This feedback often will reduce liquidity, making our observations less valuable and possibly contributing to a market crisis. Or, in rare instances, the observer/feedback loop could be manipulated to amass fortunes.

One might argue that the physical limits of knowledge asserted by Heisenberg’s Uncertainty Principle are critical for subatomic physics, but perhaps they are really just a curiosity for those dwelling in the macroscopic realm of the financial markets. We cannot measure an electron precisely, but certainly we still can “kind of know” the present, and if so, then we should be able to “pretty much” predict the future. Causality might be approximate, but if we can get it right to within a few wavelengths of light, that still ought to do the trick. The mathematical system may be demonstrably incomplete, and the world might not be pinned down on the fringes, but for all practical purposes the world can be known.

Unfortunately, while “almost” might work for horseshoes and hand grenades, 30 years after Gödel and Heisenberg yet a third limitation of our knowledge was in the wings, a limitation that would close the door on any attempt to block out the implications of microscopic uncertainty on predictability in our macroscopic world. Based on observations made by Edward Lorenz in the early 1960s and popularized by the so-called butterfly effect – the fanciful notion that the beating wings of a butterfly could change the predictions of an otherwise perfect weather forecasting system – this limitation arises because in some important cases immeasurably small errors can compound over time to limit prediction in the larger scale. Half a century after the limits of measurement and thus of physical knowledge were demonstrated by Heisenberg in the world of quantum mechanics, Lorenz piled on a result that showed how microscopic errors could propagate to have a stultifying impact in nonlinear dynamic systems. This limitation could come into the forefront only with the dawning of the computer age, because it is manifested in the subtle errors of computational accuracy.

The essence of the butterfly effect is that small perturbations can have large repercussions in massive, random forces such as weather. Edward Lorenz was testing and tweaking a model of weather dynamics on a rudimentary vacuum-tube computer. The program was based on a small system of simultaneous equations, but seemed to provide an inkling into the variability of weather patterns. At one point in his work, Lorenz decided to examine in more detail one of the solutions he had generated. To save time, rather than starting the run over from the beginning, he picked some intermediate conditions that had been printed out by the computer and used those as the new starting point. The values he typed in were the same as the values held in the original simulation at that point, so the results the simulation generated from that point forward should have been the same as in the original; after all, the computer was doing exactly the same operations. What he found was that as the simulated weather pattern progressed, the results of the new run diverged, first very slightly and then more and more markedly, from those of the first run. After a point, the new path followed a course that appeared totally unrelated to the original one, even though they had started at the same place.

Lorenz at first thought there was a computer glitch, but as he investigated further, he discovered the basis of a limit to knowledge that rivaled that of Heisenberg and Gödel. The problem was that the numbers he had used to restart the simulation had been reentered based on his printout from the earlier run, and the printout rounded the values to three decimal places while the computer carried the values to six decimal places. This rounding, clearly insignificant at first, promulgated a slight error in the next-round results, and this error grew with each new iteration of the program as it moved the simulation of the weather forward in time. The error doubled every four simulated days, so that after a few months the solutions were going their own separate ways. The slightest of changes in the initial conditions had traced out a wholly different pattern of weather.

Intrigued by his chance observation, Lorenz wrote an article entitled “Deterministic Nonperiodic Flow,” which stated that “nonperiodic solutions are ordinarily unstable with respect to small modifications, so that slightly differing initial states can evolve into considerably different states.” Translation: Long-range weather forecasting is worthless. For his application in the narrow scientific discipline of weather prediction, this meant that no matter how precise the starting measurements of weather conditions, there was a limit after which the residual imprecision would lead to unpredictable results, so that “long-range forecasting of specific weather conditions would be impossible.” And since this occurred in a very simple laboratory model of weather dynamics, it could only be worse in the more complex equations that would be needed to properly reflect the weather. Lorenz discovered the principle that would emerge over time into the field of chaos theory, where a deterministic system generated with simple nonlinear dynamics unravels into an unrepeated and apparently random path.

The simplicity of the dynamic system Lorenz had used suggests a far-reaching result: Because we cannot measure without some error (harking back to Heisenberg), for many dynamic systems our forecast errors will grow to the point that even an approximation will be out of our hands. We can run a purely mechanistic system that is designed with well-defined and apparently well-behaved equations, and it will move over time in ways that cannot be predicted and, indeed, that appear to be random. This gets us to Santa Fe.

The principal conceptual thread running through the Santa Fe research asks how apparently simple systems, like that discovered by Lorenz, can produce rich and complex results. Its method of analysis in some respects runs in the opposite direction of the usual path of scientific inquiry. Rather than taking the complexity of the world and distilling simplifying truths from it, the Santa Fe Institute builds a virtual world governed by simple equations that when unleashed explode into results that generate unexpected levels of complexity.

In economics and finance, institute’s agenda was to create artificial markets with traders and investors who followed simple and reasonable rules of behavior and to see what would happen. Some of the traders built into the model were trend followers, others bought or sold based on the difference between the market price and perceived value, and yet others traded at random times in response to liquidity needs. The simulations then printed out the paths of prices for the various market instruments. Qualitatively, these paths displayed all the richness and variation we observe in actual markets, replete with occasional bubbles and crashes. The exercises did not produce positive results for predicting or explaining market behavior, but they did illustrate that it is not hard to create a market that looks on the surface an awful lot like a real one, and to do so with actors who are following very simple rules. The mantra is that simple systems can give rise to complex, even unpredictable dynamics, an interesting converse to the point that much of the complexity of our world can – with suitable assumptions – be made to appear simple, summarized with concise physical laws and equations.

The systems explored by Lorenz were deterministic. They were governed definitively and exclusively by a set of equations where the value in every period could be unambiguously and precisely determined based on the values of the previous period. And the systems were not very complex. By contrast, whatever the set of equations are that might be divined to govern the financial world, they are not simple and, furthermore, they are not deterministic. There are random shocks from political and economic events and from the shifting preferences and attitudes of the actors. If we cannot hope to know the course of the deterministic systems like fluid mechanics, then no level of detail will allow us to forecast the long-term course of the financial world, buffeted as it is by the vagaries of the economy and the whims of psychology.

Historicism. Thought of the Day 79.0

Historicism is a relativist hermeneutics, which postulates the incommensurability of historical epochs or cultural formations and therefore denies the possibility of a general history or trans-cultural universals. Best described as “a critical movement insisting on the prime importance of historical context” to the interpretation of texts, actions and institutions, historicism emerges in reaction against both philosophical rationalism and scientific theory (Paul Hamilton – Historicism). According to Paul Hamilton’s general introduction:

Anti-Enlightenment historicism develops a characteristically double focus. Firstly, it is concerned to situate any statement – philosophical, historical, aesthetic, or whatever – in its historical context. Secondly, it typically doubles back on itself to explore the extent to which any historical enterprise inevitably reflects the interests and bias of the period in which it was written … [and] it is equally suspicious of its own partisanship.

It is sometimes supposed that a strategy of socio-historical contextualisation represents the alpha and omega of materialist analysis – e.g. Jameson’s celebrated claim (Fredric Jameson – The Political Unconscious) that “always historicise” is the imperative of historical materialism. On the contrary, that although necessary, contextualisation alone is radically insufficient. This strategy of historical contextualisation, suffers from three serious defects. The historicist problematic depends upon the reduction of every phenomenal field to an immanent network of differential relations and the consequent evacuation of the category of cause from its theoretical armoury (Joan Copjec-Read My Desire: Lacan against the Historicists). It is therefore unable to theorise the hierarchy of effective causes within an overdetermined phenomenon and must necessarily reduce to a descriptive list, progressively renouncing explanation for interpretation. Secondly, lacking a theoretical explanation of the unequal factors overdetermining a phenomenon, historicism necessarily flattens the causal network surrounding its object into a homogeneous field of co-equal components. As a consequence, historicism’s description of the social structure or historical sequence gravitates in the direction of a simple totality, where everything can be directly connected to everything else. Thirdly, the self-reflexive turn to historical inscription of the researcher’s position of enunciation into the contextual field results, on these assumptions, in a gesture of relativisation that cannot stop short of relativism. The familiar performative contradictions of relativism then ensure that historicism must support itself through an explicit or implicit appeal to a neutral metalinguistic framework, which typically takes the form of a historical master narrative or essentialist conception of the social totality. The final result of the historicist turn, therefore, is that this “materialist” analysis is in actuality a form of spiritual holism.

Historicism relies upon a variant of what Althusser called “expressive causality,” which acts through “the primacy of the whole as an essence of which the parts are no more than the phenomenal expressions” (Althusser & Balibar – Reading Capital). Expressive causality postulates an essential principle whose epiphenomenal expressions are microcosms of the whole. Whether this expressive totality is social or historical is a contingent question of theoretical preference. When the social field is regarded as an expressive totality, the institutional structures of a historical epoch – economy, politics, law, culture, philosophy and so on – are viewed as externalisations of an essential principle that is manifest in the apparent complexity of these phenomena. When the historical process is considered to be an expressive totality, a historical master narrative operates to guarantee that the successive historical epochs represent the unfolding of a single essential principle. Formally speaking, the problem with expressive (also known as “organic” and “spiritual”) totalities is that they postulate a homology between all the phenomena of the social totality, so that the social practices characteristic of the distinct structural instances of the complex whole of the social formation are regarded as secretly “the same”.

Grothendieck’s Universes and Wiles Proof (Fermat’s Last Theorem). Thought of the Day 77.0

In formulating the general theory of cohomology Grothendieck developed the concept of a universe – a collection of sets large enough to be closed under any operation that arose. Grothendieck proved that the existence of a single universe is equivalent over ZFC to the existence of a strongly inaccessible cardinal. More precisely, 𝑈 is the set 𝑉_𝛼 of all sets with rank below 𝛼 for some uncountable strongly inaccessible cardinal.

Colin McLarty summarised the general situation:

Large cardinals as such were neither interesting nor problematic to Grothendieck and this paper shares his view. For him they were merely legitimate means to something else. He wanted to organize explicit calculational arithmetic into a geometric conceptual order. He found ways to do this in cohomology and used them to produce calculations which had eluded a decade of top mathematicians pursuing the Weil conjectures. He thereby produced the basis of most current algebraic geometry and not only the parts bearing on arithmetic. His cohomology rests on universes but weaker foundations also suffice at the loss of some of the desired conceptual order.

The applications of cohomology theory implicitly rely on universes. Most number theorists regard the applications as requiring much less than their ‘on their face’ strength and in particular believe the large cardinal appeals are ‘easily eliminable’. There are in fact two issues. McLarty writes:

Wiles’s proof uses hard arithmetic some of which is on its face one or two orders above PA, and it uses functorial organizing tools some of which are on their face stronger than ZFC.

There are two current programs for verifying in detail the intuition that the formal requirements for Wiles proof of Fermat’s last theorem can be substantially reduced. On the one hand, McLarty’s current work aims to reduce the ‘on their face’ strength of the results in cohomology from large cardinal hypotheses to finite order Peano. On the other hand Macintyre aims to reduce the ‘on their face’ strength of results in hard arithmetic to Peano. These programs may be complementary or a full implementation of Macintyre’s might avoid the first.

McLarty reduces

1. ‘ all of SGA (Revêtements Étales et Groupe Fondamental)’ to Bounded Zermelo plus a Universe.
2. “‘the currently existing applications” to Bounded Zermelo itself, thus the con-sistency strength of simple type theory.’ The Grothendieck duality theorem and others like it become theorem schema.

The essential insight of the McLarty’s papers on cohomology is the role of replacement in giving strength to the universe hypothesis. A 𝑍𝐶-universe is defined to be a transitive set U modeling 𝑍𝐶 such that every subset of an element of 𝑈 is itself an element of 𝑈. He remarks that any 𝑉_𝛼 for 𝛼 a limit ordinal is provable in 𝑍𝐹𝐶 to be a 𝑍𝐶-universe. McLarty then asserts the essential use of replacement in the original Grothendieck formulation is to prove: For an arbitrary ring 𝑅 every module over 𝑅 embeds in an injective 𝑅-module and thus injective resolutions exist for all 𝑅-modules. But he gives a proof in a system with the proof theoretic strength of finite order arithmetic that every sheaf of modules on any small site has an infinite resolution.

Angus Macintyre dismisses with little comment the worries about the use of ‘large-structure’ tools in Wiles proof. He begins his appendix,

At present, all roads to a proof of Fermat’s Last Theorem pass through some version of a Modularity Theorem (generically MT) about elliptic curves defined over Q . . . A casual look at the literature may suggest that in the formulation of MT (or in some of the arguments proving whatever version of MT is required) there is essential appeal to higher-order quantification, over one of the following.

He then lists such objects as C, modular forms, Galois representations …and summarises that a superficial formulation of MT would be 𝛱¹_m for some small 𝑚. But he continues,

I hope nevertheless that the present account will convince all except professional sceptics that MT is really 𝛱⁰₁.

There then follows a 13 page highly technical sketch of an argument for the proposition that MT can be expressed by a sentence in 𝛱⁰₁ along with a less-detailed strategy for proving MT in PA.

Macintyre’s complexity analysis is in traditional proof theoretic terms. But his remark that ‘genus’ is more a useful geometric classification of curves than the syntactic notion of degree suggests that other criteria may be relevant. McLarty’s approach is not really a meta-theorem, but a statement that there was only one essential use of replacement and it can be eliminated. In contrast, Macintyre argues that ‘apparent second order quantification’ can be replaced by first order quantification. But the argument requires deep understanding of the number theory for each replacement in a large number of situations. Again, there is no general theorem that this type of result is provable in PA.

Appropriation of (Ir)reversibility of Noise Fluctuations to (Un)Facilitate Complexity

 

The logical depth is a suitable measure of subjective complexity for physical as well as mathematical objects. this, upon considering the effect of irreversibility, noise, and spatial symmetries of the equations of motion and initial conditions on the asymptotic depth-generating abilities of model systems.

“Self-organization” suggests a spontaneous increase of complexity occurring in a system with simple, generic (e.g. spatially homogeneous) initial conditions. The increase of complexity attending a computation, by contrast, is less remarkable because it occurs in response to special initial conditions. An important question, which would have interested Turing, is whether self-organization is an asymptotically qualitative phenomenon like phase transitions. In other words, are there physically reasonable models in which complexity, appropriately defined, not only increases, but increases without bound in the limit of infinite space and time? A positive answer to this question would not explain the natural history of our particular finite world, but would suggest that its quantitative complexity can legitimately be viewed as an approximation to a well-defined qualitative property of infinite systems. On the other hand, a negative answer would suggest that our world should be compared to chemical reaction-diffusion systems (e.g. Belousov-Zhabotinsky), which self-organize on a macroscopic, but still finite scale, or to hydrodynamic systems which self-organize on a scale determined by their boundary conditions.

The suitability of logical depth as a measure of physical complexity depends on the assumed ability (“physical Church’s thesis”) of Turing machines to simulate physical processes, and to do so with reasonable efficiency. Digital machines cannot of course integrate a continuous system’s equations of motion exactly, and even the notion of computability is not very robust in continuous systems, but for realistic physical systems, subject throughout their time development to finite perturbations (e.g. electromagnetic and gravitational) from an uncontrolled environment, it is plausible that a finite-precision digital calculation can approximate the motion to within the errors induced by these perturbations. Empirically, many systems have been found amenable to “master equation” treatments in which the dynamics is approximated as a sequence of stochastic transitions among coarse-grained microstates.

We concentrate arbitrarily on cellular automata, in the broad sense of discrete lattice models with finitely many states per site, which evolve according to a spatially homogeneous local transition rule that may be deterministic or stochastic, reversible or irreversible, and synchronous (discrete time) or asynchronous (continuous time, master equation). Such models cover the range from evidently computer-like (e.g. deterministic cellular automata) to evidently material-like (e.g. Ising models) with many gradations in between.

More of the favorable properties need to be invoked to obtain “self-organization,” i.e. nontrivial computation from a spatially homogeneous initial condition. A rather artificial system (a cellular automaton which is stochastic but noiseless, in the sense that it has the power to make purely deterministic as well as random decisions) undergoes this sort of self-organization. It does so by allowing the nucleation and growth of domains, within each of which a depth-producing computation begins. When two domains collide, one conquers the other, and uses the conquered territory to continue its own depth-producing computation (a computation constrained to finite space, of course, cannot continue for more than exponential time without repeating itself). To achieve the same sort of self-organization in a truly noisy system appears more difficult, partly because of the conflict between the need to encourage fluctuations that break the system’s translational symmetry, while suppressing fluctuations that introduce errors in the computation.

Irreversibility seems to facilitate complex behavior by giving noisy systems the generic ability to correct errors. Only a limited sort of error-correction is possible in microscopically reversible systems such as the canonical kinetic Ising model. Minority fluctuations in a low-temperature ferromagnetic Ising phase in zero field may be viewed as errors, and they are corrected spontaneously because of their potential energy cost. This error correcting ability would be lost in nonzero field, which breaks the symmetry between the two ferromagnetic phases, and even in zero field it gives the Ising system the ability to remember only one bit of information. This limitation of reversible systems is recognized in the Gibbs phase rule, which implies that under generic conditions of the external fields, a thermodynamic system will have a unique stable phase, all others being metastable. Even in reversible systems, it is not clear why the Gibbs phase rule enforces as much simplicity as it does, since one can design discrete Ising-type systems whose stable phase (ground state) at zero temperature simulates an aperiodic tiling of the plane, and can even get the aperiodic ground state to incorporate (at low density) the space-time history of a Turing machine computation. Even more remarkably, one can get the structure of the ground state to diagonalize away from all recursive sequences.

String’s Depth of Burial

A string’s depth might be defined as the execution time of its minimal program.

The difficulty with this definition arises in cases where the minimal program is only a few bits smaller than some much faster program, such as a print program, to compute the same output x. In this case, slight changes in x may induce arbitrarily large changes in the run time of the minimal program, by changing which of the two competing programs is minimal. Analogous instability manifests itself in translating programs from one universal machine to another. This instability emphasizes the essential role of the quantity of buried redundancy, not as a measure of depth, but as a certifier of depth. In terms of the philosophy-of-science metaphor, an object whose minimal program is only a few bits smaller than its print program is like an observation that points to a nontrivial hypothesis, but with only a low level of statistical confidence.

To adequately characterize a finite string’s depth one must therefore consider the amount of buried redundancy as well as the depth of its burial. A string’s depth at significance level s might thus be defined as that amount of time complexity which is attested by s bits worth of buried redundancy. This characterization of depth may be formalized in several ways.

A string’s depth at significance level s be defined as the time required to compute the string by a program no more than s bits larger than the minimal program.

This definition solves the stability problem, but is unsatisfactory in the way it treats multiple programs of the same length. Intuitively, 2^k distinct (n + k)-bit programs that compute same output ought to be accorded the same weight as one n-bit program; but, by the present definition, they would be given no more weight than one (n + k)-bit program.

A string’s depth at signicifcance level s depth might be defined as the time t required for the string’s time-bounded algorithmic probability P_t(x) to rise to within a factor 2^−s of its asymptotic time-unbounded value P(x).

This formalizes the notion that for the string to have originated by an effective process of t steps or fewer is less plausible than for the first s tosses of a fair coin all to come up heads.

It is not known whether there exist strings that are deep, in other words, strings having no small fast programs, even though they have enough large fast programs to contribute a significant fraction of their algorithmic probability. Such strings might be called deterministically deep but probabilistically shallow, because their chance of being produced quickly in a probabilistic computation (e.g. one where the input bits of U are supplied by coin tossing) is significant compared to their chance of being produced slowly. The question of whether such strings exist is probably hard to answer because it does not relativize uniformly. Deterministic and probabilistic depths are not very different relative to a random coin-toss oracle A of the equality of random-oracle-relativized deterministic and probabilistic polynomial time complexity classes; but they can be very different relative to an oracle B deliberately designed to hide information from deterministic computations (this parallels Hunt’s proof that deterministic and probabilistic polynomial time are unequal relative to such an oracle).

(Depth of Finite Strings): Let x and w be strings and s a significance parameter. A string’s depth at significance level s, denoted D_s(x), will be defined as min{T(p) : (|p|−|p^∗| < s)∧(U(p) = x)}, the least time required to compute it by a s-incompressible program. At any given significance level, a string will be called t-deep if its depth exceeds t, and t-shallow otherwise.

The difference between this definition and the previous one is rather subtle philosophically and not very great quantitatively. Philosophically, when each individual hypothesis for the rapid origin of x is implausible at the 2^−s confidence level, then it requires only that a weighted average of all such hypotheses be implausible.

There exist constants c₁ and c₂ such that for any string x, if programs running in time ≤ t contribute a fraction between 2^−s and 2^−s+1 of the string’s total algorithmic probability, then x has depth at most t at significance level s + c₁ and depth at least t at significance level s − min{H(s), H(t)} − c².

Proof : The first part follows easily from the fact that any k-compressible self-delimiting program p is associated with a unique, k − O(1) bits shorter, program of the form “execute the result of executing p∗”. Therefore there exists a constant c₁ such that if all t-fast programs for x were s + c₁– compressible, the associated shorter programs would contribute more than the total algorithmic probability of x. The second part follows because, roughly, if fast programs contribute only a small fraction of the algorithmic probability of x, then the property of being a fast program for x is so unusual that no program having that property can be random. More precisely, the t-fast programs for x constitute a finite prefix set, a superset S of which can be computed by a program of size H(x) + min{H(t), H(s)} + O(1) bits. (Given x∗ and either t∗ or s∗, begin enumerating all self-delimiting programs that compute x, in order of increasing running time, and quit when either the running time exceeds t or the accumulated measure of programs so far enumerated exceeds 2^{−(H(x)−s)}). Therefore there exists a constant c₂ such that, every member of S, and thus every t-fast program for x, is compressible by at least s − min{H(s), H(t)} − O(1) bits.

The ability of universal machines to simulate one another efficiently implies a corresponding degree of machine-independence for depth: for any two efficiently universal machines of the sort considered here, there exists a constant c and a linear polynomial L such that for any t, strings whose (s+c)-significant depth is at least L(t) on one machine will have s-significant depth at least t on the other.

Depth of one string relative to another may be defined analogously, and represents the plausible time required to produce one string, x, from another, w.

(Relative Depth of Finite Strings): For any two strings w and x, the depth of x relative to w at significance level s, denoted D_s(x/w), will be defined as min{T(p, w) : (|p|−|(p/w)∗| < s)∧(U(p, w) = x)}, the least time required to compute x from w by a program that is s-incompressible relative to w.

Depth of a string relative to its length is a particularly useful notion, allowing us, as it were, to consider the triviality or nontriviality of the “content” of a string (i.e. its bit sequence), independent of its “form” (length). For example, although the infinite sequence 000… is intuitively trivial, its initial segment 0ⁿ is deep whenever n is deep. However, 0ⁿ is always shallow relative to n, as is, with high probability, a random string of length n.

In order to adequately represent the intuitive notion of stored mathematical work, it is necessary that depth obey a “slow growth” law, i.e. that fast deterministic processes be unable to transform a shallow object into a deep one, and that fast probabilistic processes be able to do so only with low probability.

(Slow Growth Law): Given any data string x and two significance parameters s₂ > s₁, a random program generated by coin tossing has probability less than 2^{−(s2−s1)+O(1)} of transforming x into an excessively deep output, i.e. one whose s₂-significant depth exceeds the s₁-significant depth of x plus the run time of the transforming program plus O(1). More precisely, there exist positive constants c₁, c₂ such that for all strings x, and all pairs of significance parameters s₂ > s₁, the prefix set {q : D_s2(U(q, x)) > D_s1(x) + T(q, x) + c₁} has measure less than 2^{−(s₂−s₁)+c₂.}

Proof: Let p be a s₁-incompressible program which computes x in time D_s1(x), and let r be the restart prefix mentioned in the definition of the U machine. Let Q be the prefix set {q : D_s2(U(q, x)) > T(q, x) + D_s1(x) + c₁}, where the constant c₁ is sufficient to cover the time overhead of concatenation. For all q ∈ Q, the program rpq by definition computes some deep result U(q, x) in less time than that result’s own s₂-significant depth, and so rpq must be compressible by s₂ bits. The sum of the algorithmic probabilities of strings of the form rpq, where q ∈ Q, is therefore

Σ_q∈Q P(rpq)< Σ_q∈Q 2^{−|rpq| + s₂} = 2^{−|r|−|p|+s2} μ(Q)

On the other hand, since the self-delimiting program p can be recovered from any string of the form rpq (by deleting r and executing the remainder pq until halting occurs, by which time exactly p will have been read), the algorithmic probability of p is at least as great (within a constant factor) as the sum of the algorithmic probabilities of the strings {rpq : q ∈ Q} considered above:

P(p) > μ(Q) · 2^{−|r|−|p|+s2−O(1)}

Recalling the fact that minimal program size is equal within a constant factor to the −log of algorithmic probability, and the s₁-incompressibility of p, we have P(p) < 2^{−(|p|−s1+O(1))}, and therefore finally

μ(Q) < 2^{−(s₂−s₁)+O(1)}, which was to be demonstrated.

Regulating the Velocities of Dark Pools. Thought of the Day 72.0

On 22 September 2010 the SEC chair Mary Schapiro signaled US authorities were considering the introduction of regulations targeted at HFT:

…High frequency trading firms have a tremendous capacity to affect the stability and integrity of the equity markets. Currently, however, high frequency trading firms are subject to very little in the way of obligations either to protect that stability by promoting reasonable price continuity in tough times, or to refrain from exacerbating price volatility.

However regulating an industry working towards moving as fast as the speed of light is no ordinary administrative task: – Modern finance is undergoing a fundamental transformation. Artificial intelligence, mathematical models, and supercomputers have replaced human intelligence, human deliberation, and human execution…. Modern finance is becoming cyborg finance – an industry that is faster, larger, more complex, more global, more interconnected, and less human. C W Lin proposes a number of principles for regulating this cyber finance industry:

1. Update antiquated paradigms of reasonable investors and compartmentalised institutions, and confront the emerging institutional realities, and realise the old paradigms of governance of markets may be ill-suited for the new finance industry;
2. Enhance disclosure which recognises the complexity and technological capacities of the new finance industry;
3. Adopt regulations to moderate the velocities of finance realising that as these approach the speed of light they may contain more risks than rewards for the new financial industry;
4. Introduce smarter coordination harmonising financial regulation beyond traditional spaces of jurisdiction.

Electronic markets will require international coordination, surveillance and regulation. The high-frequency trading environment has the potential to generate errors and losses at a speed and magnitude far greater than that in a floor or screen-based trading environment… Moreover, issues related to risk management of these technology-dependent trading systems are numerous and complex and cannot be addressed in isolation within domestic financial markets. For example, placing limits on high-frequency algorithmic trading or restricting Un-filtered sponsored access and co-location within one jurisdiction might only drive trading firms to another jurisdiction where controls are less stringent.

In these regulatory endeavours it will be vital to remember that all innovation is not intrinsically good and might be inherently dangerous, and the objective is to make a more efficient and equitable financial system, not simply a faster system: Despite its fast computers and credit derivatives, the current financial system does not seem better at transferring funds from savers to borrowers than the financial system of 1910. Furthermore as Thomas Piketty‘s Capital in the Twenty-First Century amply demonstrates any thought of the democratisation of finance induced by the huge expansion of superannuation funds together with the increased access to finance afforded by credit cards and ATM machines, is something of a fantasy, since levels of structural inequality have endured through these technological transformations. The tragedy is that under the guise of technological advance and sophistication we could be destroying the capacity of financial markets to fulfil their essential purpose, as Haldane eloquently states:

An efficient capital market transfers savings today into investment tomorrow and growth the day after. In that way, it boosts welfare. Short-termism in capital markets could interrupt this transfer. If promised returns the day after tomorrow fail to induce saving today, there will be no investment tomorrow. If so, long-term growth and welfare would be the casualty.

Quantum Informational Biochemistry. Thought of the Day 71.0

A natural extension of the information-theoretic Darwinian approach for biological systems is obtained taking into account that biological systems are constituted in their fundamental level by physical systems. Therefore it is through the interaction among physical elementary systems that the biological level is reached after increasing several orders of magnitude the size of the system and only for certain associations of molecules – biochemistry.

In particular, this viewpoint lies in the foundation of the “quantum brain” project established by Hameroff and Penrose (Shadows of the Mind). They tried to lift quantum physical processes associated with microsystems composing the brain to the level of consciousness. Microtubulas were considered as the basic quantum information processors. This project as well the general project of reduction of biology to quantum physics has its strong and weak sides. One of the main problems is that decoherence should quickly wash out the quantum features such as superposition and entanglement. (Hameroff and Penrose would disagree with this statement. They try to develop models of hot and macroscopic brain preserving quantum features of its elementary micro-components.)

However, even if we assume that microscopic quantum physical behavior disappears with increasing size and number of atoms due to decoherence, it seems that the basic quantum features of information processing can survive in macroscopic biological systems (operating on temporal and spatial scales which are essentially different from the scales of the quantum micro-world). The associated information processor for the mesoscopic or macroscopic biological system would be a network of increasing complexity formed by the elementary probabilistic classical Turing machines of the constituents. Such composed network of processors can exhibit special behavioral signatures which are similar to quantum ones. We call such biological systems quantum-like. In the series of works Asano and others (Quantum Adaptivity in Biology From Genetics to Cognition), there was developed an advanced formalism for modeling of behavior of quantum-like systems based on theory of open quantum systems and more general theory of adaptive quantum systems. This formalism is known as quantum bioinformatics.

The present quantum-like model of biological behavior is of the operational type (as well as the standard quantum mechanical model endowed with the Copenhagen interpretation). It cannot explain physical and biological processes behind the quantum-like information processing. Clarification of the origin of quantum-like biological behavior is related, in particular, to understanding of the nature of entanglement and its role in the process of interaction and cooperation in physical and biological systems. Qualitatively the information-theoretic Darwinian approach supplies an interesting possibility of explaining the generation of quantum-like information processors in biological systems. Hence, it can serve as the bio-physical background for quantum bioinformatics. There is an intriguing point in the fact that if the information-theoretic Darwinian approach is right, then it would be possible to produce quantum information from optimal flows of past, present and anticipated classical information in any classical information processor endowed with a complex enough program. Thus the unified evolutionary theory would supply a physical basis to Quantum Information Biology.