Search FQXi


If you are aware of an interesting new academic paper (that has been published in a peer-reviewed journal or has appeared on the arXiv), a conference talk (at an official professional scientific meeting), an external blog post (by a professional scientist) or a news item (in the mainstream news media), which you think might make an interesting topic for an FQXi blog post, then please contact us at forums@fqxi.org with a link to the original source and a sentence about why you think that the work is worthy of discussion. Please note that we receive many such suggestions and while we endeavour to respond to them, we may not be able to reply to all suggestions.

Please also note that we do not accept unsolicited posts and we cannot review, or open new threads for, unsolicited articles or papers. Requests to review or post such materials will not be answered. If you have your own novel physics theory or model, which you would like to post for further discussion among then FQXi community, then please add them directly to the "Alternative Models of Reality" thread, or to the "Alternative Models of Cosmology" thread. Thank you.

Contests Home

Current Essay Contest


Contest Partners: Fetzer Franklin Fund, and The Peter and Patricia Gruber Foundation

Previous Contests

Undecidability, Uncomputability, and Unpredictability Essay Contest
December 24, 2019 - April 24, 2020
Contest Partners: Fetzer Franklin Fund, and The Peter and Patricia Gruber Foundation
read/discuss

What Is “Fundamental”
October 28, 2017 to January 22, 2018
Sponsored by the Fetzer Franklin Fund and The Peter & Patricia Gruber Foundation
read/discusswinners

Wandering Towards a Goal
How can mindless mathematical laws give rise to aims and intention?
December 2, 2016 to March 3, 2017
Contest Partner: The Peter and Patricia Gruber Fund.
read/discusswinners

Trick or Truth: The Mysterious Connection Between Physics and Mathematics
Contest Partners: Nanotronics Imaging, The Peter and Patricia Gruber Foundation, and The John Templeton Foundation
Media Partner: Scientific American

read/discusswinners

How Should Humanity Steer the Future?
January 9, 2014 - August 31, 2014
Contest Partners: Jaan Tallinn, The Peter and Patricia Gruber Foundation, The John Templeton Foundation, and Scientific American
read/discusswinners

It From Bit or Bit From It
March 25 - June 28, 2013
Contest Partners: The Gruber Foundation, J. Templeton Foundation, and Scientific American
read/discusswinners

Questioning the Foundations
Which of Our Basic Physical Assumptions Are Wrong?
May 24 - August 31, 2012
Contest Partners: The Peter and Patricia Gruber Foundation, SubMeta, and Scientific American
read/discusswinners

Is Reality Digital or Analog?
November 2010 - February 2011
Contest Partners: The Peter and Patricia Gruber Foundation and Scientific American
read/discusswinners

What's Ultimately Possible in Physics?
May - October 2009
Contest Partners: Astrid and Bruce McWilliams
read/discusswinners

The Nature of Time
August - December 2008
read/discusswinners

Forum Home
Introduction
Terms of Use

Order posts by:
 chronological order
 most recent first

Posts by the author are highlighted in orange; posts by FQXi Members are highlighted in blue.

By using the FQXi Forum, you acknowledge reading and agree to abide by the Terms of Use

 RSS feed | RSS help
RECENT POSTS IN THIS TOPIC

Gemma De las Cuevas: on 6/25/20 at 11:47am UTC, wrote Hi Rob, Thanks so much for reading the essay, and I'm really glad you...

Robert Spekkens: on 6/24/20 at 16:09pm UTC, wrote Hi Gemma, I really enjoyed your essay! I particularly appreciated...

Gemma De las Cuevas: on 5/14/20 at 13:58pm UTC, wrote Dear Markus, thank you so much for your comments! I'm so glad you enjoyed...

Markus Mueller: on 5/14/20 at 12:56pm UTC, wrote Dear Gemma, I enjoyed reading your essay immensely! I feel like I have...

Gemma De las Cuevas: on 5/14/20 at 7:08am UTC, wrote Hi Alyssa, thanks for reading my essay and I'm glad you enjoyed it! ...

Alyssa Adams: on 5/11/20 at 1:37am UTC, wrote Hi Gemma! This was a very fun read! I really love your point...

