Hacker News new | past | comments | ask | show | jobs | submit login
Build a digital clock in Conway's Life (stackexchange.com)
712 points by ChuckMcM on March 11, 2017 | hide | past | favorite | 87 comments

VM life

huh? downvote? the link is a virtual machine in Conway's Game of Life.

I went through a period of intense study of cellular automata. It it a deep, deep, rabbit hole of interesting bits. One of the things I contributed early was a simple 'two species' variation where the rules for dual species were encoded in three matrices. I used it as a demo on one of the Fred Fish Amiga disks (it used pretty much every Intuition window call in the book on purpose).

The clock has me thinking I need to get out my FPGA based simulator again and to hook it up to a nice 720P display :-).

If you turned that into into an actual clock with half decent accuracy, I'd seriously buy one. Even if the only way to set the time was to wait until noon or midnight to plug it in. It would probably also function well as a space heater in winter. :)

Me too. CAs are fun. But obviously people like Wolfram take them way too seriously (assuming "A New Kind of Science" was sincere and not just a way to convince hobbyists to buy Mathematica)

If you can make a large enough game of life simulation in hardware that runs at the precise speed to make the clock accurate, I'd buy it in an instant. As in, it can run any pattern you want, but running exactly that pattern results in an accurate digital clock. You'll of course need a few buttons to program in a new pattern and to set the pattern to a specific time.

Really? Hm... Clocks/accurate timing && cellular automata/dynamic systems are things I'm passionate about. (and know how to build)

For a hypothetical device you'd "buy in an instant" how are you imagining the output (and controls). Like, would you want a box with its own display? Or what?

Me too but first the design need to be fixed so that counters are both top and bottom - in that answer the bottom half of the clock takes more than 30 second to change and it stays in the transitioned state for too long as well making large changes confusing - like 7 to 8

Could you suggest some good introductory resources for getting into CA? Is there actually some systemic way of studying this stuff?

"Essays on Cellular Automata" by Arthur Burks is a good starting point. Then there's the proceedings of the conference, "International Conference on Cellular Automata for Research and Industry".

Start by going to a good library and checking out the proceedings of the Artificial Life (ALIFE) conference. Read the papers and start following the references.

For something less academic and more "look at cool stuff" there's also https://www.reddit.com/r/cellular_automata/

In addition to the more directly related stuff others have mentioned it's also relevant and interesting to dive into Complex Adaptive Systems literature if you have the inclination, for the classic order-from-chaos essays and discussions of emergent properties and so on.

> I used it as a demo on one of the Fred Fish Amiga disks

Just googled that, it's a whole archive (yay!). Which demo was it? I obviously want to see something with GoL and "every Intuition window call in the book on purpose" :)

The two species variation sounds interesting. If you don't mind, please post more about it including the three matrices. Thanks in advance.

Consider the following:

                            Cell is currently:

          Empty                   Type 1              Type 2
   T 7 | .                 7 | .                7 | . 
   y 6 | . .               6 | . .              6 | . . 
   p 5 | . . .             5 | . . .            5 | . . .  
   e 4 | . . . .           4 | . . . .          4 | . . . .  
     3 | . . . . .         3 | . . . . .        3 | . . . . .  
   1 2 | . . . . . .       2 | . . . . . .      2 | . . . . . . 
     1 | . . . . . . .     1 | . . . . . . .    1 | . . . . . . . 
     0 | . . . . . . . .   0 | . . . . . . . .  0 | . . . . . . . .
       +-----------------    +-----------------   +-----------------
         0 1 2 3 4 5 6 7       0 1 2 3 4 5 6 7      0 1 2 3 4 5 6 7
        Type 2
