3 ms·
Is Knitting Turing Complete? (2013)
- gwern 6y agoThe original post: https://web.archive.org/web/20130810104616/http://www.k2g2.org:80/blog:bit.craft:computational_model_of_knitting https://web.archive.org/web/20130810104616/http://www.k2g2.o... My guess is that it almost certainly is, in even a very reduced knitting model, by reduction to https://en.wikipedia.org/wiki/Wang_tile https://en.wikipedia.org/wiki/Wang_tile or a similar CA or rewrite system. (Actually proving this, of course, is the tricky part.)