Turing\'s Landscape: decidability, computability and complexity in string theory by Abhijnan Rej

Abhijnan Rej

Essay Abstract

I argue that questions of algorithmic decidability, computability and complexity should play a larger role in deciding the ``ultimate" theoretical description of the Landscape of string vacua. More specifically, I examine the notion of the average rank of the (unification) gauge group in the Landscape, the explicit construction of Ricci-flat metrics on Calabi-Yau manifolds as well as the computability of fundamental periods to show that undecidability questions are far more pervasive than that described in the work of Denef and Douglas.

Author Bio

Abhijnan Rej was educated in the United States with Bachelor's and Master's degrees in mathematics from the University of Connecticut. He has carried out doctoral research in mathematical physics at the Max-Planck-Institute for Mathematics in Bonn, Germany working on algebro-geometric aspects of quantum field theory and is scheduled to defend his thesis later this year. He has been a Marie-Curie Early Stage Research Fellow at Durham University (UK) and a research scholar of the Clay Mathematics Institute.

Download Essay PDF File

[deleted]

Your paper looks interesting. I too have a stringy or braney paper down below. Strings are in a sense cellular automata, or processors, and there probably are connections with computational theory.

Cheers LC

[deleted]

Dear Abhijnan,

Congratulations on an interesting paper. In mathematics people always find links between seemingly unrelated domains, and computability and decidability issues should make no exception. What I do not quite get is what this has to do with what is ultimately possible in physics? Do you want to claim that the landscape will be proven true or false by decidability considerations? According to Susskind, considerations of mathematical beauty or uniqueness should not play any role. Why would decidability be any different? In other words, what relevance would decidability or its lack of it has to do with proving or rejecting the landscape, or with extracting mathematical consequences from it?

Abhijnan Rej

LC and FM,

Thanks a lot for your interest and kind words!

LC,

Certainly cellular automata and computation theory are intimately related- certain CAs do give rise to NP-complete problems. What is not obvious to me is how we can rigorously convert questions about the string vacua into CA problems. (Actually most attempts to do actual "messy" physics on CAs turn out to be much more harder than anticipated, cf. Scott Aaranson's nice review of Wolfram's book.)

FM,

In my paper, I have tried to convey a belief that deciding the "right" point in the configuration of string vacua (whatever your notion of "right" may be, e.g. a point with a certain product of gauge groups arising from "exotic" D-brane configurations) may actually be a NP-complete decision problem. Denef and Douglas were the first to hint at this possibility and I have tried to add "mathematical firepower" to this argument.

Florin Moldoveanu

AR,

So now we should also add "NP complete" to "jury rigged" and "Rube Goldberg contraptions".

[deleted]

I have this program of looking at quantum information theory based on sphere packing. The 24-cell is the minimal sphere packing configuration in 4-dim space, which does predict the 26-dimensional bosonic string without the 2 tachyon vacuum modes. There is then further the Gosset polytope and E_8 on up to the Leech lattice. Each fundamental cell unit, say the Gossett polytope with 248 elements holds that many fundamental "letters" or units, and is then an elementary computational unit.

I don't particularly have an idea of searching for CA as the basis of string theory, but looking at quantum error correction codes as an underlying basis. This might lead to CA type of theory underneath things.

More later, I have been rather ill these last few days

Cheers LC

[deleted]

Dear Abhijnan,

Congratulations on your essay!

I have the following two non-technical questions.

The concluding two sentences of you essay are:

"Nevertheless, it is my belief that computation theory will play a larger role in any description of the Landscape in the years to come. If this is the case, it will certainly validate a [sic] often-repeated claim (cf. [23]) of the role of algorithmic decidablity [sic] in an 'ultimate' theory of the material universe."

First, can you indicate, please, the specific place(es) in [23] in which the 'claim of the role of algorithmic decidability in an 'ultimate' theory of the material universe' is made?

Second, you have not made the following point clear. Before the string theory 'mess', computability didn't play any role in physics, since the emphasis has always been, as it should be, on the structure of a physical model. As one might see from my essay and two of my papers mentioned there (ref. [11, 19]), I happened to believe that even in information processing the computability got foothold only temporarily due to the historically dominant role of logic in computer science and before the 'conventional' scientific considerations will enter the 'true' ;─) *science* of information processing , with the dominance of models for information processes *in nature*. So, the current state of string theory aside, do you really believe in the critical "role of algorithmic decidability in an 'ultimate' theory of the material universe"?

[deleted]

Dear Abhijnan Rej, I have been working my way through your essay. This requires some background review and examination to understand. I will say I suspect you might be right with the fractal geometry statement: "I will claim that the moduli space of metrics on a Calabi-Yau manifold has a fractal structure and argue, following the work of Nabutovsky and Weinberger, that there are several computability issues associated to the explicit construction of a Ricci-flat metric on a Calabi-Yau manifold." I tend to think along similar lines. As there is AdS_{d+1} ~ CFT, and that for d = 2 or 3 the AdS may be tessellated by octahedra or 120-cell or the dual 600-cell. These cells act as the generator of great arcs similar to the 2-dim case with Poincare disks. The recursive nature of these arcs has a chaotic dynamics to it.

