0
$\begingroup$

I found a question in Mathematics Stack Exchange which asks a very similar question

(https://math.stackexchange.com/questions/1023812/hypercomputation-higher-dimensional-variants-of-conways-game-of-life)

It asks whether there are Game of Life models with 3 or more dimensions and if there are Game of Life models related to hypercomputation, but the answers seem to refer to the first question and ignore the second.

So, if I am not wrong, and that is the case, then:

Is there any specific model of Game of Life (Or Cellular Automata in general) that can perform hypercomputation (i.e a Hypercomputational model of Game of Life and/or Cellular Automata)?

And also, Is there any specific model of a hypercomputational Game of Life/Cellular automata that has been applied to physics? That has proposed a cosmological/physical model of the universe based on these Cellular Automata? (Like some sort of Zuse's thesis: https://en.wikipedia.org/wiki/Calculating_Space)

$\endgroup$
  • $\begingroup$ Have you read Stephen Wolfram's thoughts on cellular automata? wolframscience.com $\endgroup$ – Solomon Slow Mar 11 at 2:08
  • 1
    $\begingroup$ Not clear whether you are asking about a cellular automaton whose next generation could only be computed by a hypercomputer, or whether you are asking about a cellular automaton that effectively is a hypercomputer. Either way, I think that in order to bring "hypercomputation" into the picture, you would have to go beyond what "cellular automaton" normally is understood to mean. Maybe if you had an infinite-dimensional CA,... $\endgroup$ – Solomon Slow Mar 11 at 2:18
  • $\begingroup$ @SolomonSlow what about the link of the question I posted? Are the cellular automata proposed there capable of doing hypercomputation? (Are these cellular automata hypercomputers)? $\endgroup$ – user180164 Mar 11 at 19:58
  • 1
    $\begingroup$ The question that you linked mentions hypercomputing, and it mentions higher-dimensional cellular automata, but I don't see where it connects the two ideas at all. The two CAs that it talks about both have actual, working software implementations. If you can actually do something, then whatever it is that you are doing, by definition, is not hypercomputing. A discussion about hypercomputing is a discussion about what computers could do IF they had certain, specific super-powers (e.g., the power to perform an unbounded number of computation steps in a fixed, finite amount of time.) $\endgroup$ – Solomon Slow Mar 11 at 20:48
1
$\begingroup$

Cellular automata can be simulated with an ordinary Turing machine, so they don't have any more power than an ordinary Turing machine -- they can't perform "hypercomputation".

$\endgroup$
  • $\begingroup$ what about the link of the question I posted? Are the cellular automata proposed there capable of doing hypercomputation? (Are these cellular automata hypercomputers)? $\endgroup$ – user180164 Mar 11 at 19:58
  • $\begingroup$ @user180164, what about it? I haven't read Zuse's book but I didn't see anything there that would make me change my answer. Cellular automata can be simulated by Turing machines, as I mentioned in my answer. $\endgroup$ – D.W. Mar 11 at 20:14
0
$\begingroup$

If you want to introduce Hypercomputation in CA, one way could be going "meta". So for example an Hypercomputer could execute a CA where every cell contains states that are uncomputables by traditional TMs. For what concern the physics part, someone (I am aware for example of Gerard Hooft) suggested a superdeterminisic theory where the basic working of reality is in fact a CA.

$\endgroup$
  • $\begingroup$ Even if every cell's next state was computed with its own TM, the whole thing could be simulated by an ordinary TM, so it wouldn't be able to perform 'hypercomputation'. $\endgroup$ – D.W. Apr 14 at 20:42
  • $\begingroup$ I don't know what you mean by "TM state", but a TM can't compute an uncomputable function (that's a matter of the definition of computable). $\endgroup$ – D.W. Apr 15 at 5:35

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.