“Is Crochet Turing Complete?”: Christina Burger with Runway (Video + Transcript)

In this talk, Christina Burger (Runway Senior Software Engineer) discusses the intersection of computer science and crochet. She explores the idea of representing a Turing machine as a crochet pattern and demonstrates her attempts at creating crochet symbols for the different states.

Like what you see here? Our mission-aligned Girl Geek X partners are hiring!

• Check out open jobs at our trusted partner companies!
• Watch more ELEVATE 2024 videos from the event, or just the “Best Of 2024” Videos!
• Does your company want to sponsor a Girl Geek Dinner or Virtual Conference? Talk to us!

Transcript:

Christina Burger:

Thank you so much. What a wonderful intro. I guess that makes my next slide less relevant. But yeah, I’ll just introduce myself quickly. I’m Christina. I not just love making software, I also enjoy all sorts of other things, including hanging out with my cats, who ignore me. And also I have a art supply shopping problem, which has recently extended into a yarn buying problem. And yeah, I also recently made a zine with my good friend Erica, and I’ll tell you a little bit more about that at the end if we have time.

All right, so this is where you find yourself at the intersection of computer science and old lady crafts. And I really love this place that I find myself in. I love both of those things equally. And I’ve also often felt like I can … it’s hard to not see them as similar things because when you’re looking at something like crochet or knitting, it’s actually quite a technical endeavor.

And I have lots of family members who always claim that they’re not technical or they’re not smart, but they’re able to make amazing, wonderful things from scratch. And so I think that there’s something to be said for respecting the technicality of certain crafts and hobbies. So yeah.

So, to kick off this talk, let’s talk about what is crochet. I just recently learned crochet myself. Previously I had tried to learn knitting, and I found it a little bit overwhelming with all of the counting and dropping stitches and things like that. And I tried crochet, and I really loved it. I feel like it’s really soothing, if you have a very active brain at the end of the day, you can just do some crocheting to wind down.

And the history of crochet is very long, and there’s lots of different countries that claim that they invented crochet. But it’s been around for a while. If you haven’t crocheted before, you use a hook like this, and yarn. And you’re just basically making fabric from yarn.

And crochet consists of a few stitches. So you can go from different heights, so you have single crochet, which is the lowest stitch, and then it goes all the way up to a super high stitch, which is a quadruple treble crochet. And yeah, these are US stitch names. I think the UK uses a slightly different system. But I learned how to crochet in Canada, so these are the ones that I use. Yeah.

And crochet can be used to make really intricate, wonderful laces. And it can also be used to make a little hat for your cat. So it’s very versatile. But learning crochet and learning crochet patterns, I felt like something about them was very familiar in that it almost felt like I was reading an algorithm. And I think that’s because it is an algorithm.

So for the next part, we have to talk about the next part of this talk, which is what is Turing completeness. The first time I heard this concept was at university, and it was very foreign to me to understand why it matters. So I’ll endeavor to explain that a little bit better.

But to introduce the concept, Turing complete just means that a language or a thing can be used to make a Turing machine in theory. And so I guess what we need to talk about more is what is a Turing machine? So a Turing machine is a theoretical model of a computer, but before we had computers. And it’s very important to be able to think through something like a Turing machine because it explains to us how we could solve general problems with one machine, instead of making a new machine for each problem that we have to solve, which was the approach that we had before we had this way of thinking.

So a Turing machine is a very theoretical thing, it’s not a physical thing. It was never built to prove that it could exist. I think people have built ones in modern times just to show that you can. But it’s more of a way of illustrating what a computer could be.

And the parts of a Turing machine are very simple. It’s this tape that you see here. And it has symbols written on the tape. And you’re able to read and write onto that tape.

And to illustrate a little bit more, because it can be a little bit hard to understand that just from a quick introduction, here is one algorithm that we will be stepping through in a Turing machine. So first of all, we’re going to start with 110, that’s the number. And our goal is to invert the number to 001. And so you can see that for this machine, we have three symbols, a zero, a one, or an empty tape or an empty cell in the tape. We have the tape and we have the ability to read a symbol under the head.

And so how this program works is we have 110, and we have this state table that tells us what to do in case of each symbol that we read. So if we read a zero, we’re going to invert it. So we’re going to write one, so write zero, write one. And then we’re going to move the tape to the right. And we’re going to do the same thing. We’re going to read one, and then we’re going to invert it and write zero; move the tape to the right, read one, write zero; move the tape to the right, and now we read an empty cell. So that means we can stop. And that’s pretty much how a Turing machine would solve this particular problem.

