Destubification

For discussion directly related to ConwayLife.com, such as requesting changes to how the forums or wiki function.
Post Reply
Book
Posts: 243
Joined: August 28th, 2021, 2:38 pm
Location: California
Contact:

Destubification

Post by Book » December 23rd, 2021, 2:05 pm

An editor maintenance report of pages marked as stubs would be quite useful to get this started. The we could see how the so-called stubs sort into different situations.

User avatar
dvgrn
Moderator
Posts: 8935
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Destubification

Post by dvgrn » December 23rd, 2021, 3:17 pm

Book wrote:
December 23rd, 2021, 2:05 pm
An editor maintenance report of pages marked as stubs would be quite useful to get this started. The we could see how the so-called stubs sort into different situations.
This modified search page seems to list all 296 of the current articles marked with a {{stub}} template. Is that a good start?

If I remember right, a number of stubbed articles have evolved enough by now that they're no longer really stubs, or at least don't need a huge amount of work.

Book
Posts: 243
Joined: August 28th, 2021, 2:38 pm
Location: California
Contact:

Re: Destubification

Post by Book » December 23rd, 2021, 3:24 pm

Yeah, that's where I was looking when I made that post about the maintenance report. I'll be using search for now.

Book
Posts: 243
Joined: August 28th, 2021, 2:38 pm
Location: California
Contact:

Re: Destubification

Post by Book » December 24th, 2021, 1:46 pm

Should "Glider to 2-engine Cordership" be merged into "2-engine Cordership"? Opinions?

Book
Posts: 243
Joined: August 28th, 2021, 2:38 pm
Location: California
Contact:

Re: Destubification

Post by Book » December 24th, 2021, 1:56 pm

Should "StreamLife" be merged into "HashLife"? Opinions?

Book
Posts: 243
Joined: August 28th, 2021, 2:38 pm
Location: California
Contact:

Re: Destubification

Post by Book » December 24th, 2021, 2:19 pm

Is anyone really going to maintain the Timeline of Life facts article? What should we do with it?

Book
Posts: 243
Joined: August 28th, 2021, 2:38 pm
Location: California
Contact:

Re: Destubification

Post by Book » December 26th, 2021, 6:52 pm

Shall we put all the test tube babies in one article? Some of their articles are called out as stubs and/or not notable, but they all look similar to me: as a group, not so stubby and perhaps noteworthy

User avatar
dvgrn
Moderator
Posts: 8935
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Destubification

Post by dvgrn » December 27th, 2021, 7:52 am

Book wrote:
December 24th, 2021, 1:56 pm
Should "StreamLife" be merged into "HashLife"? Opinions?
I'd rather the StreamLife article got destubified by adding a little more detail -- just haven't done it, because I'm not sure the old descriptions I have of the internal workings of the algorithm are entirely up to date. See The City and the City for the BESZEL and ULQOMA references.
In a 10 January 2018 email, Adam P. Goucher wrote: we have two parallel universes (each in its own quadtree). One stores the E/NE/N/NW-directed tiles and permeable tiles, and the other stores the W/SW/S/SE-directed tiles and generic tiles. Let's call these universes BESZEL and ULQOMA, respectively.

Now, each quadtree node is decorated by a descriptor containing the following information:

-- whether it's 'permeable', 'horizontal', 'vertical', 'diagonal', 'antidiagonal', or 'generic';

-- if it's directional, then a bitfield giving the occupied lanes (modulo 64 half-diagonals or 32 rows/columns, let's say*). The occupied lanes are obtained by convolving the history envelope with the Moore neighbourhood, so patterns with disjoint 'occupied lanes' do not interact.

The descriptors form a join-semilattice. The rules are:

-- 'permeable' is the bottom of the semilattice, and 'generic' is the top.

-- the join of two different directions is 'generic'.

-- the join of two descriptors of the same direction is given by the bitwise OR of their bitfields.

-- the descriptor of a non-leaf is the join of the descriptors of its 9 pseudochildren [with bitfields rotated appropriately as necessary].