Gemma De las Cuevas: on 5/7/20 at 16:06pm UTC, wrote Dear Branko, Thanks for your comment, but I disagree. I don't think it's a...

Branko Zivlak: on 5/6/20 at 15:24pm UTC, wrote Dear Gemma De las Cuevas When I read the essays of young scientists a look...


RECENT FORUM POSTS

Charles Harrow: "The AI only works really well in the "comfort zone", i.e. under test..." in Is Causality Fundamental?

Jason Wolfe: "This is unification of QM and GR in a nut shell. Gravitons exist. They..." in The Nature of Time

Jason Wolfe: "The graviton is the mathematical solution to the Schrodinger's equation. ..." in The Nature of Time

Jason Wolfe: "In all honesty, I'm not even sure what intelligent and educated people..." in Generalised Integrated...

Jason Wolfe: "It would be nice to imagine that the Germans are working on gravity..." in Generalised Integrated...

Jason Wolfe: "Jim, If its physical, it can be perceived by the body, by physical things..." in Structure Invention by...

jim hughes: "Does the Standard Model have to be described as "physical"? I'd say it..." in Structure Invention by...

Jason Wolfe: "I think an event happens at a point, and the causal consequences travel..." in First Things First: The...


RECENT ARTICLES
click titles to read articles

Lockdown Lab Life
Grounded physicists are exploring the use of online and virtual-reality conferencing, and AI-controlled experiments, to maintain social distancing. Post-pandemic, these positive innovations could make science more accessible and environmentally-friendly.

Is Causality Fundamental?
Untangling how the human perception of cause-and-effect might arise from quantum physics, may help us understand the limits and the potential of AI.

Building Agency in the Biology Lab
Physicists are using optogenetics techniques to make a rudimentary agent, from cellular components, which can convert measurements into actions using light.

Think Quantum to Build Better AI
Investigating how quantum memory storage could aid machine learning and how quantum interactions with the environment may have played a role in evolution.

Outside the Box
A proposed quantum set-up that could predict your game-playing strategy resurrects Newcomb’s classic quiz show paradox.


FQXi FORUM
July 11, 2020

CATEGORY: Undecidability, Uncomputability, and Unpredictability Essay Contest (2019-2020) [back]
TOPIC: Universality Everywhere implies Undecidability Everywhere by Gemma De las Cuevas [refresh]
Bookmark and Share
Login or create account to post reply or comment.

Author Gemma De las Cuevas wrote on Apr. 24, 2020 @ 17:19 GMT
Essay Abstract

Why is it so easy to generate complexity? Because essentially every non-trivial system is universal, that is, capable of exploring all complexity in its domain. In this sense there is Universality Everywhere. Automata, spin models and neural networks are the best understood examples of systems that jump to universality, and I also discuss some more speculative ones. One crucial consequence of universality is that it allows for self-reference and negation, which gives rise to paradoxes such as ‘I am a liar’. The truth of this statement cannot be established — it is undecidable. The liar paradox is at the core of the undecidability results in automata, provability theory, set theory, truth theory and epistemology. It is a very powerful paradox which cannot be fixed in a finite way. Undecidability is thus an inescapable consequence of the expressive power of the system, that is, of universality. In this sense, Universality Everywhere implies Undecidability Everywhere. I discuss some conceptual and practical implications of undecidability, as well as perspectives of overcoming these limitations. I also argue that universality is a statement about the power of simulation, that is, of how much a system can reach with the help of additional variables, and I discuss the relation of this notion of universality with emergence.

Author Bio

Gemma De las Cuevas is an Assistant Professor at the Institute for Theoretical Physics of the University of Innsbruck (Austria). Her research is centered around mathematical physics and quantum many-body physics. She is also interested in the universality and undecidability notions presented in this essay.

Download Essay PDF File

Bookmark and Share


H.H.J. Luediger wrote on Apr. 24, 2020 @ 19:05 GMT
Dear Gemma De las Cuevas,

"The liar paradox is at the core of the undecidability results in automata, provability theory, set theory, truth theory and epistemology."

