So, it turns out that Netrunner has now reached a level of complexity that few other games have managed: Netrunner is Turing-complete.
I’ve put a big description of what it means for a card game to be Turing-complete behind the link (in addition to a long construction and a proof), but as a summary: when running a program, computers follow a set of rules to determine what the program does next; when playing a game, humans follow a set of rules to determine what the game does next; a game can emulate a computer program if you can set up a correspondence between a gamestate and a program state in such a way that the rules of the game happen to do the same thing that the rules of the computer would (perhaps indirectly or with extra steps); and a game is Turing-complete if it can emulate any program, in any language that we know how to implement.
(Note that it doesn’t have to be able to run the program at all quickly – this construction is incredibly slow, containing two nested exponential slowdowns. It also doesn’t have to be able to take any input or produce any output, as long as the internal state of the game matches the internal state of the program being emulated. So although there’s a correspondence between Netrunner games and programs, you wouldn’t want to try to actually use Netrunner to run a program, at least with this construction; you wouldn’t finish within a reasonable length of time.)
I’d be interested in feedback/suggestions/corrections; this is one of the most complex Turing-completeness proofs I’ve ever done (not the most complex, but it’s up there), and it’s quite possible that I’ve made a mistake, either in the way in which the game is being programmed, or in something much more mundane such as the Netrunner rules. I’ve also left notes on a number of possible improvements towards the end of the article.
Absolutely delicious. I’ve been musing about this on and off over the years but am not sufficiently knowledgeable to do the work myself. The main problem was always creating the locked loops, and you’ve solved that in a pretty elegant way here.
I guess it would be even more satisfying to not have to rely on the “make this choice or lose” construct, but it’s clearly more flexible than being forced to fully lock down the players so they have no choice at all. There are a few cards could possibly be useful for that: Cayambe Grid, Reduced Service*, Cold Site Server* and Ruhr Valley all impose additional costs to run servers, and Inazuma can be used to prevent the runner from jacking out.
Reduced Service and Cold Site Server require continuous maintenance by the corp though. Could cold site be used for control flow?
Regardless, fantastic work, I find this utterly fascinating.
If you’re trying to lock down servers to be unrunnable, I think the main options are Off the Grid, Hired Help, and Front Company. Cayambe Grid doesn’t work because it’s a cost to approach, rather than a cost to run. Ruhr Valley almost works but there’s no way to take enough clicks from the Runner to fully lock the server down: you can impose additional costs with Ruhr Valley, Enhanced Login Protocol and Victoria Jenkins but the Runner will still have enough clicks if they spend their entire turn doing the run.
Cards like Cold Site Server probably can’t be used at all, though. The problem with click actions is that the players have a choice of whether or not to use them, and it’s very hard to conceive of a gamestate in which the Corp is forced to use the click action on Cold Site Server (given that it is impossible to remove the alternative option of clicking for credits).
Off the Grid is likely to be just fine for the purpose, though (until it gets errata’d to be unswappable onto centrals; lots of remote-only upgrades have been already, but that one has dodged the errata so far). It isn’t unique, so you can place one on every server you don’t want the Runner to run.
Inazuma doesn’t work for preventing jacking out unless you somehow copy its subroutines onto every ICE on the server (which I don’t think is currently possible) – its effect only lasts for one encounter. Whirlpool lasts for the whole run, but it trashes itself. You can set up a situation where the Corp is forced to reinstall Whirlpool in order to avoid losing the game (by using Whirlpool’s self-trash as the only way to get a card into Archives for Hades Fragment), but that doesn’t give any gain over Ancestral Imager, which technically gives the Runner the option to jack out but they instantly lose if they do – in both cases, a player has the choice of following the strategy or losing. The only “you can’t jack out” card that gives no choice at all seems to be Port Anson Grid, but that would involve somehow trying to create a construction without using programs, which would make things substantially more difficult.
The most difficult choices to deal with if you want a perfect, no-choices simulation are a) the Corp’s basic actions – how do you prevent the Corp trashing a resource or purging virus counters? b) the Corp choosing not to rez ICE: at present I’m forcing the rez using Blackguard, but the Runner could in theory choose not to expose it. a) could theoretically be fixed by somehow creating a Turing-complete loop within a single run, and b) could theoretically be fixed by not making use of ice rezzing to check the Corp’s credit total, but I currently don’t know of a way to accomplish either of these.