Paul Rendell implemented a Turing machine in Life. Gliders represent signals, and interactions between them are gates and logic that together can create larger components which implement the Turing machine. Basically, any automatic machinery that can implement AND, OR, and NOT can be combined together in complex enough ways to be Turing-complete. It’s not a … Read more
First, I assume you’ve already heard of the Church-Turing thesis, which states that anything we call “computation” is something that can be done with a Turing machine (or any of the many other equivalent models). So a Turing-complete language is one in which any computation can be expressed. Conversely, a Turing-incomplete language is one in … Read more
Well macros don’t directly expand recursively, but there are ways we can work around this. The easiest way of doing recursion in the preprocessor is to use a deferred expression. A deferred expression is an expression that requires more scans to fully expand: #define EMPTY() #define DEFER(id) id EMPTY() #define OBSTRUCT(…) __VA_ARGS__ DEFER(EMPTY)() #define EXPAND(…) … Read more
In issue 13 of The Monad Reader, Stephen Hicks writes about implementing the solution to an ICFP contest (involving Mars rover navigation) in TeX, with copious use of macros. Amusingly, the solution’s output when typeset is a postscript map of the rover’s path.
I’ve done a turing machine in C++11. Features that C++11 adds are not significant for the turing machine indeed. It just provides for arbitrary length rule lists using variadic templates, instead of using perverse macro metaprogramming :). The names for the conditions are used to output a diagram on stdout. i’ve removed that code to … Read more
You can encode Rule 110 in CSS3, so it’s Turing-complete so long as you consider an appropriate accompanying HTML file and user interactions to be part of the “execution” of CSS. A pretty good implementation is available, and another implementation is included here: body { -webkit-animation: bugfix infinite 1s; margin: 0.5em 1em; } @-webkit-keyframes bugfix … Read more
Here’s the briefest explanation: A Turing Complete system means a system in which a program can be written that will find an answer (although with no guarantees regarding runtime or memory). So, if somebody says “my new thing is Turing Complete” that means in principle (although often not in practice) it could be used to … Read more