(A pseudochild of a 2^n-by-2^n node is a 2-by-2 block of 2^(n-2)-by-2^(n-2) nodes. Pseudochildren overlap, unlike regular children; this overlap is necessary to ensure that we can deduce that a non-leaf is directional.)


A pair of commensurate quadtree tiles (BESZEL tile, ULQOMA tile) are said to be 'provably non-interacting' if either one of them is empty, or if they have (anti)parallel directions and disjoint bitfields.

The 2-universe hashlife algorithm then accepts, as an argument, an ordered pair (BESZEL tile, ULQOMA tile) of commensurate tiles (assumed to be in the same location). It checks whether they're provably non-interacting and, if so, computes 1-universe hashlife on each of BESZEL and ULQOMA and returns the ordered pair of their results.

If they're *not* provably non-interacting, then it just calls (13 copies of) 2-universe hashlife, recursively, in standard hashlife style. [Of course, each of those sub-calls checks for probable non-interactivity, and so forth.]

For the smallest iterations of 2-universe hashlife (running a 32-by-32 square 8 generations), the resulting 16-by-16 leaf is then checked for emptiness/directionality/genericity and the ordered pair is either (RESULT, 0) or (0, RESULT) depending on whether the tile should be in BESZEL or ULQOMA.


* you can nullify the advantage of my algorithm by ensuring that the westbound and eastbound MWSSes lie on the same lanes modulo 32. But provided you don't do this (or increase the size of the bitfield), it will *run away* with patterns comprising boustrophedonic loops of power-of-2-regularly-spaced streams.

Also, the streams need to be separated by more than 16 cells (or 16 full-diagonals for glider streams) so as to ensure that the 16-by-16 leaves only contains unidirectional ships and therefore are not classified as 'generic' by the leaf detection routine.

I don't think this restriction is too bothersome: we already dimension patterns to be 'hashlife-friendly', so it's not a huge leap to incorporate this slight constraint in subsequent constructions to make them '2-universe-hashlife-friendly'.


The final problem is detecting whether a 16-by-16 leaf is directional or not. This just involves checking whether the central 8-by-8 square (after iterating by 4 gens) agrees with the appropriate off-centre** 8-by-8 square (before iterating).

** that is to say, offset by (1, 1), (1, -1), (-1, 1), (-1, -1), (0, 2), (0, -2), (2, 0), or (-2, 0). Performing this check is linear in the number of velocities you want to handle, which is why it should be restricted to just period-4 c/4 diagonal and c/2 orthogonal.

If it agrees with *all* of these, the node is classified as 'permeable'. The zero node is, of course, permeable.
Book wrote:
December 24th, 2021, 2:19 pm
Is anyone really going to maintain the Timeline of Life facts article? What should we do with it?
I don't intend to spend any time trying to update that list, but on the other hand, there's not much harm in leaving it for another decade or so, just in case someone else gets enthusiastic about the idea. On the other other hand, there's not much harm in removing it, either, or moving it to Methodood's user pages. Methodood hasn't visited for over a decade, though, so probably we might as well just be brave and delete the page.
Book wrote:
December 26th, 2021, 6:52 pm
Shall we put all the test tube babies in one article? Some of their articles are called out as stubs and/or not notable, but they all look similar to me: as a group, not so stubby and perhaps noteworthy...
I like that idea, personally.

Book
Posts: 243
Joined: August 28th, 2021, 2:38 pm
Location: California
Contact:

Re: Destubification

Post by Book » December 27th, 2021, 2:17 pm

I'd rather the StreamLife article got destubified by adding a little more detail -- just haven't done it, because I'm not sure the old descriptions I have of the internal workings of the algorithm are entirely up to date.
I think we should go with the author's description, denoting the timeframe. I'll do that.

Book
Posts: 243
Joined: August 28th, 2021, 2:38 pm
Location: California
Contact:

Re: Destubification

Post by Book » December 27th, 2021, 5:17 pm

I've handled as much destubifying as I can, at least for now. Quite a few have been resolved.

I've noticed that there are quite few stubby articles that are not denoted as stubs, many of which have been around for years. Most lack a statement as to why they are notable, what I call the "so-what?" statement. And an example would often help. Pet peeves.

Post Reply