If the above assertion is at the heart of undecidability, the problem can be easily solved. Take for instance: 'All Cretes are liars said the Crete', which is a problem only in formal logic, i.e. when the Crete is considered an element of the set of Cretes. The Cretes as a people, however, belong to a different category than individual Cretes. So, the liar paradox speaks of a trait of the people of Crete expressed by an individual Crete, which is perfectly fine. In Tarski's words: the individual Crete speaks in meta-language about an object-language concerning the traits of the people of Crete. The same holds for "This sentence is false" or "I'm lying". In all those examples categorically separated instances play a role (which logicians and computers can not deal with for principled reasons).

The 'undecidability' illness was basically cured

a) by Gödel's (1931) incompleteness theorem, which states that Logic has no domain of applicability other than itself

b) by Tarski's (1935) theory of truth, which states that no object-language can discuss it's truths.

Some illnesses though seem to be fairly attractive...

Heinz

Bookmark and Share
report post as inappropriate
Author Gemma De las Cuevas replied on Apr. 25, 2020 @ 13:00 GMT
Dear Heinz,

Thank you for reading the essay and for your feedback.

As I understand, the solution you are proposing to the liar paradox is an example of (the first step in the construction) of a hierarchy to solve the paradox. Namely, you suggest that Cretes as people belong to a different category to individual Cretes, thereby establishing "two levels" which avoid self-reference. With these two levels, one can devise a new liar paradox (which will sound involved). Building hierarchies to escape the paradox is indeed the commonly adopted solution, as mentioned in my essay.

Regarding your two final comments, I am not exactly sure with what you mean in 1). Regarding 2) I agree that Tarski's theory of truth is a way of circumventing the paradox, but I don't think I agree with the statement that this cures the illness - for one reason, it is not a finite solution. (I recommend reading T. Bolander's entry on Self-reference in the Stanford Encyclopedia of Philosophy to learn about approaches to solve the liar paradox).

Thanks for your input again!

Best,

Gemma

Bookmark and Share

H.H.J. Luediger replied on Apr. 25, 2020 @ 16:56 GMT
Dear Gemma,

thanks for your reply, there seems to be some common ground...

As regards a) another way to express it is the generally accepted claim that logic has not solved its GROUNDING problem. When logic demands to be universally applicable (to any problem) it is equivalent to saying that it has no domain of applicability.

In my FQXI essays as of 2015 I have argued that legitimate domains, hierarchies or whatever one wants to call these categories are separated by orthogonality and thus rest on Absolut non-contradiction and hence imply nescience. That means, every legitimate object-language is not as per Tarski member of the meta-language, but categorically separated from it. The trouble with logic is in its very positivity (affirmativity)! Whatever we say can not be better as 'not-false' in the context of natural- and legitimate object-languages. That is, the optimum way to speak about the world is the metaphor.

Heinz

Bookmark and Share
report post as inappropriate

Author Gemma De las Cuevas replied on Apr. 25, 2020 @ 18:54 GMT
Dear Heinz,

Thanks a lot for your reply. This sounds very interesting. I specially liked your comment about the metaphor :) I will read carefully your essay from 2015 and get back to you.

Thanks again,

Gemma

Bookmark and Share


Flavio Del Santo wrote on Apr. 25, 2020 @ 09:16 GMT
Dear Gemma,

I enjoyed your essay tremendously, for not only is well-written and your thesis crystal clear, but I think that it brings forward some deep insights too. In particular, I never thought of universality (as power of simulation) in terms of additional variables. Indeed, it makes a nice connection with my (and Gisin's) proposal, and it would be nice to explore this further.

I found insightful your analysis of (a certain class) of paradoxex as arising from the self-reference problem and negation. And how this issues is implied by universality, in your words: "since a universal system can be fed the description of any other system, it can also be fed its own description".

I also have two naive questions:

1) The whole starting point of your argument, namely the jump to universality, relies on the concept of complexity, which, however, I don't think it is defined in your essay besides an intuitive level (which perhaps is enough!). I was wondering if the universality claim is based on some particula, formal notion of complexity. And since you "define universailty as the ability to explore all complexity in a given domain", is complexity bounded from above?

2) You mention Wolfram's Principle of Computational Equivalence ("all processes which are not obviously simple can be viewed as computations of equivalent

sophistication"). Do you have any intutions on how this is justified?