For each cell, it can be one of empty, type 1, or type 2. In the matrix you specify what the next step is given 0 - 7 type 1 neighbors and 0 - 7 type 2 neighbors, the 'classic' rules would be (only one type):

          Empty                   Type 1              Type 2
   T 7 | E .               7 | E .              7 | .  
   y 6 | E .               6 | E .              6 | . . 
   p 5 | E . .             5 | E . .            5 | . . . 
   e 4 | E . . .           4 | 1 . . .          4 | . . . . 
     3 | 1 . . . .         3 | 1 . . . .        3 | . . . . . 
   1 2 | E . . . . .       2 | E . . . . .      2 | . . . . . . 
     1 | E . . . . . .     1 | E . . . . . .    1 | . . . . . . . 
     0 | E . . . . . . .   0 | E . . . . . . .  0 | . . . . . . . .
       +-----------------    +-----------------   +-----------------
         0 1 2 3 4 5 6 7       0 1 2 3 4 5 6 7      0 1 2 3 4 5 6 7
        Type 2
The way you "read" it is left to right:

If the cell is empty, matrix 1 applies. If it has 3 Type 1 neighbors exactly, then in the next iteration it will have a Type 1 value. If it has more than 3 Type 1 neighbors or fewer than 3 Type 1 neighbors it will be Empty in the next iteration.

If the cell is type 1 then matrix 2 applies. If it has 3 or 4 type 1 neighbors it stays type 1, if it has fewer than 3 or more than 4 neighbors it becomes empty on the next iteration.

There are a number of ways to expand this, you can create two 'co-species' where they follow the original rules for their species and ignore the other except for conflict (3 neighbors of type 1 and 3 neighbors of type 2). You can create 'evolving' species where an over population of type 1 neighbors generates a type 2 cell which behaves using existing rules. Etc.

You change the rules by placing E, 1, or 2 in each matrix spot. Any spot that has more than a total of 7 neighbors is invalid (so the top right diagonal half of each matrix).

Classic Life is B3/S23, not B3/S34. Am I reading your diagrams wrong?

Also, your matrices for empty and type 1 each have an extra dot after the E on the first row (I think).

Thanks for the correction. And yes when I put in the E's I didn't correctly delete the dot on the top row.

I wish the web was still like that. No advertising, no tracking, there's not 5 mb of CSS and javascript, just information presented in a readable format.

Every time I say something like that, someone tells me that we're better off the way things are. Tracking is BS. Ads are a great way to make my computer fetch data that I neither need nor want, and to run programs that work against my best interests using my own CPU cycles. I'm not completely convinced that we wouldn't be better off dumping the current state of the art and re-designing from first principles.

I agree with the sentiment, but with a slightly different angle. I think one of the things that made the early Internet interesting was that it was populated almost exclusively by enthusiasts (geeks, artists, etc) with little commercial motivation. Stuff was quirky and interesting. Today's Internet is a fantastic platform for commerce. I'd be very sad to see it go, but I also think there's a need for the weird old quirky net we had before marketing took over. What I'd like to see is the emergence of a new enthusiast network that's inherently difficult and inconvenient to commercialize alongside the existing net. One is good for getting eyes on content and marketing stuff, which is important, and the other is good for just putting up whatever you find interesting simply because you want to. When I want to buy something I'll use what we have now, but the other net would be more interesting to just browse around and share stuff on.

I think IPFS [1] or something similar might have the potential to resurrect the geek net. IPFS with a distributed mesh network infrastructure seems like it would be slow, inconvenient for commerce, and probably attractive only to the kind of people that made the early net interesting, especially with the current net as competition.

1. https://ipfs.io

I think to a certain extent Bruce Sterling anticipated your thoughts in his classic cypher punk novels: all the elite hackers met in areas they controlled and that had to be broken into... I've often wished for a place with a higher bae to entry but then privately wonder if that's one of the /r/iamverysmart thoughts I should just quietly strangle before sharing it with others.

There's nothing wrong with having a filter. If I want to have a deeply technical discussion that requires a decade+ of speciality knowledge to understand, then so be it, that discussion isn't for everyone. Being on the edge of a knowledge domain is difficult enough as it is. Pushing the boundaries of my own knowledge requires like-minded individuals, and stopping to explain kills the flow.

There are plenty of other times when a more open, informal setting is appropriate, and beginners and journeymen are welcome. But not every time.

