1
$\begingroup$

As we know, Conway's Game of Life is Turing-complete. And Turing-complete systems can be used to calculate irrational numbers such as $\sqrt{2}$, $\pi$, $e$, etc. which have non-repeating digits.

So it might be natural to reach the conclusion that Conway's Game of Life can be used to generate non-repeating digits.

To limit the scope of this question and not make it open-ended and opinion-based, I'll be asking: has there been research on cellular automata:

  • generating infinite non-repeating patterns,
  • by programming it to carry out computation similar to square root and base-2 logarithm over fixed-point numbers? (these computations are the easiest I've thought of that can be carried out on fixed-point numbers with sufficient numericall accuracy)
$\endgroup$
4
  • 1
    $\begingroup$ Are you asking about Conway's Life specifically, or cellular automata in general? And what do you mean by "generating infinite non-repeating patterns"? Two gliders traveling in opposite directions is a pattern that never repeats exactly, but I suspect you're looking for something more complex. $\endgroup$ Commented Sep 8, 2021 at 7:56
  • $\begingroup$ @IlkkaTörmä Edited. $\endgroup$
    – DannyNiu
    Commented Sep 8, 2021 at 9:02
  • 2
    $\begingroup$ I'll just leave this here: conwaylife.com/wiki/Pi_calculator $\endgroup$ Commented Sep 8, 2021 at 13:38
  • 2
    $\begingroup$ A recent example is a paper by Kutrib and Malcher, One-Dimensional Pattern Generation by Cellular Automata, Cellular Automata (ACRI 2020), LNCS 12599, doi: 10.1007/978-3-030-69480-7_6. From its abstract: "we [...] look at cellular automata towards their ability to generate formal languages, here called patterns, within certain time constraints. As an example we describe a construction of a cellular automaton that generates prefixes of the well-known Thue-Morse sequence within real time." Thue-Morse is a famous non-repeating pattern. $\endgroup$ Commented Sep 8, 2021 at 18:01

1 Answer 1

1
$\begingroup$

Rule 110 is a cellular automaton that is Turing complete, hence it can generate non-repeating patterns. Since it is Turing complete it can certainly compute the square root of a fixed-point number.

$\endgroup$
2
  • $\begingroup$ I might be mistaken but I don't see the "by programming it" part in your answer. $\endgroup$
    – DannyNiu
    Commented Sep 8, 2021 at 13:00
  • 1
    $\begingroup$ @DannyNiu It is Turing complete, just write "the program" of your choice as a Turing machine, and use the Turing completeness construction. If you want infinite non repeating pattern you can calculate $\pi$ or something similar. $\endgroup$
    – nir shahar
    Commented May 31, 2023 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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