Can Doom Run It? An Adding Machine in Doom | Hacker News Reader

Can Doom Run It? An Adding Machine in Doom

blog.otterstack.com

348 pointssigna1155 comments

Shameless self-promotion, I made a similar thing in Quake: https://youtu.be/xVLtnKyRSb4

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/

Watched and subscribed. I also watched your Quake speedrun vid, really cool stuff!

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

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.

edit:

>The respawning happens after a randomized time delay (roughly 8 seconds to 5 minutes) - https://doom.fandom.com/wiki/Spawning#Monster_respawning

for particularly subjective definitions of 'shortly'

if 5 minutes is the upper limit you just have figure out how to delay the next cycle for 5 minutes, giving you a 3mHz clock.

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

> Now we can finally make the ultimate punchline: "Can Doom run it?"

But surely the ultimate punchline is “Can Doom run Doom?”

Sure here :)

https://hackaday.com/2022/07/12/even-doom-can-now-run-doom/

Does the Babbage Engine run Doom?

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?

You have!

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

Here's some theoretical background on DOOM's Turing-completeness: https://calabi-yau.space/blog/doom.html

In the genre of "an implementation of game X on an accidentally Turing-complete Y", it never hurts to bring up Tetris implemented in the Game of Life: https://codegolf.stackexchange.com/questions/11880/build-a-w...

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.

You can find the post about it here: https://www.doomworld.com/forum/topic/131881-conways-game-of... and the code: https://github.com/pwiecz/conway.wad

> provided scrolling floors

Duke3D's Build Engine?

Boom is "just" pure Doom + some static limits being raised, and a few new types of floors and lines (plus a few other smaller changes) :)

I understand that, but it's more a question of/if using a vanilla engine

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.

Relevant xkcd: https://xkcd.com/505/

How do rocks give rise to qualia ?

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

How do atoms?

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…

How do you imagine them being connected?

It's not clear how two lit inputs results in an unlit output or vice versa with that setup. How do you make that work?

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)

1. https://web.cecs.pdx.edu/~mperkows/temp/June16/ConservativeL...

Do you know of any specific examples I can look into where someone built a computer circuit out of normal objects?

Searching on “mechanical computers” may provide some things. Stuff could also have been done with water.

The main example is using billiard balls to act as a circuit (the benefit here is it’s entirely reversible.). It has not been done at scale

https://handwiki.org/wiki/Billiard-ball_computer

Not exactly "everyday", but you can solve differential equations using pulleys and gears.

https://en.m.wikipedia.org/wiki/Mark_I_Fire_Control_Computer Is pretty cool analog computer

I wonder if one could turn crowds of humans into one, eg. engineering flash sales and other social cues they nudge them through 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

Toy model train sets can be Turing complete: http://www.cr31.co.uk/stagecast/trains/tt8_mech_logic.html

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.

This is described, IIRC, in The Three-Body Problem[1]

[1]: https://en.wikipedia.org/wiki/The_Three-Body_Problem_(novel)

And more generally the concept is known as a China brain

Thank you, I suspected this is where I remembered it from, I had narrowed it down in my memory to either this book, or something from Vernor Vinge.

To give use some ideas:

https://www.youtube.com/watch?v=IxXaizglscw

https://patents.google.com/patent/US3314439A/en

And maybe some inspiration:

https://archive.org/details/ExhalationByTedChiang

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?

We have a brainfuck interpreter in brainfuck. We have Conway’s game of life in Conway’s game of life. When will we get doom in doom?

as linked upthread: https://hackaday.com/2022/07/12/even-doom-can-now-run-doom/

As said in that thread, I don't think that counts in the context of this achievement here. It's not a "DOOM implemented in DOOM" thing.

https://www.pcgamer.com/doom-hacker-gets-doom-running-in-doo...

I think I even saw this on here a few months back.

Ask not what you can run Doom on, instead ask what Doom can run for you

Researchers discover reality is being run in Doom

doom it !

The hell-factory reveal is hilarious to me

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

Had a good chuckle over that one.

It's been known for a while that Doom maps can encode arbitrary logic.

https://doomwiki.org/wiki/Voodoo_script

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.

But can it run Crysis?

Can Doom run Doom?

Now all we need is Doom in Doom!

We're doomed.

hello

Reply on news.ycombinator.com