Right. So I was thinking about this and how familiar it felt. And I thought, could you represent all of that as a crochet pattern? And it turns out you absolutely can. And it also turns out that it’s really fun to figure it out.

So before we go through the pattern that I ended up making, I will show you a few of my attempts. I tried to make various ways to represent the different symbols in crochet, and all of them turned out a bit wonky. One I tried to do with color, and I think you could totally do that with color. But I gave up after one row because I realized that it’s cheating, it’s not really thinking too much about crochet stitches and more about the colors. But yeah, you could definitely do that if you want.

So let’s go back to what we had before, the Turing machine that we were or the problem that we were solving with Turing machine in this previous slide. But now we’re going to solve it in crochet. And I did end up with a more acceptable crochet block. And all of you are welcome to use my pattern to make your own crocheted Turing machine.

So what is our algorithm here? So to start with, we’re going to chain 15. Chain just means putting in the foundational stitches to start, so these ones at the bottom. We’re going from left to right. So from row one, we’re going to add a few stitches for height, and then we’re going to chain one, and do a double crochet, chain one, do double crochet, all the way through. And that’s just to set up the tape.

These shaded areas of double crochet, these are just structural to keep the piece in a sort of grid. So I shaded them so that you can ignore them and understand that only the ones that are not shaded are important for our tape. Okay. And then in the second row, we are going to write or not, I guess, not write, we’re going to make a double crochet to represent a one, another double crochet to represent another one, and a picot, which is this little piece at the top, to represent a zero, because we need three states, we need to be able to also represent an empty cell, which is a chain.

So yes, we’ve done that. And then the crucial part is that we need a stitch marker, which looks like this. And that’s how you can mark a place within your work. So you can mark, oh, I’m here, yeah? And that’s going to be our head. So in our crochet Turing machine, we’re going to not move a tape, but move a stitch marker. So we are putting the stitch marker at the picot, and that’s going to be where we start. And then we’re going to go over to row number three.

So for row number three, four, and five, we’re just going to follow the algorithm, which is this part here at the bottom. So the algorithm goes, copy each stitch that you see from the previous row unless you’re at the marker. If you’re at the marker, if you see a picot, do a double crochet. If you see a double crochet, do a picot. And if you see nothing, then you’re done.

So let’s go through. To the next row. Copy, copy, copy, copy, to the marker. We see a picot. So we’re going to do a double crochet. Copy the rest. Chain three to turn. And then we’re going to remember to move our stitch marker over two stitches to the right.

In the diagram, they’re all to the right, but if you were doing actually the crochet, you’d have to remember to move it to the left, because you turn your work every time you add a new row.

So yes, for row number four, we’re going to see that we have double crochet, so we’re going to do a picot, double crochet, double crochet. Move our stitch marker to the right. And then copy everything. Chain three to turn. Copy everything. And then we see a double crochet, so we do a picot, a picot, and double crochet. So we’re just copying again from row four. And we know that we’re done because in theory we moved the stitch marker to the right and saw that it was empty, so we were done with the algorithm. And yeah, this pattern is available, I will share the link in the chat, if anyone wants to follow it.

And just wanted to show a bit more visually, it can be really hard to see. Also, I’m not the world’s best crocheter, but this is my final product. And I’ve tried to highlight the different stitches and what they mean both in the diagram and in the finished product. And if you look at the colors, to represent the one and the zeros, that might also help for you to see that we started with a picot and two double crochets, and we ended with a double crochet and two picots.

So that was a really quick run through both of Turing machines and crochet. I guess, my conclusion is that crochet is Turing complete, as long as you don’t think too hard about the fact that a person has to still do the crocheting. There’s no such thing as a crocheting machine, we have knitting machines, but crochet is actually really complicated to automate. And so mostly it’s done by humans. So I guess, in that way it’s not Turing complete because it’s not a machine at all. But it’s still a really interesting thing to think about, how we have algorithms in our day-to-day lives that we’re following. And how we can integrate computer science more into our granny-like crafts.

Yeah, so that is pretty much it. Just one final note, I wanted to share my zine. Oops, sorry. Wanted to share my zine here, which I made with my good friend Erica. It’s filled with really positive thoughts and fun puzzles, we have a crossword. So follow the link in the slide here if you would like to buy one. Or if you have any questions, now is the time.

Like what you see here? Our mission-aligned Girl Geek X partners are hiring!

• Check out open jobs at our trusted partner companies!
• Watch more ELEVATE 2024 videos from the event, or just the “Best Of 2024” Videos!
• Does your company want to sponsor a Girl Geek Dinner or Virtual Conference? Talk to us!