Talk:Reversible cellular automaton

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Undecidability[edit]

This part of the lede is ambiguous:

However, for cellular automata that are not defined by these methods [block or second-order], on arrays of two or more dimensions, testing reversibility is undecidable.

I understand that reversibility testing is undecidable in general, but does this also mean that there cannot exist a third method of constructing reversible automata? QVVERTYVS (hm?) 08:48, 1 September 2015 (UTC)[reply]

I hope this edit makes it both clearer and a little more accurate. —David Eppstein (talk) 01:47, 27 September 2015 (UTC)[reply]

GA Review[edit]

GA toolbox
Reviewing
This review is transcluded from Talk:Reversible cellular automaton/GA1. The edit link for this section can be used to add comments to the review.

Reviewer: Edwininlondon (talk · contribs) 21:13, 26 September 2015 (UTC)[reply]



1. WELL WRITTEN

  • Just a few comments below.

2. VERIFIABLE

  • exhaustively sourced to a diversity of sources

3. BROAD

  • a cursory search of in Google reveals nothing substantial that has been omitted

4. NEUTRAL -

  • all fine

5. STABLE

  • no edit wars or major recent activity

6. ILLUSTRATED

  • What is missing is an illustration of the basic principle, ideally at the beginning, i.e of a one-dimensional CA, maybe showing the rule to copy state from a fixed neighboring cell and then reverse its value.
    •  Done (with a slightly less trivial rule) —David Eppstein (talk) 21:22, 29 September 2015 (UTC)[reply]
      • Fantastic image!

