1
$\begingroup$

Is there some link between the concept of emergence and Turing Completeness? The ideas feel intuitively like they might be linked, but I can find nothing online.

The idea came to me because I was exploring Conway's Game of Life, and it was hard not to suppose a link between these two properties.

Edit: In response to Raphael's point, I have a clarification to the question (which I thought was implied, but in hindsight, it really wasn't)

Must it be the case that systems that exhibit weak emergent complexity are also Turing Complete?

|cite|improve this question
$\endgroup$
  • $\begingroup$ The question in itself is very interesting, but I'm not sure how to frame it. Turing completeness is a property of computational models, mathematical, "ideal" objects with a formal definition. On the other hand, natural phenomena exist in the real world, and we can at most model them with our mathematical tools. Whether or not a model is suitable for a given phenomenon depends on what kind of questions you want to ask to the model, and there are often multiple valid models, used depending on context. $\endgroup$ – quicksort Nov 4 '17 at 18:14
  • $\begingroup$ Conway's Game of Life is just a special case of a cellular automaton, a computational model that in some variants is indeed universal. $\endgroup$ – quicksort Nov 4 '17 at 18:15
  • $\begingroup$ This seems like a prompt for philosophical discussion, not a question for scientific or mathematical facts. Too broad? Primarily opinion-based? Community votes, please! $\endgroup$ – Raphael♦ Nov 4 '17 at 20:29
1
$\begingroup$

I suggest you to give a look to S. Wolfram's book "A New Kind Of Science" (that is also available online).

The centeral ideas are:

Though these ideas are probably not new, they are exposed in a fascinating way (to be honest, a rather informal and non-mathematical "way").

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.