But can it run Doom?
Stimhack forum user callforjudgement recently made a post presenting their proof that Netrunner is Turing complete. It’s a pretty dense read, but very interesting.
It’s long been speculated that this could be possible. A few years back, there was a bit of commotion online about a paper showing that Magic: The Gathering was Turing complete. It’s also been known for some time that Netrunner contains NP-hard problems.
The proof is using a collection of different techniques to lock down both the runner and corp players so their only options are to take certain desired actions. This results in a stable loop which can be used to model a Turing machine.
One important limitation of the proof is that the players are not completely without agency. This would be almost impossible to achieve in the current card pool. Instead, a number of game ending conditions are set up so as to make any actions but the desired ones end the game in a loss for the player in question, meaning an “optimal player” would never take them. This is a bit “softer” than the full lockdown achieved in the MtG proof, and you have to accept this premise for the construction to work.
Some of the key pieces involve the ice Whitespace, which is used to manipulate the runner’s credit total and effect different outcomes depending on the runner’s credits, as well as Hourglass, which drains their clicks to keep them constrained. Always Be Running ensures the runner must always start their turn by making a run, and all servers but one are protected by ice that will kill the runner to ensure they will run the one server which will maintain the loop.
Another fascinating aspect is the “sword of damocles” remote which is used to create a trap for the corp to make it unfeasible for them to use the purge action, which could otherwise break the loop. If the corp purges, access to this remote is unlocked for the runner, resulting in their victory and a loss for the corp.
I’m not going to go into more detail here, but instead urge everyone who’s interested to read the proof themselves. It’s an impressive feat.
References
Cards mentioned:
Whitespace
Hourglass
Always Be Running
Other:
Netrunner is Turing complete, Stimhack forum post
The proof
Magic: The Gathering is Turing Complete, research paper
Netrunner Mate-in-1 or -2 is Weakly NP-Hard, research paper