Undecidable Turing-Complete Christmas Tree Automata in Practice

"Have you ever heard of Rule 30?"

A friend chirped me in skype asking if I was familiar with "Rule 30". He's going in for a job interview and they'd asked him to code this Rule 30 as an exercise. I hadn't heard of it, but I was intruiged, and I'm always one to try to help a friend. Off to the Google-Mobile, Batman!

As I would learn, Rule 30 refers to something introduced by Stephen Wolfram in 1983] (1). Even if you're not familiar with Wolfram, you're probably familiar with his work. Especially, if you took any college level Calculus classes. He was a computer scientist, and word is he was pretty good at the maths. If you don't know him, check him out, cool dude.

Anyway, on to this Rule 30 business. Rule 30 is one of many rules that pertains to binary cellular automaton (2). Now, when I read that the first time, they lost me halfway through binary. If you're like me, never fear!

Elementary Celluar Automaton

So, how's this work? For each cell there are two possible values: 1 or 0. Each of Wolfram's "Rules" (there are 255 of them) defines a list of rules that tell you how to determine whether a given cell is 1 or 0. It does this by analyzing the "neghborhood" of the cell in question. What is meant by neighborhood is discussed in more detail below.

What it means to be 1D

You may be famliar with other Cellular Automata, such as Conway's game of life Game of Life(3). This method is similar, but there is a primary difference. Game of Life is 2-dimensional, with a third dimension of time. That means that as the rules are applied and the pattern progresses, the "board" is refreshed.

Rule 30 and it's siblings are 1-Dimensional. In this case, the y axis is, in fact, time. That means that as the program is run the new output is appended to the old, rather than the entire "board" refreshing.

Why "Rule 30"?

Since there are2×2×2 = 8 possible binary states for the three cells neighboring a given cell, there are a total of 2^8=256 elementary cellular automata, each of which can be indexed with an 8-bit binary number.

So, Binary: 00011110 = decimal 30. Therefore, Rule 30. This holds true for all of the other rules, too, by the way. Not terribly important, but I found it interesting, so there you have it. Moving on.


Yes! Rules inside rules!


Above are the rules given for Rule 30. This is how you determine whether your "cell" is a 1 or a 0. Upon first inspection, this made absolutely 0 sense to me. (binary pun possibly intended?).

What you need to understand here is what is meant by "neighborhood". When you're determining the 1/0ness of a cell, you look at it's neighborhood and compare that against the rules. Neighborhood being the three cells above it. So, 111 = 0, 110 = 0, so forth and so on. Once you get your mind around that, you're off to the races.

Once you have your rules, you apply them to the given input (in this case a single "line" of the grid with at least one cell set to "1"). What do you get?


So Pretty.

But how do you DO it? Well, let me show you.

The Codez.

*** Warning!** I have absolutely no intention of using OO practices here. No classes will be made, no injection will be used. I will interface nothing. If this makes you uncomfortable, you may want to stop reading.*

End result, I want to create this cool looking graph thing. That's how a picture it, a graph, or grid, Once you're there, it becomes a matter of some setup, and then some iteration. It looks like this:

//First thing's first, let's codify those rules. 
$rules = array(
    '111'=> 0,
    '110' => 0,
    '101'=> 0,
    '100' => 1,
    '011'=> 1,
    '010' => 1,
    '001'=> 1,
    '000' => 0

//create an empty array to hold your grid
$lines = array();

//set up that first line 
$first_line = array_fill(0, 51, 0);

// make sure you set at least one of those cells to 1,
// or this will going no where fase. 
$first_line[24] = 1;

//now add your line to the grid. 
$lines[] = $first_line;

//Lets compile that grid

// I'm doing 10 iterations, you can do as many as you like. 
for ($i = 0; $i< 10; $i++)
    // make a new line
    $line = array();

    for($j = 0; $j< 51; $j++)
        // The "pattern" is determined by the "neighborhood" or the 3 cells in the 
        // generation (row) above our cell in question. 
        $pattern = (string)implode('', array_slice(end($lines), $j - 1, 3));

         // if we have a valid value, great. Elsewise, give is a 0. 
         $line[] = (strlen($pattern) == 3 && isset($rules[$pattern])) ? $rules[$pattern] : 0;

    Add the new line into the grid
    $lines[] = $line;

// Now, let's output it
foreach ($lines as $line)
    foreach ($line as $piece)
        echo $piece;
    echo "\n";



Merry Christmas!

For mine, I changed 1 to '/' and 0 to '*'. Why? Because it's December, and it looks festive, that's why. I just taught you how to output a Christmas tree in your terminal!

Clearly, with the added nerdery, this is no longer a Christmas Tree. This is what we call a FSM Tree. The perfect DIY gift for your budget conscious nerd.


And there you have it. Merry Christmas, Nerds.

Post Script

You may be wondering why the post title references Turing completeness(4). As I mentioned before, our beloved Rule 30 has 254 siblings. One of these siblings is known as Rule 110, and this rule is turing complete.

The process for running through Rule 110 is the same as Rule 30 (that holds true for all 255 rules, by the by), the only change is the rules. So, if you're interested, here are the rules for Rule 110 (in Christmas tree format, of course)

$rules = array(
    '///'=> '*',
    '//*' => '/',
    '/*/'=> '/',
    '/**' =>'*',
    '*//'=> '/',
    '*/*' => '/',
    '**/'=> '/',
    '***' => '*'

Go forth and make a Turing machine.


  1. Wolfram, S., "Statistical mechanics of cellular automata", http://journals.aps.org/rmp/abstract/10.1103/RevModPhys.55.601
  2. Elementary Cellular Automaton, http://mathworld.wolfram.com/ElementaryCellularAutomaton.htm
  3. Conway's game of life, http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life
  4. Turing Complete, http://c2.com/cgi/wiki?TuringComplete
You’re not alone

Ending the stigma.

When you open up a story on Medium (for those of you who’ve never used it), the ghost prompt says “Tell your story..”

I’ve been staring at those words for five minutes now, not really reading them. It wasn’t until they finally registered that I knew what I needed to say here.

I want to talk about depression, but it’s difficult. It’s crazy difficult. And to talk about it in a personal sense? A sense that relates to my personal experiences? That’s almost impossible.

But it needs to not be impossible. It needs to be okay.

I was 13 when I tried to kill myself for the first time. I’ll never forget that day. I took a bottle of aspirin over the kitchen sink. I don’t remember wanting to die, or knowing that I was killing myself. I’d stayed home from school sick that day. I wasn’t really sick, I just didn’t feel like being around anyone outside of my own skin. I had a headache, and I went to the kitchen. I remember the aspirin (it was the generic uncoated kind) turning into mush in my mouth. I couldn’t swallow it all, and it tasted to vile. I coughed up a bunch and got a glass of water to swallow the rest down.

The next few hours of my life were a horrible, wretched, world spinning ride of nausea and pain. My parents came home, and they knew immediately something was wrong. My dad got me to throw up, and then the pain stopped. I remember throwing up pieces of my stomach lining, and my dad crying. I think he cried, anyway. I cried.

A year and a half later, I was diagnosed with depression and bipolar disorder, after being sexually abused.

I started smoking, and I started cutting. I have 13 scars up my right arm, including very crummily etched letters that spell “Fuck”. There are a few scars on my shoulder, too, and one on the inside of my wrist. I remember taking just enough aspirin to make the world spin and wash, but not enough to die. I wanted to die, and I hated myself for being too much of a coward to do it.

With my diagnosis came a prescription for Zoloft. But, when I looked at those little orange bottles, I didn’t see a way to get healthy, or any help for me. I saw a label, plastered across my face, that said I was sick. There was something WRONG with me, and I had to be fixed.

I didn’t take those pills. I stockpiled them, and eventually, I swallowed two bottles at once. I got my stomach pumped that day.

Eventually, I decided I wasn’t sick. Fuck being sick. Fuck being broken. I’m not that. I resolved to never take one of those pills ever again. I left highschool and went to college. I got pregnant, I had a daughter. I got married, and then divorced. I moved to the big city, I got married again, I had two boys, I finished school, I became a successful developer. I love my job, and I love my family, and most days, I love my life.

But here’s the truth: I can’t count the number of times I’ve wanted to die. I can’t count the number of times that I’ve sat alone and cried, because I couldn’t think of a single happy thing. Sometimes, I can’t think of anything at all, just an expansive nothingness. It eats at you, and if you let it, it will consume you.

I’m afraid to let everyone know. What if they don’t think I’m okay to do my job, once they know? What if my “successfull” career falls to shambles, because they think there’s something wrong with me? What if they take my kids because I’m sick? What if they judge me?

I’ve tried to tell people a few people close to me, but they shake their heads. They don’t believe me. When I was a kid, it was easy to see how messed up I was. I was slicing my arm to pieces, for Christ’s sake. But now; now I”m successful. Now, I’m a good mother and a good wife, and I have a successful career. There’s no way that I’m sick. They don’t believe it.

Today, reality came crashing in. Someone many people knew and loved died because of this disease, and hundreds of thousands of others have died before him. So here I am: I’m sick, and I hurt, and my hurt is no less real than if I were bleeding.

It’s odd to me, that I feel GUILTY for being sick. You don’t feel guilty for getting the flu, or pnuemonia, or cancer. Those are things that happen TO you, but for some reason, we’ve all decided that depression and mental illness are somehow our fault. Like I could have done something to stop it, or solve it.

I couldn’t. I can’t. I am me. I am beautiful, and funny and brilliant and successful. I am a good mother, and a good wife, and I have depression.

I don’t want your pity. I’d like support, and more than anything, I’d like awareness. I’d like to live in a world, where I can say, “Hey, I’m bipolar” without people looking at me like I’m a leper. I’d like to know that generations that come after us won’t be judged, or scared, or guilty, for having this sickness. One where they can seek help as easily and freely as people do when they have readily visible illnesses.

I have tweeted, and I will be tweeting once a day: my diagnosis, along with #endthestigma. If you’re willing to share yours, do. A simple tweet diagnosis and the hashtag. If you’re not, then feel free to retweet mine. More people need to know that it’s okay. That it will be okay.

And if anyone feels the way I have felt in the past, reach out. I will listen, always. I don’t care if I know you, or I don’t. I don’t care what time it is, or where I am. I have my cell phone on always, if you need someone to talk to, message me. Just say “Kayla, I need help.” You’ll have my full attention, I promise.

Stop Letting Numbers Define you

My mom is in town this week, and on her last day here, we decided to go clothes shopping. She found a few shirts that I adored, and offered to pick them up for me. I grabbed my customary ‘M’ off the rack and started to leave.

I stopped myself just short, staring down at the shirts in my hand. “Yeah, I should probably try those on.”

It was good that I did, because my customary ‘M’ reduced me to a sausage. Time to move up to the new customary “L”. I switched the shirts, and we made for the register. Except, as we walked, and she made joyful small talk, I felt like I wanted to cry. Like I’d been punched in the gut. I felt miserable.

It’s the same way I felt upon realizing recently that I have two pairs of jeans left that fit comfortably. The same way I feel whenever I step on the scale. I weigh about 180lbs right now, give or take a few ounces. It’s the same amount I weighed when I gave birth to each of my sons. I’ve officially gone up a size and about 15lbs in the past year.

I came to terms with the fact that I will never be a size 0 a long time ago. At nearly six foot tall, it is literally impossible for me. However, I still can’t handle going up a size. “I used to be a nine!”, I say. Single digits! That was awesome. And here I am, back in a size twelve. This is not awsome.

When I feel like this, my inner pep talk kicks in. I tell myself: “Girl, you’ve had three kids. Give yourself a break”. Or “There are too many things in this world worth eating to be skinny. Eat all the things”. Or, my favorite “You’re beautiful on the inside. You’re smart and your funny, and you’re nice. That’s enough”.

You know what, pep talk voice in my head that’s trying in vain to make me feel better and is really only succeeding in making me feel worse? I have something to say to you: Go straight to hell. You, and the feelings that bring you out, can go jump in a big lake of fire. Feel free to take the media industry that conditions little girls to strive for flat stomachs and huge tits right along with you.

Cause here’s the thing. All of those pep talk things are true. There IS a plethora of amazing food out there, just waiting to be devoured, and I really enjoy devouring it (Not to mention beer. Don’t get me started on beer). I AM a nice person. I’m generally kind, and honest. I tell a hell of a joke. I’m a wonderful mother, and yes, my body has brought three amazing little people into this world. Those three people are also kind, and honest, and incredibly funny, in part due to me. More than any of that: I am happy. As a person who hasn’t spent a good percentage of her life being happy, happiness is golden.

Maybe (probably) I should feel guilty because I spend more time working, and mothering, and yes, eating, and not enough time exercising. But these are choices I’ve made, these are priorities I’ve set. I should be able to own those things, and the bigger clothes those choices bring, without this deep nagging feeling of self loathing.

I should worry about my weight because of my health, or because of the example I set for my children. I should NOT worry about my weight because of what size some yahoo at the clothing company decided to throw on a label or where the dial stops when I step on a scale. Because neither of those numbers define me. Neither of those numbers will make me any happier than I am now.

And really, possibly the hardest thing for me to accept: Neither of those numbers will make me any more attractive. I felt ugly and miserable at a size nine. So, no, it wasn’t really that awesome, no matter how much I tell myself it was. I feel ugly and miserable at a size 12. The size doesn’t change how I feel.

Being happy, though.. that changes everything. I feel beautiful when I’m playing outside with my kids. I feel like a rockstar when I serve them a great meal. I feel great when I make someone smile. And when I’m smiling, I couldn’t give a damn about how I look.

The Truth: I am the most attractive when I’m happy. When I’m smiling. When there are absolutely no fucks given over what size my damned jeans are.

So, from me to you, Pep-Talk Voice: Fuck you. Fuck the excuses I make to myself to explain away why I’m gaining weight. I don’t need excuses. I don’t need permission to gain weight, not even from myself. I DO need to be happy. I DO need to own my choices and either be okay with them, or change them.

I DID need to write this, so thanks for reading.