I love this write-up, especially the interactive diagrams at the end. My vid doesn't go into as much detail on the actual circuit design, but like the article it uses a bunch of BCD ripple-carry adders. For output I use standard 7-segment decoders. As noted in the comments there are faster ways to do logic in Quake which I overlooked in my research, but to my knowledge noone has made a circuit this large before. I've put the source code on github for anyone that wants to take a deeper look: https://github.com/matthewearl/q1logic/
They can also be opened by other monsters (I explain why this is useful later).
In other words, this device is the analogue of a transistor in electronic machines --- a signal-controlled signal switch. The notion that NAND is the "most basic level" required for digital computation is widespread, but a lower level exists, and this is it.
My system is not Turing complete, and it's because it doesn't have unbounded loops and state. When monsters arrive at their destination, they stay there forever. There's no way to "reset" monsters. This can probably be done by selectively recalling (teleporting) certain monsters so they can act as input to the next iteration of the calculation. This is probably the next step to proving whether or not Doom is Turing complete.
The other person's article linked near the end shows that he came up with the exact same thought:
We'll place a teleporter right in front of them and they'll find themselves locked away in a circuit of our devising spinning a hamster wheel for our benefit. Forever. Just make sure the circuit is placed where the player will always be a specific direction (e.g., south) so they'll forever keep trying to run in that direction.
Thus, the monsters can be thought of as the "electrons" or "working fluid" of this machine.
One of the ideas I've had in my mind but never got around to is to generate a game level that replicates the 6502, which has been reverse-engineered completely: https://davidmjc.github.io/6502/cd.svg
> The notion that NAND is the "most basic level" required for digital computation is widespread, but a lower level exists, and this is it.
It's not quite the same I think. With NAND you only need the NAND. With transistors you need two kinds of transistors, N-channel and P-channel, or a transistor and a pull-up/down resistor.
That is, you need one device that conducts with "1" as input, and one that conducts with "0" as input. In this Doom circuit he has a device with both functions built into one device, one side opens on "1", the other opens on "0".
This implementation actually reminds me more of "Petri nets" and asynchronous logic. I wonder if using techniques from that domain would be useful for implementing circuits in Doom.
They could trigger a crushing ceiling when a monsters out-state is consumed, destroying the monster. In nightmare mode, the monster would shortly thereafter be respawned to its original location, ready to take on another value from its inputs.
That's different, though. That's breaking out of DOOM, not implementing DOOM in DOOM. You might argue that the "reference implementation" (i.e. ID's DOOM) is the "canonical" doom and thus this counts but... it's still not "DOOM implemented in DOOM", it's running x86 code.
Not to take from that achievement away, though, I just don't think it fits in the context of this post!
I don’t think that means anything though. Doom the game is not a Turing complete programming language. You could write doom in the underlying C and then have it run on a screen in game but that still wouldn’t be doom running doom.
In fact now I’ve confused myself, what would constitute doom running doom?
I think what is being discovered right now is whether DOOM itself is Turing complete, and if so, can you program DOOM inside of DOOM by making a computer inside of DOOM composed of DOOM monsters and map features that, when ran, recognizably played DOOM.
Sum up: creating a computer inside the game of DOOM and programming that computer to itself play DOOM would constitute DOOM running DOOM
I've actually implemented the Game of Life in Doom engine.
But I've used a significantly stronger "computation model" - Boom engine, which provided scrolling floors, and more actions being possible to be triggered by monsters.
It sound like an interesting exercise to make a vanilla-compatible variant of the map.
I've been contemplating lately what types of everyday items could be used to create a simple calculator / full adder, outside of the digital realm. Something like candles would be interesting to experiment with. I haven't thought of how it would technically work yet, but if anyone has ideas please share.
This is an interesting but niche topic. It’s called conservative logic[1] and is typically described via a pool/billiard “circuit.” The idea is that it’s more expensive but entirely reversible. I find myself wondering what simple bit possible computers primitive man could have come up with (had they dedicated themselves as much as e.g. the pyramid builders)
Overflowing water pools with barriers operated by level or flow in some other pool would be the intuitive candidate. Very close to popular mental models of electricity and people do like to have fountains around. Fountain/playground intermediates seem to be particularly popular.
It's been baffling me since late childhood that this isn't a thing everybody loved until they became "oh no, not another one of those!" frequent. Remember when fountains of that giant stone sphere slightly elevated by water pressure type weren't definitely not cool anymore yet?
I also read a sci-fi book (forgot the title) that involved a pre -tech civilization that had invented computation, and executed code with large crowds of people standing in a grid following set rules to act as logic gates.
as I mentioned in another reply to this, there is a popular sci-fi book that includes computation with crowds… surely someone on here will mention the title
Well if you connect two candles together (“A” and “B”), that would make a NAND gate already, with lit being 0.
To connect two of these candle NAND gates together, you’d have to make sure it wouldn’t burn in reverse though. I’ll leave that exercise to the reader…
In the comic, I believe the idea is that this entity is moving the rocks by hand, but following the rules of computing which slowly, but steadily, creates the world as a computer simulation. And in this case, the qualia would be an emergent property of that simulation, but how that happens or whether it happens at all is a much bigger debate...
"I wonder what neat trick they'll use to clear the calculator after getting an answer."
> Pulls out rocket launcher and just starts shooting the monsters.
"Oh."
This reminds me of a dream I had the other nite where I was trying to use a smartphone. I remember getting super frustrated because it was unusably slow.
I love this write-up, especially the interactive diagrams at the end. My vid doesn't go into as much detail on the actual circuit design, but like the article it uses a bunch of BCD ripple-carry adders. For output I use standard 7-segment decoders. As noted in the comments there are faster ways to do logic in Quake which I overlooked in my research, but to my knowledge noone has made a circuit this large before. I've put the source code on github for anyone that wants to take a deeper look: https://github.com/matthewearl/q1logic/