The NP-complete nature of the Bousso-Polchinsky F_4 flux on D7-brane to compute the cosmological constant I find interesting. My paper below discusses how the comsological constant is due to a quantum critical point. I am intending to include a more comprehensive paper on this, where the FQXI paper is more of a survey of calculations. In what I work with I utilize K-theory and the wrapping of D-branes. I am not sure if this has a strong or weak intersection with what you have written up here.

I have a bit of a question about the Gromov-Hausdorff metric. This appears to be a measure in the moduli space. For general relativity the moduli space is non-Hausdorff and I am wondering how one works up convergence conditions (page 7 of your paper) in general. Of course your paper primarily works with Calabi-yau spaces, which have elliptical moduli. So if you could comment some on this it might be helpful.

Cheers,

Lawrence B. Crowell

Abhijnan Rej

LG,

In Max Tegmark's paper, Goedelian incompleteness is brought up impilicitly in discussion type IV "reality", in his terminology. Now it is a fact that over the years both responsible scientists and those could be, admittedly uncharitably, called "crackpots" have time and again brought up the issue of undecidability in physical theory. What I attempted to do (admittedly following up on the work of Fredrik Denef and Michael Douglas) is to say that with the string Landscape, because of its _combinatorial nature_, we finally have a testing ground for such ideas in the contest of a relevant and interesting physical question.

LC,

The convergence conditions in the work of Nabutovsky and Weinberger is rather subtle. They work with $\latex Al(M)$ and impose path metrics on it. In fact if you see the paper by Acharya and Douglas on the finiteness of the Landscape, you see a discussion of the GH metric. In my work I have conjectured the existence of an analog of $latex Al(M)$ in terms of the ample cone; recently purely mathematical results show that there is indeed a convergence in the Gromov-Hausdorff topology for CY metrics.

[deleted]

I looked into the prospect of incompleteness in physics some years back. To be honest the more I looked into it, even wrote a short paper on this back almost 20 years ago, the less attractive the idea became. It seems to me that Godelian incompleteness of physics might represent the end of physics. This might ultimately be the state of affairs at the Planck scale, or in some reciprocal sense the totality of the universe (multiverse etc) that Godel's theorem applies. However, I would like to think we could work physics properly before reaching that sort of wall.

In my paper I work on how the Bousso-Polchinski approach to the cosmological constant is best considered according to a quantum critical point. My FQXI paper gives a survey of the ideas involved. This is physics similar to the breakdown of the Landau-Fermi electron fluid near the divergence of a quasi-particle mass. Ultiamtely what underlies this is statistical mechanics or stat-quantum mechanics. The combinatorics of many states near a Fermi surface is not explicitly computable, but there are K-theoretic topological numbers involved.

I am looking at the Denef & Douglas paper and Acharya and Douglas paper, so I will try to figure out what is happening there. As near as I can see the Gromov metric is really a sequence of metrics which converge to some infimum.

Cheers LC

pjackson

I feel Lev Goldfarb had a very good point, which remains unanswered. Math can be a wonderful tool for description, and even exploration, but certainly not the only tool. We sometimes get too carried away in wonderment of it's supposed 'powers'.

The motion and interaction of the solar systems planets and moons is beautiful and logical. Does it make any difference to them if math can describe and predict them or not? Our most powerful computers are of course nowhere near being able to do so for even only 3 objects in motion, and an undiscovered comet or large asteroid could throw it all out anyway. Is math central to their action and future? Of course not. Can math describe how any person will react, how a butterfly wing flapping will change the weather? what a spaceman will do in any circumstance. No, and never. It will always remain incomplete.

This is not to criticise or degrade math but to remind us we have other very important tools, mainly in the infinite quantum potential of our minds. We are in danger of forgetting this by focussing purely on counting all our eggs into one spacially defined basket.

The road through strings and branes has been very interesting to explore, but there are always times we should take stock, step way back to get an overview of ALL aspects of our existence, learn the lessons, and only then move on, in whatever new ways we will perceive.

[deleted]

We have to remember that with physics we ultimately measure things, and these involve numbers. That is why we have mathematics. The same holds for even the most advanced of physics, where the idea of using Riemannian geometry or topology is to compute coupling strenths, orbits, scattering ampitudes, probabilities and so forth.

Cheers LC

Jayakar Joseph

Dear Abhijnan Rej,

I think the turing algorithm on string theory landscape differ in Lambda-CDM and Coherent-cyclic universe models with some variations due to the inconsistency of space-time, plank time and nondeterministic polynomial time. Hence the decidability on the formulation of logics varies in both models as the Coherent-cyclic universe model has the hierarchy of heterogeneous-matters in trifurcated tree structure, whereas in Lambda-CDM universe model all formalisms are for a homogeneous universe and thereby their computability also differ.

