Hacker News Reader

Comment by Tunabrain | Hacker News Reader

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

View on HN

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

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.

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

Reply on news.ycombinator.com