With a Turing-Complete language, if a program runs out of memory on one machine, you can run the same code on a bigger machine without modifying it, and it can use the additional memory. With fixed-length rule 110, you need to modify the code if you want to use more memory.
"Stuff which is somehow limited (stack overflows, arbitrary configuration, etc) is still considered Turing complete, since all "physical" Turing machines are resource limited."
In my opinion, worrying about infinite memory, in regards to Turing completeness, makes the task of implementing computation much less interesting.
Also, I'm pretty sure CSS only does one generation (or a finite number of them) before stopping anyway.
"As the DOOM engine was not designed to be an interpreter, there are some constraints on our programs written against it. The biggest one is how large our programs can be. Since each gate uses at least one tag, we can use this as a metric to derive an upper-bound on the size of a program. As the DOOM engine uses 16-bit tags, this means we can have, at most, 65535 gates. This is not a particularly large number. We may be able to implement a very small CPU but this limit will be hit pretty quickly I believe."
The z80 had ~8,500 transistors. The 8086 had ~29,000 (checking Wikipedia). You could get far fewer if you use a 1-bit microarchitecture, I'm sure. I think there was a DEC (PDP?) computer that used that trick to have a really low transistor count, but I don't remember what it was called.
The real problem is RAM; for this you may as well cheat and modify Doom's code to add a RAM chip, and I/O while you're at it.
You could create a CPU in Doom implementing an architecture for which a C compiler exists, capable of compiling Doom, and run it in the CPU in Doom. For "reasonable" speed you'd have to do more than one simulation step per frame render (in the host Doom). If you ran it for long enough maybe you could get a full frame of Doom in Doom.
> half trillion lines of types totaling 177 terabytes ran through the type checker around the clock for 12 days to get the first frame
panstromek•6mo ago