Though the unification gauge group is applicable for both models, the Coherent-cyclic universe model does not require any average unification gauge group as this model does not explain any multiverse. The minimal supersymmetric standard model has much adaptability for Coherent-cyclic universe model and we may need variant in supersymmetric string theory as the decidability of string vacua in supersymmetric string theory have some inconsistency for this model. Altogether this article provides a good explanation on the complexity of decidability for the computability of universe in both models. So interesting is in it...!

With best wishes,

Jayakar

[deleted]

Hello dear Mr Abhijnan Rej,

A very instructive paper for me who doesn't know well the computational and strings languages ,if I can say .

Yes ideed in this optic ,the complexity which is already important in the physicality ,becomes still more complex with these computations .

The mathematical method nevertheless is very interesting ,like the ones of Lawrence ,Florin and Ray and others I forgot of course some people ,perhaps you could write a paper in team ,I am persuaded you are going to ponder interesting new computational methods because of course the complemenatrity is essential to optimize systems even a human creation if I can say .

Good luck too for the contest .

Best Regards

Steve

[deleted]

Abhijnan Rej,

There are a number of articles here which brush on the issue which you present here with computation. I have steered a number of these authors, who I think are competent in physics, to your well written essay. My essay presents problems of quantum information and phase transitions with respect to this. It would be interesting to get a number of people dialoguing on these matters.

Cheers LC

[deleted]

Dear LC,

Thank you so much for all the publicity :-)

I agree with you that some of us should seriously discuss issues related to computation and $latex \Lambda$/multiverse but probably once the "noise" of the competition dies out a bit.

I think one result you might find useful is the NP-completeness of solving the general 3d Ising model (due to Sorin Istrail). Perhaps this has something useful for you?

Best,

[deleted]

Yes I will look up Sorin Istrail's paper. These issues are of course related to Ising problems, or lattice gauge problems, and I think in general with the physics of quantum matter. There quantum fluctuations domeinate the ordering of the system and determine the phase it exists within. This will be determined by quantum cricial points with interesting scaling principles.

I think that computational principles enter into the graph structure (nearest neighbor interactions etc) in discrete structures, whether this be spins in an Ising system, atoms and electrons with Skymrion physics, or four fluxes on D7-branes.

There is another essay which you might find ingeresting, It is Christian Corda's essay on gravity waves:

http://www.fqxi.org/community/forum/topic/477

I am a bit disheartened to see it fall below the 4.0 mark, as I think this is too a superior paper.

Cheers LC

[deleted]

I was unsuccessful at finding Istrail's papers. So you might have to steer me in the right direction or send these to me.

I don't know if you have considered in these analyses networks, such as Erdos or non-Erdos networks. For cluster analysis of phase transitions, where I think the cosmological constant is maybe fixed by a quantum critical point or transition, these matters might be very important.

Cheers LC

[deleted]

Dear Abhjnan Rej,

I am working my way through your interesting essay, but wondered if you had accidentally made a circular argument that will affect your conclusions.

Specifically, on page 3, you determine the average rank of a D3-brane as 16/5 ~ 3 or 16/4 = 4.

In my own models, I equate rank with dimensionality. Thus, our 3 1 dimensional spacetime has revealed the Standard Model with rank 2 1 1, but has not revealed the rank 4 Georgi-Glashow SU(5) GUT (because an unbroken 4-D Spacetime allows more phenomena than a broken 3-D Space 1-D Time).

My Yang-Mills models led me to consider a rank-4 SU(5) Georgi-Glashow, a rank-6 SU(7), a rank-10 SU(11) (Georgi also considered an SU(11))and a rank-12 SU(13). IF these Yang-Mills models are a proper way to consider gauge/ tensor unification, AND IF these gauge/ tensor ranks correspond to dimensions, then my model is 12 dimensional. (On a side note, if Emile Grgin and Florin Moldoveanu are correct about the relevance of quantions, then it seems unnatural to develop an odd-dimensioned 11-D M-theory out of even-dimensioned 2-D quantions. Now a 12 dimensional theory doesn't sound so radical.)

True, the D3-brane is relevant to our 3 1 dimensional spacetime, but I don't consider your extrapolations (based on your Ref [14]) into multiple dimensions to be any more foundational than my own (which are based on naturally-occurring crystalline symmetries).

I haven't finished reading your paper. I may have more observations or questions later.

Good luck in the contest!

Ray Munroe

[deleted]

Dear Abhijnan Rej,

I finally finished reading your interesting essay.

Regarding "computational complexity", Information Theory predicts complexity to scale as

N ln(N). If N~10500, then this is a huge amount of complexity that will overwhelm any computer network with "busy beaver function".

Conjecture 3.1 is interesting to me because it implies that spacetime may fundamentally be discrete rather than continuous. This connects with ideas by other essay authors: Hans-Thomas Elze, Constantin Zaharia Leshan, and me.

Regarding your periods, they may be related to my lattice symmetries, and seemingly offer the only hope of simplifying this to a practical computation. Without some way to greatly simplify the problem at hand, this computation is doomed to your "fairly grim picture of what we can know about the Landscape".

Good Luck in the contest and with your thesis!

Ray Munroe