The old 2600 website was organized in circles with innoquous hacking challenges to enter, it could still be done somewhat, if one can solve the issue of simply googling solutions

That's the other half of the challenge: preventing the solutions showing up on stackoverflow. Hell maybe you use a few easily googled solutions as a way to mark the script kiddies and shuffle them into their own swamp.

I like that idea, though it seems the best way to 'make that happen' is to explicitly form a community that agrees to only put their content in IPFS. And there would have to be enough popular members that others would be motivated to join and access what's there. Otherwise I don't see it as more than a toy.

Yeah, that's a good point. One of the things that I think could help would be to make the basic technology stack somehow different from html/css/js, so that different (not necessarily more or less) things are possible in the new medium. I don't know what that should look like, because my own preference is strongly toward text-oriented content which is well-served by the current stack, but having a different kind of toys in the playground might be enough to entice people to contribute all by itself.

> Otherwise I don't see it as more than a toy.

I was a kid so I could well be wrong, but my memory of the early net was that most 'regular' people kind of saw it as a toy. It wasn't until the start of the .com boom that it really became something different. Being seen as a toy might actually be good in this case.

I love text based content, too. Maybe this is a chance to return to using the terminal by default (I learned about the Bloomberg terminal recently; I guess people still use text-based interfaces a lot).

I like the idea of using a different tech stack, though it would have to be very simple to keep up with (and surpass) current levels of innovation. Hence, the terminal?

> my memory of the early net was that most 'regular' people kind of saw it as a toy I think you're a few years ahead of me, then. I don't remember much of that time. But the difference might be (and I hope not) that the general web was a much more unique tool back then, and people knew about it from sheer novelty. I think the chicken/egg problem of users is harder to solve in this case. Not saying it can't be done, just saying it has to be solved intentionally and with effort.

Well, it seems there are two of us on the Internet. I do almost everything except browsing the web straight from the terminal.

> people knew about it from sheer novelty

This is a really good point. The essence of the question probably boils down to how many people like us there are out there, who want an alternative badly enough to work on it (and in it) while it's small and sparse. The only real feature I can think of that might seriously set it apart from today's net for everyone else is privacy protection, which could be built in from the ground up.

You mentioned something earlier.

> the other net would be more interesting to just browse around and share stuff on.

What if that was the focus of the system? Make it super easy to publish and find Information. Webpages are honestly kind of hard to work with, and the tendency is to make them way too flashy. Remake the incentives of the system based on what was learned from the first version, and something really cool, and super useful, might be the result. I imagine that a terminal-interface focus might be instrumental.

I like that idea; like a separate com-net and pub-net, or something. IPFS seems like a great way to spread the cost among the users; it reminds me of an even more decentralized version of Usenet, or something.

We're better off the way things are, when compared to before. I'm not saying things are perfect, or even good, but we're definitely better than before.

You complain about ads, but think about what they enable. How many times do you use google per day? It lives off ads. Do you use any social network? They live off ads.

Ads are certainly not the best way for us to obtain those kind of commodities, but between having them and not having anything I still choose them.

> You complain about ads, but think about what they enable.

Saying that the ends justify the means certainly simplifies things. It's not a compelling argument to me; I suppose that I'm too much of an idealist.

> Do you use any social network? They live off ads.

Indeed, they do. And I use the benefit of my education to block them every way that I can, pushing the cost onto others. Without ads, or at least some kind of financial support, networks like that would fall apart. Necessity being the mother of invention, and interpersonal connections being necessary, we'd invent another solution. I like the idea of small, independent, federated social networks, but I don't know that they'd actually be practical.

The great thing about the modern web is that ads are centralized (for various values of centralization) on ad networks. So it's damn easy to have an ad-free experience by dumping them to in hosts.

It doesn't get rid of silly css and "too clever by half" javascript for the "content site" but dumping the ad networks makes a difference.

Every time I suggest this some ... person... says "but the ads pay for the Internet!" I just look at them as if they're wearing a suit made of dead kittens.

Three of those four URLs are .edu, and if you look at ../ in the other one, it says it's a college project. The web needed no advertising or tracking or marketing because basically everyone on the web was an academic.

