Doesn't Turing completeness require the ability to modify an arbitrary amount of memory? (because the length of the tape on a Turing machine is unbounded).
However, if I understood correctly, the size of the Game of Life grid is fixed in the Makefile and cannot be extended arbitrarily at runtime, making it not Turing complete (cool nonetheless!).
Although, maybe a Makefile that generates a Makefile with an arbitrary number of cells...?
It's like claiming my computer isn't turing complete because it only has 8 gigs of ram instead of infinity. I mean pedantically nothing is actually turing complete because the universe is finite. In this case you just have to write a sufficiently large grid, a 40x40 grid isn't required by the technique it's just how big this one was written.
That just means that the game of life simulation isn't a Turing machine in itself. You don't need to be able to change the size of the Game of Life grid at runtime, it's good enough if you're able to do so by changing the code.
Now I suppose you would run into problems with programs that write arbitrary amounts of data, but then again that's a limitation of nearly all practical 'Turing machines'. You can (probably) make a Makefile simulating a Turing machine with a tape of any size you want, so in a sense it's 'close enough'.
In case of lambda calculus the equivalent condition is being able to evaluate arbitrarily large expressions. This sort of a Makefile-based evaluator could only do strings up to some hardcoded finite length.
I would say that this is a good argument against using such a complicated spec. This kind of constructs should be explicit - if in a build system at all. I hate Make because of all the crazy "build systems" that should have been written in a more readable language, but ended up as a Make kludge.
The point is that, as mentioned in the article, the POSIX make spec is positively barren! Indeed, this is another example of very simple substitution systems turning out to be emergently Turing complete.
It's not necessarily a good thing. It's definitely interesting, though. It's difficult to come up with systems that are simultaneously useful and don't have emergent complexity - and it's not clear to me if it's worth the effort to even try in the general case!
For what it's worth, in my opinion build systems should definitely be intentionally, not accidentally, Turing complete.
Junkyard full of random Python, Ruby, or Scala is not any better.
Build rules are code, and thus should be treated like one. Not treating them
like code is the main reason many non-trivial makefiles (or rakefiles, or
SCons rules, or whatever) look like sh&t.