I wish you the best of luck for the contest!

Cheers,

Flavio

Bookmark and Share
report post as inappropriate
Author Gemma De las Cuevas replied on Apr. 25, 2020 @ 12:46 GMT
Dear Flavio,

Thanks a lot for reading the essay and for your feedback. I am very glad we found some points in common and would very much like to explore them.

Regarding your questions:

1) A priori I don't think one can characterise the jump to universality in terms of some complexity measure, since complexity measures are defined for specific fields (for formal languages, spin...

view entire post


Bookmark and Share


Jochen Szangolies wrote on May. 1, 2020 @ 13:45 GMT
Dear Gemma,

thanks for a highly readable and insightful essay! I love the phrase 'the long reach of undecidability'; it is perfectly evocative of the often subtle ways in which the phenomenon of undecidability is relevant to often seemingly quite remote areas, such as determining whether a certain Hamiltonian has an energy gap in the ground state.

You present a few first steps...

view entire post


Bookmark and Share
report post as inappropriate
Author Gemma De las Cuevas replied on May. 4, 2020 @ 14:23 GMT
Dear Jochen,

Thank you so much for your comments! I believe they are very useful and will help me formalise some of the ideas of the essay - on universality, the jump to universality, and their application to various domains. I will keep you posted if I do any progress in these fronts :) Let's stay in touch.

Thanks again, really.

All the best,

Gemma

Bookmark and Share


Branko L Zivlak wrote on May. 6, 2020 @ 15:24 GMT
Dear Gemma De las Cuevas

When I read the essays of young scientists a look at reference to see whether they are on the right track. To be on the right track, you need to penetrate the minds of the greats of science of the past who have unrivaled achievements (Newton, Boskovic, Maxwell,…, Planck, Einstein, Euler, Ramanujan). Everything else leads to paradoxes, singularities… and a waste of time.

Regarda,

Branko

Bookmark and Share
report post as inappropriate
Author Gemma De las Cuevas replied on May. 7, 2020 @ 16:06 GMT
Dear Branko,

Thanks for your comment, but I disagree. I don't think it's a waste of time not to cite very influential thinkers - I believe it can even be liberating :)

Sincerely,

Gemma

Bookmark and Share


Alyssa Adams wrote on May. 11, 2020 @ 01:37 GMT
Hi Gemma!

This was a very fun read! I really love your point "Undecidability is thus an inescapable consequence of the expressive power of a system — it is the other side of the coin of universality. Universality Everywhere, thus, implies Undecidability Everywhere." This is a very good point. but also, it seems that physical systems like biology don't seem to mind.

It's interesting to think that we, as humans, can hold these paradoxes in our heads without any issue. I don't explode (like computers do in movies) when presented with a paradox. We just kinda go "Huh" and then move about our daily lives. it's strange to think that maybe paradoxes don't affect us that much, yet have such a profound effect on mathematics. I personally think it's due to the disconnect between our current mathematical theories and physical reality. We have much more to model!

Cheers!

Alyssa

Bookmark and Share
report post as inappropriate
Author Gemma De las Cuevas replied on May. 14, 2020 @ 07:08 GMT
Hi Alyssa,

thanks for reading my essay and I'm glad you enjoyed it!

>> This is a very good point. but also, it seems that physical systems like biology don't seem to mind.

I agree with you. It seems that the paradoxes cannot be "implemented" (in biological sytems or in physical computers). Only things that "make sense" can be implemented. Make sense is here defined with respect to the usual logic.

>>It's interesting to think that we, as humans, can hold these paradoxes in our heads without any issue. I don't explode (like computers do in movies) when presented with a paradox.

I don't explode (obviously) but I am left in a blocked state: I don't know how to solve it, and I cannot conclude that 'I am liar' is true nor false. So in this sense I am in a dead end - maybe that's the cognitive version of exploding :)

>>I personally think it's due to the disconnect between our current mathematical theories and physical reality.

I am also very interested in the question of whether one could define some mathematical models that circumvent some of these paradoxes. Or, alternatively, that model better the way we think. Or the two wishes together. The first wish has been addressed in alternative models of truth, such as Kripke's theory of truth and developments thereof. People investigating models of consciousness may be have addressed (in a perhaps oblique way) the second wish.