The new web is no longer restricted to the ivory tower; you can get a lot better answers on StackOverflow than you could have ever gotten from the old academic internet. But it does have to feed its new master, capitalism.

> Three of those four URLs are .edu, and if you look at ../ in the other one, it says it's a college project. The web needed no advertising or tracking or marketing because basically everyone on the web was an academic.

That's simply not true. By the mid-90s academics were already a small minority on the web. The OP's sample links are biased because it's a somewhat academic topic.

There was plenty of free and cheap hosting around back then, and for those types of pages bare-bones shared hosting works just fine. For the longest time I paid about $60 a year to host a static site, and it worked great. Hardly the type of money that I needed sell out to advertisers to recoup my costs.

Even GeoCities, while mostly crap, hosted its fair share of useful content.

> The new web is no longer restricted to the ivory tower; you can get a lot better answers on StackOverflow than you could have ever gotten from the old academic internet. But it does have to feed its new master, capitalism.

Nowadays there is technically a lot more information available, but there's significantly more crap to dig through to find it.

And FWIW, I disagree that StackOverflow is "better" than the old style internet. Most StackOverflow answers are shallow - they answer the question, but there's no researching or learning, it's usually just an answer handed to you. It's like the old "teach a man to fish..." thing.

I think it's interesting to note that (anecdotally, at least) things that are "less practical" attract far more in-depth SO answers than those that are more "useful in the real world" (insert connection to capitalism) - Haskell/"help me push this into the typesystem" questions tend to attract very well-thought-out answers oftentimes, and usually multiple answers at different levels of abstraction.

(Not that I'm discounting things like the excellent low-level questions on things like cache misses/alignment/"why are sorted lists faster to process", but I think they're rarer.)

If anyone here knows their way around the StackOverflow API and has some time, I think it could lead to an interesting couple of hours.

The issue is that there's more and more information put online by someone wanting to get something out of it - and for the absolute minority who are putting stuff up without expectation of direct return, it's easier to use a proprietary service than learn HTML.

Three of the linked examples aren't that readable, not that I disagree with your point.

I'm surprised nobody posted smoothlife! It's a continious version of GOL


!! Cool! Thanks for this, I hadn't seen it before. A bit more than a decade ago (ugh), I wrote a plugin for Adobe Aftereffects which implemented a continuous version of GOL a whipped up on the luminance channel. Made for some really really trippy effects.

Academic institutions truly keep the spirit of the old web alive!

Glad you liked it.

What fun!

I did a similar project in minecraft with my teenaged son a few years ago. We started by designing gates (made of torches and redstone), then a clock, then a divider chain, then a demulitiplexer which drove the 7 digit segments. We cheated slightly because the clock counted in hexadecimal. It was a great father son bonding project, being able to teach each other about minecraft and electronics!

It looks a whole lot harder in life though, but I guess when you've mastered the basic gates it must build up the same way. Building it in 2d makes an extra challenge though.

Since Conway's Life is Turing Complete (IIRC), it would be theoretically possible for someone to write a compiler for it, no?

This seems obviously very hard, but since this seems to be catching up, how long until someone decides it's "easier" to write some sort of language + compiler that outputs the initial state needed to do whatever you want in a Life's board?

On another note...this is truly mind-blasting. So, what else do people like him/her do when looking for a challenge? I can't even start to fathom what kind of intelligence level do you need for this, let alone imagine what would I find challenging if I were able to reach these level of mental performance.

Or maybe it's just my puny brain trying to make sense of it... but it just seems so amazing to me the type of minds that you can encounter when public forums like SO are there for almost everyone to access.

Not that it isn't impressive, but it begins to make much more sense how one would go about this once you realize there are higher level functional pieces studied in Conway's GOL. Thinking about the solution in terms of just the rules to the game would require beyond-human intelligence (I speculate); but if you can use these higher level constructions, it's reasonable depending on how well you know them. E.g., from his response:

It uses p30 technology. Just basic things, gliders and lightweight spaceships

