Knitting Is Turing Complete?
Saturday, 31 August 2013

All sorts of "simple" activities can be viewed as computation - but knitting? Yes, knitting...

I have to confess I have used knitting patterns as examples of programs and to convey the general idea of programming and programming languages - but have you ever seen a knitting pattern? Now we have a much deeper look at the relation between knitting and computation via the aptly named A Computational Model of Knitting

Photo by Johntex.

The argument goes that it isn't just the human that forms the computational hardware that runs the knitting pattern program, but the knitting needles and the stitches. That is the knitting needles and different types of stitches form the computational hardware of a computer.

"First off we can observe, that hand knitting needles both have a storage and a stitch processing function."

The basic idea is that when you knit with a pair of needles each stitch is a bit like writing a one on a Turing machine tape.

But it doesn't stop there - you can knit with more than two needles and with needles that aren't straight.  If you have three needles then the third needle acts like additional storage. A needle with one end blocked acts like a LIFO or stack; a needle with two pointy ends can be used as a double ended queue or deque.

From here things get increasingly fanciful, but you do need to realize that knitting is far more complicated than it seems at first look. For example, the ball of yarn is free memory and each stitch can be regarded as a data structure of pointers to the stitches it is connected to, i.e. a linked data structure.

The observation that knitting is sequential in nature leads to the speculation that it is an implementation of the Von Neumann architecture but with each needle forming a computational unit that tend to work in pairs - hence Von Neumann Knitting.

The whole thing has a four-clock cycle operation sequence which corresponds to knitting a standard stitch. There are also operations for creating different types of stitch as well as plain - purl, twisted purl and so on  - you can read the details on the original blog post.

The reason for all of this elaborate restructuring of knitting into computational science?

Does it need a reason?

One thought is:

"... that once we have identified the atoms of the knitting process, we can use them as building-blocks for all kinds of hand-knitting stitches and knitting instructions."

This sounds much too practical. I'd much prefer to consider the abstract computer science questions. What is the halting problem in terms of Von Neumann knitting? Is there a non-computable sock? Is the free memory to be considered finite or unbounded? And what about the scarf complexity question....

A Computational Model of Knitting

#### Related Articles

A Water Droplet-Based Computer