Thanks again for your input :)

All the best,

Gemma

Bookmark and Share


Member Markus P Mueller wrote on May. 14, 2020 @ 12:56 GMT
Dear Gemma,

I enjoyed reading your essay immensely! I feel like I have learnt a lot — I was not aware before of the Boltzmann-machine and neural-network-types of universality, and it was nice to see the different examples put side-by-side. As universality is everywhere, undecidability must be too. And this raises several fascinating questions: does knowing transcend proving? Can the limitations be overcome by some other type of logic? What about the relation (as pointed out by Deutsch) to physics? Your essay gives a fascinating exploration of those ideas.

One thing that suggests itself to be explored further, I think, is your statement that (Turing-type) universality only happens in digital systems. It feels like there must be some grain of truth to it. But it is probably not that easy to make it fully rigorous. For example, quantum theory has a continuous (non-digital) set of wave functions, and yet, it admits error correction (and contains a kind of “hidden” form of digitality)… So what kind of “digital” we need for reliable self-representation (for the liar paradox, as you pointed out) is perhaps a deeper question?

All the best,

Markus

Bookmark and Share
report post as inappropriate
Author Gemma De las Cuevas replied on May. 14, 2020 @ 13:58 GMT
Dear Markus,

thank you so much for your comments! I'm so glad you enjoyed the essay!

>> quantum theory has a continuous (non-digital) set of wave functions, and yet, it admits error correction (and contains a kind of “hidden” form of digitality)… So what kind of “digital” we need for reliable self-representation (for the liar paradox, as you pointed out) is perhaps a deeper question?

This is a very interesting question. But I don't know if the digitality needs to be "hidden" or mysterious. Consider natural language. At the spoken level it is continuous; yet, as a code, it is digital. The latter is reflected in the fact that it admits a representation with finitely many symbols. Listening to someone speak a language with their accent is doing error correction, i.e. mapping the sounds to a finite set of objects that give rise to a word and thereby an element of the language.

I'd love to discuss this next time we meet :)

Thanks again for reading the essay and for your very encouraging comments.

All the best,

Gemma

Bookmark and Share


Member Robert W. Spekkens wrote on Jun. 24, 2020 @ 16:09 GMT
Hi Gemma,

I really enjoyed your essay! I particularly appreciated all of the scholarship that went into your exposition of the topic. It seems to me that the role of universality is underrepresented in such discussions, so it was nice to see it centre stage in your essay. Concerning this: “Perhaps computable, provable, true, etc could be defined in a completely different yet-to-be-discovered way, which would rid them of the paradoxes.” Do you have any ideas of what this would look like? Also, have you thought at all about whether universality for quantum computation (as opposed to classical computation) comes with any novel consequences for self-reference? Thanks!

Bookmark and Share
report post as inappropriate
Author Gemma De las Cuevas replied on Jun. 25, 2020 @ 11:47 GMT
Hi Rob,

Thanks so much for reading the essay, and I'm really glad you enjoyed it!

>> Concerning this: “Perhaps computable, provable, true, etc could be defined in a completely different yet-to-be-discovered way, which would rid them of the paradoxes.” Do you have any ideas of what this would look like?

Not really. As mentioned in the essay, many people have tried to solve these paradoxes, mainly by building explicit or implicit hierarchies in the definition of truth, or computable, or knowable. (This is wonderfully explained in the Thomas Bolander's article on Self-reference - https://plato.stanford.edu/entries/self-reference/ ). But these hierarchies are infinite, so they only provide a solution in the limit, which I don't see as a solution. But perhaps we ought to take Markus P. Mueller's view and do not see this as a limitation, but rather as an indication that 'what is true / provable / knowable' is the wrong question.

>> Also, have you thought at all about whether universality for quantum computation (as opposed to classical computation) comes with any novel consequences for self-reference?

No, I haven't thought about that yet, but will definitely do. I would also love to discuss this with you :)

Thanks again for reading and commenting, and all the best,

Gemma

Bookmark and Share


Login or create account to post reply or comment.

Please enter your e-mail address:
Note: Joining the FQXi mailing list does not give you a login account or constitute membership in the organization.