You can find lots of info on all these higher level things, e.g.: http://conwaylife.com/wiki/Spaceship

> Since Conway's Life is Turing Complete (IIRC), it would be theoretically possible for someone to write a compiler for it, no?

Does Turing completeness matter for this? I can see how it might matter if the question was about writing a compiler IN Life, but not for writing a compiler FOR Life.

It does if your source language is Turing-complete and you expect the compiler to successfully compile every valid source program.

Computation is what the compiler would get you to start, another aspect would be to tie that to display somehow. The clock here had to be visually displayed. So some sort of display driver situation is needed that is drivable from the compute engine.

There are basic units that were discovered and then those lead to more abstract/complex structures like what we're seeing here.

"Collision-Based Computing" may be of interest to you. (Springer's prices are outrageous, but you may be able to get it via interlibrary loan.) https://www.springer.com/us/book/9781852335403

its an amazing analogy to lots of things, but especially programming. makes me realize the game is more aptly titled than i had thought.

You can compile code to run on this universal computer:



I knew someone probably tried this already.

I'm once again amazed at how "routine" this stuff seems to be. In the top solution go to the life simulator and paste in a copy of the gist and then click 'fit pattern' and run. Amazing stuff.

I've had to check the Wikipedia article on Conway's Game of Life a few times to make sure I'm remember it right: Yep, four simple rules is all it takes to describe a Universal Turing Machine.

How whacky.

Stephen Wolfram postulates that quantum mechanics and therefore all of physics and the whole universe emerge from a few simple cellular automata rules.

How truly wacky (if true)

I believe I read somewhere (Chaitin?) that what you stated implies a deterministic universe. It doesn't seem plausible.

The Many-Worlds Interpretation of Quantum Mechanics is deterministic. It's one of the (many) qualities that makes it so attractive.

You don't think it's plausible that the universe is deterministic?

Why not? All the laws of physics we know of are already deterministic.

Except (maybe) all of quantum mechanics

Just because there are things we can't measure from inside this universe doesn't mean that those things aren't deterministic.

> Just because there are things we can't measure from inside this universe doesn't mean that those things aren't deterministic.

There is no reason to believe that non-local hidden variables are the reason for the probabilistic nature of QM.

Many worlds is another classic interpretation that works.

What would be the nature of those things, given that we find no correlation at all with things in this universe?

I could believe we just aren't measuring with enough precision (and perhaps, it's impossible to do so). But that's still deterministic and inside our universe.

It does if we're living in a simulation.

You can get Turing completeness in a one-dimensional cellular automaton: https://en.wikipedia.org/wiki/Rule_110

Direct link to the clock running in a browser:


If anyone would like to see/interact with some more interesting patterns (often with explanations), I just finished this WebGL Conway's app a couple weeks ago: http://symbolflux.com/conwayz/

The code is copypastable into the program Golly, which can run it much faster than Javascript.

The reason that this is great, is that it is awesome to try to mess with such patterns in life, by breaking something in one location by locally altering a few pixels and seeing how the failure slowly spreads throughout the whole mechanism.

Hashlife in javascript starts hicking up on that, Golly can simulate it at very watchable speed :)

An entire society is my alarm clock :D

"That's just slavery with extra steps!"

Terrific find ChuckMcM. Only took 7 months to answer. Next up, Tetris.

Talking about Conway's. I've seen a small talk by Nicolas Schabanel about gliders with DNA bricks. Quite madenning.

Amazing. Sadly I work 7 days a week and have no time for fun stuff like this.

One day you'll find the time.

One day you'll make the time.

One day we will all die.

Except gliders floating in infinite space. Maybe.

For some on the world it's today.

Time is an emergent phenomena - an extra dimension - of the bulk interior of our de Sitter space. On the boundary of the de Sitter space, there is no time.

Sounds like OC's day-job has placed them on the boundary of de Sitter space, then.

*choose to work 7 days a a week

Google Easter has a nice little easter egg when you search for for "conway’s game of life".

Now build a digital clock in Dwarf Fortress.

First you have to implement DF in GOL.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact