Makefile Assignments are Turing-Complete | Hacker News Reader

Makefile Assignments are Turing-Complete

nullprogram.com

60 pointsbidouilliste16 comments

Well, if you want to do computation inside GNU make there are tools like the GNU make Standard Library: http://gmsl.sf.net/ and I wrote quite a lot about GNU make stuff here ($$$): https://www.nostarch.com/gnumake and here (free): http://blog.jgc.org/2013/02/updated-list-of-my-gnu-make-arti...

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...?

> Doesn't Turing completeness require the ability to modify an arbitrary amount of memory?

Why would it? Lambda calculus is nothing about modifying anything.

And GNU make (though with GNU extensions) is certainly Turing-complete: https://github.com/shinh/makelisp

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.

Yeah, now that I took a look at the source you seem to be correct. The whole machinery appears to be hardcoded for the 4x4 case.

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'.

Nice hack

OHHH! That is so sick. 174Kb of macros to implement a Conway's Game of Life

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.

So you'd say that it's a good thing? How is hidden complexity good?

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.

Eh, you pretty much have to specifically design systems to avoid turing completeness. It's a hilariously low bar to clear.

Welcome to the Turing tar-pit in which everything is possible but nothing of interest is easy.

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.

Reply on news.ycombinator.com