Additional comments[edit]

  • I don't think the Wolfram needs to be quoted in the lead. This doesn't seem controversial.
    • I put this in the lead because I thought this was a nice quote for motivating interest in the subject, and it didn't really fit into any of the more technical sections later. MOS:LEAD states that material in the lead "should define the topic, establish context, explain why the topic is notable, and summarize the most important points, including any prominent controversies." So this is an example of something that establishes context (how this fits into the theory of cellular automata more generally) rather than the summarization function performed by most lead text (including in this article). But if you think it should be moved elsewhere in the article, please suggest where. Or did you think it was not worth including at all? —David Eppstein (talk) 04:01, 30 September 2015 (UTC)[reply]
      • I wasn't challenging the content itself, I agree it provides good context. There are 2 things that bother me. 1) He is the only one named, which is fine I think if he is indeed a stand-out person in the field. Do you think he deserves being singled out? 2) the way I interpreted the [[MOS:LEAD] bit about citations is that in this case we should rephrase Wolfram in the lead rather than cite, in which case we don't need the source reference in the lead. As for a place in the main article, maybe at the end of the Theory, before 3.1?
        • In cellular automata in general, yes, Wolfram is one of the founders of the field. They were studied before him but he made major and early contributions to the subject that set the course for a large part of what followed. —David Eppstein (talk) 22:23, 30 September 2015 (UTC)[reply]
  • ordered pair (r,l) | This order puzzled me, with right being on the left. Seems (l,r) would be more expected order. The outcome of (a,b) X (c,d) as you have it now should be (c, b)
    •  Done. I think this was just a mistake. But if we're taking the left part of the left argument and the right part of the right argument, the outcome would be (a,d), as it already was. —David Eppstein (talk) 21:22, 29 September 2015 (UTC)[reply]
  • would it not be better to choose one of non-reversible and irreversible rather than mix?
    •  Done. I think "irreversible" is a little more idiomatic. —David Eppstein (talk) 21:22, 29 September 2015 (UTC)[reply]
  • SecondOrderCADiagram appears too early when viewed on smartphone, should live inside the Second order section
    •  Done. I also moved an earlier image left so that these two could be on the right side in higher-resolution views. —David Eppstein (talk) 21:27, 29 September 2015 (UTC)[reply]
  • Theory section: the beginning feels repetitive. So much has already been explained. Point 4 is the first new bit.
    • In the text just above the numbered items, the formal definition of a "configuration" is new, and takes up most of the text. This is also the first point at which the requirement that the update function must be the same everywhere ("invariant under translations") is formalized mathematically. Some of the numbered items were discussed less formally earlier, but this is the first point where it is stated that these five different-looking definitions are actually all equivalent. But obviously these points weren't adequately conveyed in your reading, so some revision to make them clearer would be a good idea. In particular this edit is intended to clarify how the different numbered items relate to each other. —David Eppstein (talk) 22:31, 29 September 2015 (UTC)[reply]
      • OK, I get it now.
  • An edge in Sutner's graph | Edges are in non-directed graphs. Should it not be arrow?
    • A search in Google scholar for the combination of the phrase "directed graph" and one of the different names for the linky things in them finds about 25k instances of "arrows", about 25k instances of "directed edges", about 45k instances of "arcs", and about 100k instances of "edges". In other words, the insistence in our directed graph article that these things are primarily called "arrows" appears to be false. This also matches my own experience in reading and writing research articles about graph theory. But in this edit I clarify how the edges are directed and that the cycle needs to be directed. —David Eppstein (talk) 23:13, 29 September 2015 (UTC)[reply]
      • You convinced me. My own CS class from decades ago never was a reliable source in hindsight.
  • Abstract algebra section could use an introducing sentence, something like Abstract algebra has been used as the basis for algorithms for enumerating certain kinds of reversible cellular automata.
  • from a rectangular band, in which the cell states are pairs of values (a,b) drawn from sets L and R | better to use the exact same notation as above (which was problematic anyway)
    •  Done, now using pairs of values (l,r) as earlier. But the same variables l and r were also used for something else (numbers of conserved quantities) in the same paragraph, so I also changed those to be lambda and rho. —David Eppstein (talk) 03:52, 30 September 2015 (UTC)[reply]
  • HPP model, anisotropy, FHP all need a wikilink
  • References: some article names have camel case; make them all consistent. E.g Can Anything from Noether’s Theorem Be Salvaged for Discrete Dynamical Systems? | Can anything from Noether’s Theorem be salvaged for discrete dynamical systems?
    •  Done. I only found one other one, Margolus' Crystalline computation. —David Eppstein (talk) 00:39, 30 September 2015 (UTC)[reply]
  • The odd reference has unneccessary abbreviations, such as Discrete Math. Theor. Comput. Sci. Proc.
  • link Proc. 36th Annual Symposium on Foundations of Computer Science doesn't go the 36th
  • Comput. Soc. Press | Computer Society Press
  • Try and make names as consistent as possible, e.g Vichniac, G. | Vichniac, Gérard
    • The intent was to match the name in the individual publication; not all authors use the same form of their name for all publications. But in the case of Vichniac, the name as published was "Gérard Y.", so I've fixed that. I also checked the other instances where authors were named by initials, verified that in all but one case that was the name used in the publication, and fixed the one case where it wasn't. —David Eppstein (talk) 21:22, 29 September 2015 (UTC)[reply]
  • Add ISBN: 9780262200608 to Toffoli, Tommaso; Margolus, Norman (1987) and maybe external link to https://mitpress.mit.edu/books/cellular-automata-machines
    • I prefer not to add links to publisher sales websites; I think they're too commercial and not informative enough to be encyclopedic. But I added the ISBN. —David Eppstein (talk) 21:22, 29 September 2015 (UTC)[reply]
  • Add ISBN: 978-0-470-16879-0 to Schiff, Joel L. (2008) and maybe external link http://eu.wiley.com/WileyCDA/WileyTitle/productCd-047016879X.html
    • Ditto. (In both of these cases, I added the citation with reference to a physical book; these two books happen to have the ISBN printed on the back but that's not always the case.) —David Eppstein (talk) 21:22, 29 September 2015 (UTC)[reply]
  • To appear at the 6th Innovations | This conference was in January. I can't easily find the proceedings, maybe not out yet.
  • Link "Conservation laws in rectangular CA" gives access denied

Edwininlondon (talk) 19:55, 29 September 2015 (UTC)[reply]

Ok, I think I have responded to all of your suggestions above (which doesn't exactly mean I have done all of them as suggested). Is there more to do? —David Eppstein (talk) 04:18, 30 September 2015 (UTC)[reply]

  • No. I enjoyed reading and reviewing it. Thank you for responding to my suggestions, and, again, I think the image you added is very illustrative, fantastic addition. I think it's great that you as an expert contribute to WP. I urge you to take it further and nominate it for Featured Article. There are hardly any CS articles that get to FA. Edwininlondon (talk) 20:53, 30 September 2015 (UTC)[reply]

I don't see the GA symbol on the article page. Did I do something wrong? Edwininlondon (talk) 06:40, 2 October 2015 (UTC)[reply]

According to the instructions the symbol is supposed to be added later by a bot. But it also says you should add this article to Wikipedia:Good articles/Mathematics and I don't know whether the bot is triggered by the GA template at the top of this article or by that addition. —David Eppstein (talk) 07:11, 2 October 2015 (UTC)[reply]


Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Reversible_cellular_automaton&oldid=1212698346"