By ais523 (aka callforjudgement)
/u/petrapan82 on Reddit: [Magic: the Gathering is Turing-complete. Do] any of you know if the same goes for Netrunner?
ais523: I looked into this a while back. Netrunner has the potential to be Turing-complete, but I think it needs more cards printed than it currently has.
Null Signal Games: *prints more cards*
Much has been made recently about Magic: the Gathering being Turing-complete. However, it turns out that it isn't the only constructed-deck card game that achieves this; Netrunner has also achieved this level of computational power (probably fairly recently).
In this article, I demonstrate that Netrunner is Turing-complete (when generalising the deck construction rules to remove the limits of 3 copies per card and 15 influence per deck), giving a complete construction. You don't need to know how to play Netrunner to read this article; I'll be summarising the relevant game rules as I go along.
Null Signal Games have an explanation, as does Wikipedia, but I'll also have a go at an explanation myself.
Netrunner is a card game played between two players, each equipped with a customised deck that was made by choosing a subset of cards from a very large selection. In this respect, it is similar to trading card games like Magic: the Gathering and Yu-Gi-Oh!, although it is not technically a trading card game due to the way in which the cards are obtained. (Rather than coming from randomised booster packs, Netrunner cards are purchased as sets whose contents are known in advance; thus, for example, if you want a copy of Whitespace, you would be guaranteed to get it upon buying a copy of System Gateway. At least in theory, this puts all players on a level playing field when it comes to deck construction, without being dependent on luck in stumbling into specific rare cards.)
Unlike many constructed-deck card games, Netrunner is unusual in that the two players, one representing a "Corp" (a large corporation in a futuristic cyberpunk world) and one representing a "Runner" (a hacker who is trying to disrupt the Corp's agendas), have very different gameplay; not only do Corp and Runner decks use entirely different cards, the game mechanics are different for the Corp and Runner too (the Runner's win conditions are primarily based around attacking the Corp, whereas the Corp is much more defensive and can win by by keeping the Runner out for long enough to advance their agendas, although some Corps have tricks and traps available to catch out Runners who attack them too recklessly).
When proving things about Netrunner, it is important to be clear about which version of the game I'm talking about. The original Netrunner was released in 1996 by Wizards of the Coast, with rules and cards that are similar to, but not compatible with, the more modern versions of the game. From 2012 to 2018, Fantasy Flight Games produced their own version, Android: Netrunner, which (having been produced for longest, and having the most cards printed) is probably the best-known version of the game. After Fantasy Flight Games stopped producing Netrunner, Null Signal Games (formerly known as NISEI) have continued Netrunner, producing their own sets of Netrunner cards, which are compatible with Fantasy Flight's (but not with the original Netrunner).
Most Netrunner play nowadays uses a combination of Fantasy Flight's and Null Signal Games' card pools and Null Signal Games' rules, and for this proof, I'm going to do the same thing; everything will aim to work under what is at the time of writing the most recent set of rules by Null Signal Games, Comprehensive Rules v22.12, using a mix of Null Signal Games' and Fantasy Flight's cards. I'm also going to be ignoring ban lists and rotation for this, with any card printed by either organisation being legal.
Finally, to make the Turing-completeness proof work, it's necessary to ignore the normal limits on deck construction (which limit decks to 3 copies of each card, and cards totalling no more than 15 of the "influence" points that normally limit which cards players can run in which decks); to be able to implement arbitrarily large programs, we need to be able to represent them with arbitrarily large numbers of cards, and Netrunner's current methods of adding additional cards (or other card-like objects) to the game during play are too restrictive to be of use, so all the cards used by the construction need to start in the players' decks. Fortunately, there's a style of Netrunner play known as "draft" in which none of these limits exist; decks are built with use special "draft identity cards" which allow unlimited expenditure on influence, and which allow more than 3 copies of each card. As such, this proof is going to assume that the players are playing under draft rules (and somehow constructed enormously large decks during the draft). Unfortunately, these rules don't seem to actually be officially published anywhere (Fantasy Flight say "Keep checking this space for more information about Android: Netrunner Draft Play, including the rules."), but there are various unofficial descriptions floating around on the Internet, so I'll be using this description of the draft rules in a Stack Exchange answer to define the relevant rule changes: each player uses a draft identity, no 3-card limit, no influence limit, agendas from any faction can be used, games are won at 6 agenda points. (This modifies rules 1.4.4 (by permitting out-of-faction agendas even though they lack influence costs) and 1.7.2 (by winning at 6 agenda points instead of 7) and deletes rules 1.4.5 and 1.4.7.) Because it's possible, this proof is designed to work regardless of whether the win condition is scoring 6 points or 7, so that particular difference between normal play and draft play won't matter.
Let's think about algorithms. Algorithms are often run on a computer; we might write an algorithm in a programming language, as unambiguous way of describing to the computer what the algorithm is. However, there are other situations in which an algorithm can be followed. For example, we could set up a complicated gamestate in a card game, and then use the rules of the game in order to determine what should happen as a result. In this case, we're following an algorithm in order to resolve the gamestate; the rules tell us (ideally unambiguously) what should happen next, we do it, the rules tell us what happens after that, and so on, and going through the game in this sort of step-by-step way is effectively doing the same thing as a computer is doing when it runs a program.
This means that it's possible to "program" in a card game via constructing a gamestate that mirrors a computer program in the sense that there's a direct correspondence between the states of the program and the state of the game; we start in situations that correspond to each other, then the computer runs a few instructions of the program and the players play the game according to its rules, and now the situations still correspond to each other. So the game and the computer program are doing the same thing, and it makes sense to talk about how much computational power the game has.
Some programming languages have more computational power than others, in the sense that some of them can express programs that can't be expressed in other languages. (For example, most programming languages can write an "infinite loop" in which the computer forever repeats a calculation that will never end, but some languages are intentionally designed to avoid this, with all the programs they're able to express ending after a while. Due to not being able to run indefinitely, these latter languages are less powerful because they can't express all the programs that the more powerful languages could.)
One of the main observations of computer science is that, perhaps surprisingly, pretty much all the programming languages we use in practice, and many that we don't, are as powerful as each other, in terms of what programs can be expressed – any program written in any of the languages can be translated to any of the others, and will do the same thing (although it might do it more slowly, it will eventually come to the same result). Additionally, nobody has yet discovered a way to implement a language that's more powerful. (Although computer scientists can define, and have defined, languages that are more powerful and can express more algorithms, these are all philosophical/theoretical languages that we have no way to realise in practice; they all require things like time travel that we don't currently know how to implement and which may not be physically possible.) The term "Turing-complete" refers to programming languages, and other things that can express/define algorithms, that have this same practical-maximum level of computational power as the languages we generally use to write programs; a Turing-complete language can express any program that any other practically realisable language we know of can, and could in theory run it. (However, actually doing this would be unrealistic in many Turing-complete languages; there's no requirement on how long it would take to run the translated program, and many constructions, including the one in this article, have abysmal performance. The requirement is purely about whether the program runs at all, not about how long it would take.)
As such, what this article aims to show is that, given a program that does something on a practical computer, we could translate that program into a Netrunner gamestate that corresponds to it, in the sense that playing the game starting from that gamestate will produce the same result that running the program would, after following the same sequence of intermediate steps, and we can make the conversion without having to know what the program will do. If the program ends, the game will end; if the program runs forever, the game will go on forever; at any point, we can look at the gamestate and convert it back into a state of the program, to know what the computer would be thinking when it reaches the same point in the program as the Netrunner game has reached in its own calculation.
There's one part of the correspondence which causes problems, though. When running a computer program, we generally don't want the computer making choices/decisions of its own; we want it to do the same thing every time. For most games, though, the whole point is for the players to be making decisions, and this threatens to cause the correspondence to break down. As such, there's a need to somehow limit the freedom of the players to make decisions, so that they end up following the steps of the algorithm rather than doing their own thing, but there's also a need to ensure that this is something that "comes from the game itself", rather than allowing the Turing-completeness to be injected into the game from outside.
The most "perfect" way to do this would be to create a gamestate which implements an entire program without giving the players any opportunity to make any decisions along the way (or where they have decisions but none of the decisions matter). I believe that this is possible for Magic: the Gathering. Unfortunately, it is probably not possible yet for Netrunner, meaning that a slightly more permissive definition of Turing-completeness is needed.
Instead, this proof uses a different approach: a) the players will be constrained to make choices via a very computationally simple algorithm ("always expose, always run HQ, never jack out, never break subroutines, always rez, always return a card to the deck, click for credits rather than purging virus counters"), meaning that the Turing-completeness is obviously not coming from the way the players make decisions, and b) I'll prove that this strategy for the players will produce the same game result (or lack of result) that would be obtained if two "optimal" Netrunner players played starting from the gamestate. (In other words, I'm proving two potential definitions of Turing-completeness simultaneously: "it's Turing-complete if the players make choices in this simple way" and "it's Turing-complete if the players play optimally".) In order to prove b), I will ensure that "making the wrong choice" either comes to the same thing as making the right choice, or else allows the opponent a line that trivially wins the game by making only a small finite number of choices – an optimal player will never make a move that trivially loses the game unless they were doomed to lose anyway, so whenever the optimal player deviates from the expected strategy, it will be in a way that has no overall impact on the game result.
The term "Turing-complete" is a little ambiguous in terms of how it's popularly used, with people using it to mean either "Turing-powerful" or "Turing-equivalent". The distinction rarely matters in practice, and the two possible meanings are often used more or less interchangeably, which is why the definitions aren't 100% nailed down. But there's a chance that it matters here.
The definition of "Turing-equivalence" requires a programming language, or something else that can implement an algorithm, to be equally powerful to all our practically realisable Turing-complete languages. Normally, Turing-completeness proofs are concerned with proving that a language is at least as powerful as Turing-complete languages generally, i.e. "Turing-powerful". However, to be equally powerful, theoretically it also needs to be proven that the language is not more powerful than the Turing-complete languages it's being compared it to. Note that if a card game is more powerful than typical programming languages, this implies that the rules require the players / judges of the game to make determinations about the gamestate that aren't (as far as we know) physically possible to calculate; this would generally be considered a mistake in the rules, but it's hard to mathematically guarantee that this mistake hasn't been made.
Although a pedantic point, in the case of Magic: the Gathering, this almost happened. In Magic, the rules state "If a loop contains only mandatory actions, the game is a draw" (728.4). Many players understand this to mean that the rules are capable of detecting situations in which a gamestate will lead to an infinite chain of mandatory actions and will end such games in a draw, and with that interpretation of the rules, Magic would be "uncomputable" because it is possible to set up chains of mandatory actions for which it's impossible for a Turing-complete programming language to determine whether or not the chain will ever end (thus, because the game could determine it, the game would be more powerful).
However, the rules of Magic define "loop" fairly narrowly, requiring it to be "a state in which a set of actions could be repeated indefinitely" (728.1b). The rules of Magic don't specify any special handling for the situation in which there's an infinite chain of mandatory actions that never repeats, which is probably enough to keep Magic computable (although there's room for interpretation on this, because the language used for this by the rules is not as precise as it would be in a computer program or a mathematical paper).
Netrunner's rules on infinite loops (10.13) specify special handling only when a) a mandatory infinite loop is created or b) an optional infinite loop is created during a run. Neither of these situations occur in this proof (although the construction in this article is capable of translating an infinite loop into a Netrunner gamestate, because it can translate any program and an infinite loop is a valid program, the construction produces an optional infinite loop that occurs outside a run, thus doesn't trigger either of the above points). I currently don't know of a way to construct a Netrunner gamestate for which it's uncomputable to determine whether or not one of the two sorts of specially handled infinite loops have occurred, and think that it's unlikely with the current card pool. However, I also haven't managed to entirely rule it out. So from a pedantic / technical point of view, although this proof proves that Netrunner is Turing-powerful, I can't prove that Netrunner is also Turing-equivalent.
In many constructed-deck card games, there are fairly simple ways to "go infinite", reaching a point where the same set of actions can be repeated indefinitely. However, in Netrunner, there is a limit to the number of actions that a player can perform in a turn, with each action spending a "click" from a fixed supply that refreshes only at the start of a turn. Although there are methods available to gain additional clicks, these tend to have costs high enough to prevent players performing an infinite number of actions wtihin a turn. Additionally, most cards that allow the reuse of previously played cards have limitations that prevent them being played multiple times in a single game, which forms a further obstacle to infinite loops. As such, some Netrunner players have been known to doubt whether loops can be constructed in Netrunner at all. (Although there are a few well-known loops such as Ansel 1.0 + Ganked!, in which Ansel 1.0's third subroutine is used to reinstall Ganked!, which then causes an encounter that causes Ansel 1.0's subroutines to run again, that sort of loop is hard to use in a proof like this because it gives one player too much choice over whether and how to continue or end the loop.)
The problem here is that in order for Netrunner to be Turing-complete, it needs to contain loops that keep the game going indefinitely, ideally without giving the players too much freedom of choice. In this section, I look at a simple loop of this nature – "simple" in terms of what the loop accomplishes (quite a few cards are needed to ensure that both players do what they're supposed to do rather than deviating from the script, so although the behaviour of the loop is simple, the gamestate required to sustain it is a little less simple, and the explanation as to exactly why it works is somewhat lengthy). The Turing-completeness proof will build on this loop, constructing a much more complicated loop of the same general nature that does calculations in addition to keeping the players' actions locked down.
The basic idea is that actions within a turn are generally limited by available clicks, but the players get a new allotment of clicks every turn, and thus an easy way to get an infinite supply of actions is to allow the loop to cross multiple turns. In order to create a true loop here, there are two requirements: a) the players' actions need to be restricted to the extent that they spend their clicks on the same actions every time, and b) the game doesn't progress towards a win condition. Because the Corp and Runner play by different game mechanics, the method of locking down the actions will be different for the two players.
In Netrunner, the structure of the Runner's turn is very simple: they are given four clicks at the start of their turn, and once they have no clicks left and have finished resolving their actions, they can (and must, if no card is giving them alternative options) discard down to their maximum hand size (if necessary) and then end their turn. Most things that the Runner can do in the game cost a click. (Although some cards grant the Runner abilities that they can choose to use "clicklessly", this construction avoids that problem by ensuring that any such ability in the Runner's deck either does nothing, or does something that actively helps the proof, in all the situations where it would be legal to use.) It is possible, and fairly common, for a Runner to lose additional clicks while in the middle of performing an action: the method used by this construction to lock down the Runner's actions is therefore by forcing their first action of the turn, and ensuring that they lose all their clicks before the second action could happen. As such, each Runner turn consists of one action, the same action every turn.
There are six "basic actions" that the Runner always has available and can spend their clicks on (rule 5.2.8), plus any additional types of action that they might gain through cards. Instead of trying to rule out five of the six actions (in order to force the sixth by elimination), this construction instead forces the Runner to take one particular action: the Runner has an installed copy of Always Be Running.
Always Be Running has been errataed a couple of times, but its essential functionality has always been the same, of limiting what the Runner can do with the first click of their turn – it either has to be spent playing a run event (with this construction, there are none in the Runner's deck), or else taking the basic action to run a server (which in this construction is the only option). Running is the primary "combat" mechanic of Netrunner; the Runner picks one of the Corp's servers, and then tries to get through the Corp's defences on that server ("ICE"), "breaching" that server if they get in. For the purposes of this construction, the Runner is never going to successfully breach a server unless the Corp deviates from the strategy; the construction will ensure that the run always gets stopped by the Corp's ICE.
The choice of server does matter, however. In Netrunner, the Corp always has three servers representing their hand, deck and discard pile, and can make more during the game; each server has its own ICE dedicated to it. In order to form a perfect loop, the Runner needs to choose the same server every time. The primary way that this construction ensures this is by giving the servers that the Runner isn't supposed to run ICE that will cause the Runner to immediately lose the game if encountered. (ICE in Netrunner basically works by giving a list of "subroutines", consequences that will occur upon encountering the ICE if the Runner doesn't prevent them happening somehow.) The simple loop in this section will do this job using Karunā, in a situation where the Runner has no cards in hand. In Netrunner, "do X net damage" means "the Runner discards X cards at random; if they can't, the Corp wins the game" (10.4.1, 10.4.4). Karunā has two subroutines that start "Do 2 net damage", either of which will cause the Runner to lose the game if it fires. The Runner is able to prevent one of them firing ("break" it) by using Always Be Running, but the card requires the Runner to lose two clicks in order to break a subroutine; after spending one click to start a run, and two to break a subroutine, the Runner will only have one click left and be unable to break a second subroutine. The Runner is given no other cards that are able to interact with that piece of ICE during a basic-action run. Thus, an encounter with Karunā will immediately win the Corp the game regardless of the Runner's actions. (The presence of Always Be Running is the reason why the construction has to use a piece of ICE with two game-winning subroutines; one wouldn't be good enough.)
In this construction, the Runner will always be running "HQ" – the server that represents the Corp's hand. Any other runnable servers will be protected with Karunā, or some ICE or combination of ICE that presents a similarly insurmountable obstacle (and the Karunā will already be "rezzed", i.e. already active and ready to use). When following the fixed set of choices used for the "follow this simple strategy" version of the proof, the Runner will always run HQ because that's what the strategy says to do. An optimal Runner player would also always run HQ, because running into a Karunā would immediately lose them the game; there's no way to stop both net damage subroutines firing, and with Karunā rezzed and thus visible face-up in the play area, the Runner will know that it's there and thus be able to avoid it.
HQ will also be guarded by ICE. When running HQ, instead of an insurmountable piece of ICE, the Runner will encounter a rezzed Hourglass. Hourglass has three subroutines, each of which causes the Runner to lose a click. Now, because the Runner has Always Be Running, it's possible to break one of those subroutines, but it doesn't matter whether the Runner does or not; after spending one of their four clicks to make a run, there are three left, and the Runner either loses all three to subroutines, or else two to Always Be Running and the remainder to the remaining subroutines. Either way, the Runner will have no clicks left after the ICE encounter.
It's possible for a server to have multiple ICE installed on it; in this case, the ICE will (unless something changes the order) be encountered in the order it was installed, from newest to oldest. In order to create a simple loop, the second piece of ICE can be something like a rezzed Spiderweb that causes the run to end without any further consequences; if the Runner tries to continue the run after going through the Hourglass, they will end up hitting the Spiderweb and having the run forcibly ended. (The more complicated constructions below will work by replacing the Spiderweb with some much more complex sequences of ICE, in order to start doing computation.) After the run ends, the Runner has no clicks left because of the Hourglass, and has no cards that would let them do anything clicklessly, so must end their turn. The Runner's gamestate hasn't changed at all in this process; for example, they neither drew nor used any cards, and neither lost nor gained credits. As such, this construction effectively completely locks down the Runner's actions; their only choices are to run HQ and waste their turn running into the Hourglass + Spiderweb combo, or to run somewhere else and end up immediately losing the game (and neither "follow this simple strategy" nor "play optimally" will ever take the latter option).
The Runner does, however, have one choice to make (beyond the choice of server to run). When making a run, the Runner has to encounter the first piece of ICE on the server. However, after passing a piece of ICE, the Runner doesn't have to continue; they have an option to "jack out", ending the run there and then without having to risk the consequences of any further ICE subroutines. For the simple loop in this section, this doesn't matter at all; jacking out voluntarily has exactly the same consequences as running into Spiderweb and having the run forcibly ended would. As such, the "jack out" rule is mentioned primarily because it will be relevant to later sections, rather than because it is relevant here.
So I've demonstrated how it's possible to, in effect, neutralise all the Runner turns entirely, with the Runner effectively having no impact on the gamestate. What about the Corp?
Netrunner's mechanics are different for the Corp and for the Runner, and one of the more obvious places that shows up is in the turn structure. A Runner turn is as simple as "spend four clicks, then discard down to hand size", but a Corp turn is very slightly more complex:
One difference between the Runner and the Corp is in the number of clicks they get per turn, with the Runner getting four and the Corp getting only three. In the absence of a card ability allowing a turn to end early, both players have to spend or otherwise lose their entire allotment of clicks before they can end their turn (rule 5.4.2). This fact wasn't relevant in the construction for the Runner, but will be relevant in the construction for the Corp; the idea behind locking down the Corp's actions is to eliminate all other possibilities for what the Corp could spend their clicks on, forcing them to be spent only on the things required by the construction.
The other big difference is the mandatory draw. One of the main consequences of this game mechanic (and probably part of the reason it was included within the rules) is that it tends to prevent the game being prolonged indefinitely, because it makes the Corp's deck serve as a timer counting down towards the end of the game; it depletes a card from the deck every turn, and it ends the game if the deck is empty at the start of a turn (by causing the Runner to win). Both Fantasy Flight and Null Signal Games have generally been trying to keep this timer intact in their card designs, with Fantasy Flight generally designing cards that return other cards to the deck to be usable only once in a game, and Null Signal Games having a tendency to make such cards draw additional cards as a side effect (to give a net reduction in the size of the deck even though some cards were shuffled back). If all Netrunner cards had been designed like that, a cross-turn infinite loop would be impossible because there would be no way to prevent the mandatory draw ending the game. Fortunately, though, a few cards slipped through the cracks, allowing the Corp to indefinitely recycle cards back into their deck and thus allowing them to survive arbitrarily many mandatory draws.
There are a few possibilities of cards that could be used, but for the constructions in this document, I'll use Hades Fragment. This is an "agenda" card. If "scored", an agenda is worth a given number of points towards winning the game (3 in this case). Agendas also usually have side effects when scored, either immediately upon scoring them, or lasting for the rest of the game. Hades Fragment has a particularly useful "while scored" effect – it allows the Corp to return one card from their discard pile ("Archives") to the bottom of the deck ("R&D") every turn (before the mandatory draw). The idea behind the construction is that during the Corp's turn, they have six cards in hand but none of them can legally be played; so they all remain in hand during the Corp's turn, and one of them gets discarded to hand size at the end of the turn. The Corp can then survive the start of the next turn by moving the card back to their deck using Hades Fragment and immediately drawing it using the mandatory draw.
The identity of the unplayable cards doesn't matter much. As a concrete example, I will be using six copies of Game Over, which can only be played if the Runner stole an agenda on the previous turn; in this construction, the Runner won't be stealing agendas, so Game Over will remain permanently unplayable. Using six copies of the same card means that the Corp has only one choice about which to discard (it would be equally possible to use a range of different unplayable cards; then, the Corp would have a choice, but the choice would make no difference.)
Here's a list of the "basic actions" that a Corp can perform on their turn (i.e. the actions that they have available when they have no cards giving them additional possibilities) (rule 5.2.7):
Most of these actions can easily be made impossible. The Corp is never going to be able to draw a card, because their deck is always empty except for immediately before the mandatory draw (and you can't spend a click on a basic action unless you're able to resolve that action). They don't have any agendas, assets, upgrades or ICE in hand because none of their cards in hand have any of those types (Game Over is an operation) – and none of their operations can legally be played. The construction will avoid giving the Corp any installed cards that can be advanced (some such cards, like Hades Fragment, were previously in the Corp's deck – but all such cards will have been made permanently inaccessible before the loop starts, by scoring them, stealing them or removing them from the game). For the simple loop, the Runner will not be tagged (this is something that will change in the more complex loops below!). This means that the Corp is already limited to only two of these actions: clicking for a credit, or purging virus counters. Because purging costs three clicks, the Corp therefore has only two possible sequences that would spend all their clicks on their turn, and according to the rules of Netrunner, must choose one of them:
The option that allows the construction to work is for the Corp to click for three credits. If the Corp takes this option, then each of their turns will gain 3 credits with no other net change, and each of the Runner's turns will do nothing, creating a gamestate in which nothing ever changes apart from the Corp's credits ticking up by 3 every turn forever. 3 turns out to be an inconvenient number to use for the rest of the proof, so the Corp is also given 24 remote servers, each of which contains a copy of PAD Campaign in its root (protected, as usual, by Karunā in order to prevent the Runner running it); this gives the Corp 24 credits at the start of each turn (because each PAD Campaign gives one), so they gain a total of 27 credits each turn rather than 3. (A "remote server" is a server that the Runner can attack but that exists on its own, rather than representing the hand, deck or discard pile.)
Preventing the Corp from purging virus counters, instead of clicking for credits, requires making the gamestate somewhat more complex. To achieve this, the Corp is given a 25th remote server. In the root of the server is The Board, which is being used as a method to let the Runner win the game if they ever get into the server: if the Runner breaches the server and trashes it, they gain 2 agenda points (plus 1 for every agenda in their score area). As such, it's possible to ensure that "trashing The Board wins the Runner the game" by giving them agendas with a total value of 5 points in their score area, and no relevant text (there are plenty to choose from; most agendas do nothing in the Runner's score area other than being worth points).
Guarding the server will be a somewhat more complicated ICE than the Karunā used earlier; instead, the construction uses Nerine 2.0 with a lot of cards and counters hosted on it:
Just as with Karunā, if the Corp follows the strategy, the Runner can't survive an encounter with this ICE. The Nerine 2.0 has three subroutines (two of them naturally, and one of them from Wetwork Refit); as of the most recent errata for these cards, all three subroutines start by doing 1 core damage. Just as with net damage, a point of core damage will cause the Runner to discard a card at random, or lose the game if they can't (there are also other effects but those don't matter here). So to survive a run on the server, the Runner would have to break all three subroutines. The Runner will have three clicks left at this point (having used one to start the run), and Chisel doesn't help (it reduces the ICE strength to 4 by cancelling out Patch, and subsequently to 3, but this isn't enough to destroy the ICE). So the Runner's only options are to break subroutines with Always Be Running (which breaks one subroutine but loses two clicks) or with Nerine 2.0 itself (which breaks two subroutines but loses two clicks). With only three clicks left, the Runner can't afford to use both of these abilities, nor to use the same ability twice, so the best they can do is to break two subroutines and lose the game when the third fires.
In order to prevent the Corp purging virus counters, the Runner is given an installed copy of D4v1d (which breaks subroutines on ICE that has power 5 or greater) that has 3 hosted power counters, along with a copy of Skulljack. If the Corp doesn't purge, then D4v1d can't be used as it has no legal target (the Nerine 2.0 has a strength of either 4 or 3, likewise Karunā has a strength of 3, but D4v1d can only target ICE with a strength of at least 5). However, if the Corp does purge virus counters, then this will remove two virus counters from Chisel, increasing Nerine 2.0's strength to 6; when the Runner encounters it, Chisel will reduce the strength to 5, but this is still high enough for D4v1d to work. So the Runner will be able to use D4v1d to break all three subroutines and continue past the ICE, breaching the server. When the Runner breaches a server that contains an asset, they are given the opportunity to trash that asset, by paying its trash cost; The Board has a trash cost of 6 (its printed trash cost is 7, but Skulljack reduces this by 1), and the three copies of Kyuban give the Runner 6 credits as they pass Nerine 2.0. This means that the Runner will always be able to afford to trash The Board, and the points from doing so win them the game.
The upshot of all this is that an optimal Corp player will, in this gamestate, never use the basic action to purge virus counters (unless the game is already lost at that point). Doing so would give their optimal-Runner opponent the opportunity to immediately win the game on their own turn (and the opponent in question would take it), because there's no hidden information involved – with all the cards on the server rezzed, the Runner will know that the Corp has no way to prevent them getting into the server and trashing The Board for the last two points.
(A side note: The Board's effect of reducing agenda point values is actually irrelevant to the construction. There are very few cards that are worth agenda points when accessed, but cannot be advanced with the basic action: this one was selected because its effect while installed has no negative impact on the construction.)
The simple loop construction in this section causes both players to repeat a simple sequence of actions that prolongs the game indefinitely, with no net change apart from the Corp gaining four credits every turn.
During the Runner's turn, they are forced to start their turn by taking the basic action to make a run, due to their own Always Be Running. Most choices of run would lose the Runner the game, so they run HQ, which is guarded by Hourglass and Spiderweb; no matter what their choices, the run drains all their clicks and accomplishes nothing else, and their turn ends in the same state in which it started.
The Corp's actions aren't forced, but deviating from the intended path immediately loses the game. In order to survive their mandatory draw, the Corp must return a Game Over to their deck using the effect of a Hades Fragment in their score area. They then spend their whole turn clicking for credits, and discard the Game Over to hand size, ready to return it to their deck and draw it again next turn. Failing to recycle the card would cause the Corp to lose to their mandatory draw; and the only option the Corp has other than clicking for credits is to purge virus counters. Purging would immediately allow the Runner to survive a run on a remote server, trashing The Board and winning the game as a consequence. As such, the Corp will avoid taking unintended actions (except when they provably make no difference to the game result) because they immediately lose the game, and thus are either inferior to, or else lead to the same game result as, the intended actions. The net effect of the Corp's turn is that they gain four credits (three from the basic action and one from PAD Campaign).
The main restriction needed to make this work is that the Runner's and Corp's hands and decks (and the Corp's discard pile) are empty apart from the six Game Overs; additionally, the fact that the Runner has D4v1d will place restrictions on what ICE can be used in the rest of the construction, because the Runner will be able to break subroutines on sufficiently strong ICE.
One of the main obstacles to implementing Turing-complete algorithms in systems like Netrunner that weren't designed for computation is trying to find a way to store arbitrary amounts of data. Netrunner doesn't have many things in the game which can be made to take on arbitrarily many possible values without choices being made by the players. It does have a few – things like the players' credit pools can go arbitrarily large – but that's only two values (and to make the construction work, later parts end up having to put a limit on how high the Corp's credit total could go, so only the Runner's credit pool turns out to be usable for this purpose).
Turing-completeness requires a certain minimal level of being able to remember data. Fortunately, one possibility that works is "you have one number that can grow unboundedly large, and a method of multiplying it and dividing it by constants" – that's the technique used by this construction, and the number will be the Runner's credit total. However, Netrunner doesn't have easy methods available to do arithmetic on credit totals; it would be nice if there were an ICE whose only subroutine said "triple the Runner's credit total", but there are no printed cards like that (and unlikely to be any such cards in the future). Instead, the only methods available to make decisions conditional on the Runner's credit pool work by checking whether their credit total is above or below a specific number. This means that at some critical point within our multiplication or division algorithm, the Runner's credit pool needs to contain a known amount of credits – and that means that at that particular point in time, our program can't be using the Runner's credit pool to store data. With the fully Turing-complete version of the construction given later, the Corp's credit pool won't be usable for that either. So some other place is required to store arbitrarily large amount of data during the times when the Runner's credit pool is actively being used to do arithmetic.
Given the shortness of options for unboundedly large numbers that it might be possible to keep continuous control over, the best option seems to be the Runner's tag count. In Netrunner, the Runner can gain a "tag" as a consequence of the effects of various cards. In this construction, the tag will then persist until it's removed by another card effect. (There's a basic action to remove a tag by paying 1 click and 2 credits, but the Runner will never be able to take that action in this construction, because they're forced to spend their first click each turn running into Hourglass and losing the rest.) Tags are entirely interchangeable with each other, so the only thing that matters with respect to tags is how many tags the Runner has, and that number can grow arbitrarily large (rule 1.9.2: "The bank is an unlimited supply; running out of game pieces to track a type of counter does not prohibit a player from gaining counters of that type or placing them on cards.", and a tag is a sort of counter).
There are plenty of ICE that have subroutines which give the Runner tags, so there is no real difficulty in controllably adding tags to the Runner. However, removing tags in a way that gives neither player a choice is much harder. This construction solves the problem by using the Runner's identity; the runner will play as Boris "Syfr" Kovac: Crafty Veteran. This is a draft ID (as required by the draft rules), and because it's an identity card, it's active right from the start of the game (each deck can only contain one identity, but it's removed from the deck before play and becomes active immediately). Boris's effect only does anything if the player has more Criminal cards installed than cards from any other faction; to ensure that this is always the case, the gamestate gives the Runner a sufficiently large number of installed copies of HQ Interface in order to make up the numbers. (The construction doesn't involve the installation or uninstallation of any more than a small finite number of cards, so it's possible to determine statically how many HQ Interfaces are needed; there's no limit on how much hardware the Runner can have installed, and the effect of HQ Interface is irrelevant because the construction prevents the Runner ever breaching HQ. Because HQ Interface is a Criminal card, it will count towards the requirement for meeting Boris's condition.)
When Boris's condition is met, it removes one tag at the start of the Runner's turn, unconditionally and without any choices being made. The construction makes use of this to, effectively, insert an arbitrarily long "delay" into the main logic of the program; the ICE on HQ will be set up such that, if the Runner has x + 1 tags, the Runner and Corp both end up accomplishing nothing for x turns, with the only significant thing happening during that time (in this section – the full construction will be slightly more complicated) being a steady increase in both players' credit counts. As such, tags can be seen as a "delayed" source of credits for both sides; each tag given to the Runner beyond the first will turn into 3 Runner credits and 27 Corp credits before any further gamestate progress is made. (The mechanism therefore ends up equivalent to each tag beyond the first turning into 3 Runner credits and 27 Corp credits "at the end of the turn" – although the gain is actually spread out across multiple turns, nothing else is happening during those turns.)
Building this sort of tag battery is almost very simple. In order to get the desired behaviour when both players are following their set strategy, all that's required is to change the simple loop in the previous section so that it gives the Runner credits every turn in addition to the Corp, and so that it continues as a simple loop for as long as the Runner is tagged, but acts differently if the Runner is untagged.
Most of these goals can be achieved by changing a few cards:
The idea is that due to the Pachinko, the construction is equivalent to the simple loop in the previous section for as long as the Runner is tagged; the only difference is that the Runner now has a steady drip of credits too, due to the three copies of Rezeki. When the tags run out, though, the Pachinko won't end the run and the Runner will sail right on by. The entire rest of the construction is then placed "behind" the Pachinko – it only executes once the tags have run out.
The problem here is not in what happens if the Runner and Corp follow their simple strategy, but rather what happens in the "optimal play" model; as it stands, the players' actions are not fully locked down. Compared to the simple loop, there are two new choices that the players could attempt to take, and for the proof to be valid, it needs to be proven that a player who takes the wrong choice will necessarily end up losing the game (thus the choice will not be made by an optimal player unless the choice is provably wrong anyway).
The smaller change needed here is with respect to locking down the Runner's choices. Whenever the Runner passes a piece of ICE, they have the option to jack out (i.e. abort the run) rather than continuing the run, something that could break the construction if the Runner decides to jack out to avoid encountering a Pachinko that they could otherwise run through (doing this would cause the tag-battery to run for too long and give the Runner and Corp too many credits). Because the Runner's hand is empty in the construction, fixing this is fairly simple: all that is required is to give the Corp a scored Ancestral Imager, an agenda with a continuous after-scored effect that does 1 net damage whenever the Runner jacks out (i.e. "discard a card at random, if you can't you lose the game" aimed at a Runner who has no cards to discard). An optimal Runner who has no way to prevent net damage will never jack out when facing an Ancestral Imager with an empty hand (unless the game is provably doomed anyway), as it would cause the game to be lost immediately.
There is a limit to how many scored agendas can be used to provide effects on the game – if the Corp scores agendas with sufficient value, they win the game and thus the game would have ended already – but Ancestral Imager is worth only 1 point, and even added to the 3 from Hades Fragment, this comes to only 4 points, not enough to win the game.
What about the Corp side? The issue is that the simple loop construction locks down the Corp's actions by considering in which legal ways they could string together basic actions to take an entire turn, but when the Runner has tags, an additional basic action becomes available: as long as the Runner is tagged, the Corp can pay 1 click and 2 credits to trash a resource. As this construction relies on tags, it's impossible to deny the Corp this action by preventing the tag requirement being met; and because the construction uses Always Be Running (a resource) to lock down the Runner's actions, the action also can't be prohibited by denying it targets; nor is it possible to prevent the Corp gaining the required credits. (Wireless Net Pavilion is promising, but can't be used to solve the issue because it was errataed to be "unique", meaning that only one can be installed at a time, and preventing the Corp being able to afford that would mean that their credit count would always have to be zero between turns.)
Instead, the gamestate needs to be designed so that if the Corp ever trashes a resource, the Runner will immediately be able to win as a consequence. The key to this is to ensure that Always Be Running is the Runner's only resource; if the Corp wants to trash a resource, they will have to trash that one. Doing this will then "unlock" the Runner's turn, allowing them to take actions other than running into the HQ ICE every turn and losing all their clicks.
The rather complicated Nerine 2.0 in the previous section was designed with this in mind. In the previous section, the Runner could get through Nerine 2.0 if the Corp purged virus counters, but not if the Corp had followed the strategy (they would lose the game during the encounter if they tried). In this section, the only change is to give the Runner an installed copy of Tracker, plus enough installed copies of T400 Memory Diamond to allow them to have that many programs installed at once (normally the Runner is limited to 4 "memory units" worth of programs installed at a time, and Tracker plus D4v1d plus three copies of Rezeki would be too much, but some cards such as T400 Memory Diamond raise that limit). If the Corp follows the strategy, or purges, everything is the same in the previous section: Tracker can't be used because Always Be Running restricts the Runner to take the basic action to run, or play a run event, with their first click each turn (and Tracker does not fall into either category); Tracker can't be used during a run (rule 5.2.2.a), and the Runner will have no clicks left by the time the run ends (and thus be unable to pay the cost to use the Tracker).
However, if the Corp does choose to trash a resource, their only choice will be Always Be Running. The Runner will then no longer have their actions locked down, and in particular will be able to choose the remote server guarding The Board with Tracker, and then use Tracker's ability to start a run there (the credits they gained from the three copies of Rezeki, plus the clicks they gained for the turn, are enough to pay for it). The Runner will have three clicks left after starting the run; this lets them lose two clicks to use Nerine 2.0's ability to break its natural two subroutines, and Tracker will prevent the extra subroutine from Wetwork Refit resolving, so the Runner breaches the server without taking any core damage. As in the previous section, breaching the server allows the Runner to trash The Board and win the game.
This section contains a "tag battery" construction, which converts each tag on the Runner into 3 Runner credits plus 27 Corp credits with no other net change to the gamestate. This is useful because the Turing-completeness construction in this document sometimes needs both the Corp's and Runner's credit totals to be near 0 simultaneously, but nonetheless needs to be able to store an arbitrary amount of data while that's happening; the data is thus stored in the tag count ("charging" the tag battery), and will be again stored in the Runner's credit pool when the battery discharges.
During the Runner's turn, they are forced to start their turn by taking the basic action to make a run, due to their own Always Be Running. Most choices of run would still lose the Runner the game, so they run HQ, which is guarded by Hourglass and Pachinko; As long as the Runner still has tags, the Pachinko ends the run, meaning that no change happens other than the Runner gaining three credits via their three copies of Rezeki. The tags gradually run out, over the course of many turns, due to the effect of Boris "Syfr" Kovac: Crafty Veteran; once they have run out, the Pachinko no longer ends the run, meaning that the rest of the construction can be placed "after"/"behind" the Pachinko in order to cause it to run in those and only those situations where the tag battery isn't busy converting tags back into credits.
The Corp's actions aren't forced. They have somewhat more legal options than in the previous section, but all the new options involve trashing Always Be Running, and the gamestate is set up in such a way that doing so would allow the Runner to immediately win the game on their turn (via allowing them to breach a remote server, trashing The Board installed in its root, because they now have fewer restrictions on what actions they can take, and in particular can now use Tracker as a cheap method of dodging a subroutine).
The only restrictions needed to make this work, above those required for the simple loop to work, are that the Runner's identity is now fixed and that the Runner can use no resources other than the one Always Be Running (unless trashing them would somehow lose the Corp the game). (As an aside, the Corp's identity ends up not mattering at all during the construction, so long as it doesn't do anything that causes the construction to break; as such, it makes the most sense to use the blank draft identity, The Shadow: Pulling the Strings.)
The previous sections have been looking at a particular sort of loop: an infinite loop that crosses both players' turns. However, it isn't the only sort of loop that exists within this Turing-completeness proof. In this section, I'm going to look at a different sort of loop: a loop that happens within the course of a single turn (in fact, within the course of a single run), but which is finite and eventually terminates. In a later section, I'll discuss how the loop gets started, but for the time being, the only relevant factors are that a) the Runner cannot start a run on Archives but b) the Runner somehow ended up running on Archives anyway, with no clicks remaining, and exactly 1 tag. (Archives is the central server that represents the Corp's discard pile, but for the purposes of this section, all that actually matters is that it's a server – the runner isn't getting in anyway. I had to pick this particular server in order to make later parts of the construction work, but this part of the construction would work equally well with any server.)
So far, the constructions have been working with permanently rezzed ICE (i.e. ICE which was rezzed in the starting state of the construction, and for which there are no effects that might derez it, meaning that it remains rezzed the whole time). This one is a bit more complicated when it comes to rezzing and derezzing, though, so it's worth going over the rules for how rezzing works, for the benefit of readers who might not know the game. Most Corp cards (including ICE and assets, but not operations) can exist in two states: "rezzed" and "unrezzed". While unrezzed, the card still exists in the game and can be interacted with, but typically has no abilities (unless the abilities specifically indicate that they work while the card is unrezzed). In the case of ICE, that means that unrezzed ICE will not be able to fire its subroutines (although it still has a fixed location in the "sequence of ICE" on the server, and won't move if its rezzing status changes). When the Runner reaches a piece of ICE ("approaches" it), the Corp is given an opportunity to rez the ICE, but doing so requires paying a number of credits known as the ICE's "rez cost" (which is printed in a corner of the card representing the ICE, next to its name). If the Corp rezzes the ICE, its subroutines will then be active, and will affect the Runner unless broken; but if the ICE is left unrezzed, the Runner will go straight past without any of the subroutines doing anything. Once rezzed, the ICE stays rezzed until something happens to derez it.
Unlike the previous sections, where the servers were quite simple, Archives has a much more complex sequence of ICE. As such, the list of "what ICE goes on Archives" gets a subsection of its own; I'm going to present the list on its own first and then explain it later on.
Archives is protected by the following ICE, listed in the order in which the Runner encounters it:
Unrezzed ICE is placed on the table face-down, so a Runner doesn't necessarily know what it is. However, the construction assumes that the Runner knows what all the ICE is already, e.g. because it was originally installed using Jinja City Grid (which reveals ICE as it installs it).
The effect of Wave depends on the exact number of rezzed harmonic ICE. This construction assumes that there are exactly 7 harmonic ICE rezzed (the others are in an irrelevant location where they'll never be encountered, such as behind a Karunā that's protecting a PAD Campaign).
The Runner mostly has the same cards available as in the previous sections, but for this construction to work, they're given two more: GPI Net Tap and Blackguard. These two cards form an interesting combo: whenever the Runner approaches a piece of ICE, the Runner can expose the ICE using GPI Net Tap; and if they do, then due to the effect of Blackguard, the Corp is then forced to rez the ICE if they can afford to. This combo is particularly important to the construction because it serves as a method of doing two different things based on the number of credits that the Corp has, without giving the Corp any choices: if the Corp is rich enough to rez the ICE, then the Runner can expose the ICE and force them to rez it; if the Corp is not rich enough to rez the ICE, then it cannot be rezzed (the Corp cannot voluntarily rez ICE without enough credits, nor can it be rezzed by the effect of Blackguard).
There are a couple of choices available to the Runner here, though. They could use GPI Net Tap to jack out, ending the run; however, this would immediately lose the game for the same reasons as in the previous section (this is all one big construction, so the Corp still has an Ancestral Imager in their score area), so an optimal Runner won't do this and the "follow this simple strategy" Runner has been told not to. The Runner also gets to choose whether to use GPI Net Tap; it would be possible for the Runner to not expose the card, and not force the rez. However, after the 5 unrezzed copies of Whitespace there is a Diviner, which has the same rez cost that Whitespace does, and after the unrezzed Bandwidth there is a Data Mine which has the same rez cost that Bandwidth does. A hypothetical optimal Runner will never choose not to expose as many copies of Whitespace or Bandwidth as possible (unless the game is doomed anyway), because doing so gives their opponent the opportunity to save their credits to rez a more lethal piece of ICE instead – if the Corp gets to rez Diviner or Data Mine, that will instantly win them the game, because both those ICE have subroutines that do net damage and thus will win against an empty-handed Runner. It's strictly better to force the opponent to do something than it is to give them a choice between doing that thing and winning the game. (And, of course, the "follow this simple strategy" runner is exposing all the ICE anyway.)
Along similar lines, the Runner will force the Corp to rez the Cell Portal by exposing it; if the Corp leaves Cell Portal unrezzed, the Runner will go past it and immediately lose the game upon encountering the Data Mine beyond it. The Corp will always be able to afford to rez Cell Portal, because the subroutine on the Wave immediately before it will give the Corp 7 credits when the Runner encounters it, enough to pay the rez cost; and if the Runner forces them to do so, they save themself from the Data Mine because Cell Portal's subroutine "resets" the run, sending the Runner back to the start of the server. (It also gives the Runner an opportunity to jack out, but due to the Ancestral Imager, the Runner can't take that opportunity to jack out either without immediately losing the game; likewise, the Runner could break the Cell Portal's subroutine with D4v1d, but that would simply cause them to continue onwards to the Data Mine and lose.)
On the first pass through the server, all the ICE that isn't permanently rezzed will be unrezzed: the net damage ICE can't ever have been rezzed because otherwise the Runner would have lost the game already; whenever Cell Portal is rezzed, its subroutine immediately fires and derezzes the ICE again (because ICE can only be rezzed while the Runner is approaching the ICE); and all the remaining ICE has a hosted Tranquilizer. Tranquilizer, as long as it has two or more virus counters on it, derezzes the ICE it's hosted on at the start of the Runner's turn; as such it will be unrezzed before the first pass through the server on any given turn (because after the start-of-turn derez, it couldn't possibly be rezzed until the Runner approaches it, thus will still be unrezzed at the first point at which the Runner approaches it each turn).
The Corp will then end up forced to rez as much of the ICE on the server as they can afford (because the Runner will be exposing all the ICE along the way, with Blackguard forcing the Corp to rez it if they can). On subsequent passes through the server, the Corp will have no credits left and not be able to rez any further ICE, so the rezzed/unrezzed status of all the ICE will be set during the first pass through the server and remain the same through the entire turn.
What exactly happens will therefore depend on the Corp's credit count (as of the start of the run). There are four specific counts that are used in this construction: 0, 2, 20, and 22. For each of these counts, here's what happens on the server up to but not including the Wave:
In each of these cases, the Corp is left with exactly 0 credits going into the Wave. This provides 7 credits, which the Runner forces the Corp to spend rezzing Cell Portal, restarting the run. The Corp now has 0 credits again, and will be unable to rez any ICE on the next loop through the server; and every run after that works the same way, with the Corp being briefly given enough credits to rez Cell Portal and having no credits the rest of the time. As a consequence, the set of rezzed ICE on every loop through server will be the same, and will depend on the number of credits the Corp started with. There are therefore, in effect, four different "configurations" of rezzed and unrezzed ICE for the Archives server, and it's possible to choose between them using the Corp's credit count.
Most of the ICE on the server, and most of the cards hosted on it, together with the Runner's expose combo, exist purely to determine which ICE is rezzed and unrezzed, and to force the Runner to run through the server in a loop until a subroutine ends the run; the previous subsection explains the effect of everything but the Bandwidth and Whitespace.
With the server set up, the Bandwidth and Whitespace are what perform the actual arithmetic:
Let's consider an encoding of numbers in which 0 is encoded as 9, 1 is encoded as 12, 2 is encoded as 15, and in general x is encoded as 3x + 6. The run on Archives will thus encounter x copies of Whitespace in total (with the last encounter ending the run), and the Runner will end up with exactly 6 credits. That'll give the Runner some number of additional tags, say y (and they started with exactly 1). If a tag battery is in use, then each of those additional tags is converted to 3 credits by the tag battery; thus assuming y > 0, the Runner will end up with exactly 3y + 6 credits by the time the tag battery allows them to do anything other than ineffectually bouncing off HQ. In other words, what this server is basically doing is taking a representation of the number x (which will determine the number of encounters with Whitespace), and converting it to a representation of the number y (which is determined by the number of encounters with Bandwidth).
In the configuration of the server in which the Corp started with 0 credits, this effectively takes a nonzero number x and multiplies it by 2: the Runner encountres two copies of Bandwidth then one of Whitespace, and repeats until Whitespace ends the run, so y will equal 2x. Similarly, if the Corp started with 2 credits, there is one more Bandwidth and thus this configuration of the server calculates y = 3x (for nonzero x).
The other two configurations of the server are intended for use only with nonzero x values that are divisible by 6. Assuming that x is divisible by 6, then there will be exactly x ÷ 6 complete loops through the server, and no incomplete loops (because the last ICE in the loop is the sixth Whitespace, which ends the run after the Bandwidths have fired). Each of these loops contains 2 or 3 copies of Bandwidth (depending on whether the 20-credit or 22-credit configuration is in use), so the server ends up calculating y = 2x ÷ 6 = x ÷ 3 or y = 3x ÷ 6 = x ÷ 2 respectively.
In other words, the server will end up calculating one of four mathematical operations, for which y ends up equal to x either divided or multiplied by either 2 or 3 (the divisions require x to be divisible by 6, and in all cases it must be nonzero). The input is taken from the Runner's credit count (encoded as 3x + 6), and (via a tag battery) the output eventually ends up back in the Runner's credit count, with the same encoding.
The arithmetic setup on Archives presents a problem when the Archives-arithmetic loop is combined with the cross-turn loop in the previous sections: that loop relied on the Runner being unable to survive a run on any server but HQ, but (depending on the Corp's and Runner's credit counts) the Archives ICE setup is not necessarily going to be immediately lethal for the Runner to run on their own turn. As such, some other method is needed to prevent the Runner choosing to run Archives rather than HQ.
This construction uses an approach that is simple in terms of the required gamestate: the root of Archives holds Off the Grid. This is an upgrade, a card that can be placed in the root of a server, and typically modifies something about the way the players interact with the server. Off the Grid makes it impossible for the Runner to initiate a run on Archives, and thus provides a different method to ensure that the Runner runs on the correct server. (Although it trashes itself if the Runner makes a successful run on HQ, in this construction the Runner will never make a successful run on HQ.)
One issue with this is in how the gamestate is set up in the first place: Off the Grid can only be installed in the root of a remote server. However, it is possible to get it into the root of Archives with Metamorph, which has a subroutine that swaps two non-ICE cards; this makes it possible to swap an installed upgrade in the root of a remote server with one in Archives, getting around the install protection.
Under Fantasy Flight's rules, it is generally accepted that swapping card locations is a valid way to get cards into locations where they couldn't be installed. (For example, there is an "unverified" ruling on the NetrunnerDB page for Metamorph that talks about this interaction, taken from ANCUR which is generally considered a fairly reliable source.)
Null Signal Games have also created cards with restrictions on where they can be placed, such as La Costa Grid, and those cards have a restriction "Remote server only." Under Null Signal Games' rules, that restriction prevents the upgrade even being swapped onto a central server (rule 8.5.12). This restriction, however, is limited to abilities that are worded with the name of a server followed by the word "only"; and the card's original wording "Install only…" is clear that it affects installation, rather than what might happen to a card later on.
Null Signal Games appear to be in the process of errata-ing some of Fantasy Flight's upgrades from the older wording (which allowed them to be swapped onto servers where they cannot be installed) to the newer wording (which does not allow such a swap). For example, Self-destruct and Calibration Testing have received such errata. However, according to what is at the time of writing the most recent Card Text Updates list (v22.12), Off the Grid has not received such an errata, and still has its original text, which prohibits installing but not swapping.
As such, it is possible that this proof will break in the future. The most promising approach for fixing this is to use Front Company – its second effect does exactly what would be needed, and its first effect prevents the Runner from just running the Front Company itself – but unfortunately its first effect would also break the mechanism that prevents the Corp trashing a resource or purging virus counters. Most likely that issue can be worked around, but it would be more complex. (One promising approach to work around the issue is to use Political Graffiti; if it could somehow ends up on an agenda in the Runner's score area, a virus counter purge could immediately win the Runner the game. However, it isn't clear, from the current rules, whether or not the condition counter would stay hosted as the agenda moved into that zone; maybe a future update to the rules will clarify.)
This section gives a construction for an arrangement of ICE on Archives which is able to do arithmetic. Depending on the Corp's credit count when the section is entered (0, 2, 20, or 22), it calculates one of four arithmetic operations: multiplication by 2, multiplication by 3, division by 3, and division by 2 respectively (with the input and output encoded in the Runner's credit total as 3x + 6 – the output is temporarily stored in the Runner's tag count, and changed back into a credit total using the tag battery). The operations only work on positive integers, and the divisions only work on numbers that are divisible by 6.
This is accomplished using Whitespace and Bandwidth to do the actual arithmetic, plus Cell Portal and Wave to put them into a loop. In order to select which operation is performed, GPI Net Tap and Blackguard are used to force the Corp to rez as much ICE as possible, and Rook manipulates rez costs so that particular credit counts for the Corp cause particular combinations of ICE to be rezzed.
The Runner could attempt to interfere with the construction by choosing not to use GPI Net Tap or by breaking the subroutine on Cell Portal; Diviner and Data Mine are used to ensure that if the Runner deviates from the plan to a sufficient extent to change the output of the computation, the Runner loses as a consequence. (As long as the Runner follows the plan, the Corp has no ability to make any choices.)
The only restrictions the Archives setup places on the construction is that Archives can't be used for any other purpose.
The combination of the tag battery and Archives arithmetic produces a variable that can store unbounded values, and be multiplied and divided by 2 and 3. It turns out that that's all that's needed in terms of data storage in order to be able to write a Turing-complete language; however, in addition to being able to store data, programming languages also require some sort of workable control flow, in order to determine when to do the multiplications and divisions, and to perform operations conditional on the resulting value. This in turn requires some sort of method of storing or specifying the program that's being run.
Fortunately, it turns out not to be too difficult to create something like that in Netrunner. In this section, I'll look at how it's possible to store a program, and implement fully general control flow including conditional statements, using only two resources: the Corp's credit pool, and the ICE on HQ, the central server that represents the Corp's hand.
This construction uses three important numbers that help to remember the program / what the program is doing.
The first of these is a value I will call K. K depends on the size of the program that's being implemented within Netrunner; the larger the program, the larger K has to be. As such, it will have a fixed value for any given program (and thus can be "hardcoded" as part of the arrangement of the ICE on HQ) – but the construction needs to be able to work with arbitrarily large K so that it can be used to implement arbitrarily complex programs, and thus I'll talk about K in the abstract rather than fixing any particular value for it. This construction will choose K to be 6 more than a multiple of 36, in order to ensure that it produces the correct remainder upon being divided by various values.
Next up is the "instruction pointer" i, which remembers which part of the program is currently executing. The possible values for i are the integers from 0 to K − 1 inclusive, and each value refers to a short list of commands that exist within the program; you can think of them as "line numbers" like in BASIC. Individual instructions will be implemented using specific pieces of ICE, but there can be multiple instructions on a line; each of the instruction-ICE will correspond to a particular line, and the construction will be designed so that only the ICE that corresponds to line i (i.e. that implements an instruction on line i) can/will be rezzed. As such, the ICE that the Runner encounters will be precisely the ICE that corresponds to the current line.
Finally, there is the "arithmetic instruction register" a, which is used to determine which arithmetic instruction to execute using Archives. This can take on the integer values from 0 to 22 inclusive (0, 2, 20, 22 correspond to the four arithmetic instructions as in the previous section; the other values are allowed temporarily because its value can only be increased by 1 at a time, so a will have to be changed via meaningless values like 1 and 14 in order to reach large meaningful values like 22).
i and a will both be stored using the Corp's credit count c, using the simple formula c = 27i + a. This storage is unambiguous because 0 ≤ a ≤ 22 < 27, so it is always possible to extract i as the quotient and a as the remainder of c ÷ 27.
In the construction so far, the ICE on HQ starts as follows: rezzed Hourglass, rezzed Pachinko. In order to make HQ usable to implement the program's instructions and control flow, this "early" ICE will be made slightly more complex.
The first change is that the rez costs of ICE on HQ are going to be made much higher. In the Archives construction, I used one copy of Rook (which increases the rez cost of all ICE in the server by 2) in order to increase the cost of 0-rez ICE to 2, and 2-rez ICE to 4. For HQ, this construction uses (27K − 2) ÷ 2 copies of Rook, so that the rez cost of ICE that naturally costs 2 to rez will be increased to 27K. (Because K is 6 more than a multiple of 36, it will be even, so this can be accomplished using an integer number of copies of Rook. They need to be hosted on different ICE of the server, but it doesn't matter which – and despite the large number of copies needed, there will be plenty of ICE to put it on. If somehow not enough ICE were available, it would be possible to add extra ICE beyond the last ICE of the server – a point which the Runner will never reach, and thus the subroutines on the ICE don't matter – and host the Rooks there.)
These high rez costs are going to be used for multiple purposes during the construction, but the first of these purposes is to deal with a potentially negative interaction between two parts of the program: the tag battery, and the instruction pointer. The basic problem here is that while the tag battery is running, the Corp is gaining 27 credits per turn (i.e. increasing i by one, whilst leaving a the same), and thus the instruction pointer is moving forwards by one line each turn: when it goes above K, the instruction pointer will be "out of bounds" and the construction will no longer work correctly. In order to fix this problem, an unrezzed copy of Bloom is placed in between the Hourglass and Pachinko, hosting a Tranquilizer with at least two virus counters, followed by an unrezzed Diviner. Most of the time, this extra ICE has no effect on the construction because the Corp will not be able to afford to rez it: a rez cost of 27K can only be paid once the instruction pointer has gone out of bounds (and both the Bloom and Diviner share this rez cost). However, if the instruction pointer does end up reaching K while the tag battery is running, the Bloom will be rezzed, immediately deducting its rez cost of 27K from the Corp's credit pool and resetting the instruction pointer back to 0. Because the Bloom occurs before the Pachinko, this rez can happen even while the tag battery is running; thus, the "new" effect of the tag battery is, for each tag beyond the first, to give the Runner 3 credits, and to advance the instruction pointer by 1 line or to wrap from the end of the program (i = K − 1) back to the start (i = 0).
(The rez will be forced for the same reason as in the Archives construction: because there is lethal ICE with the same rez cost immediately behind the ICE whose rez is to be forced, an optimal Runner will expose and force the Rez of the Bloom so that they don't end up losing the game to Diviner's net damage, and the "follow this simple strategy" Runner will expose it because that's what the strategy says to do. Exactly the same technique can be used with all the other unrezzed ICE used in the rest of the construction; as such, I'll stop repeating the proof of "when this unrezzed ICE is encountered, it gets rezzed if and only if the Corp can afford to" and just let the proof be implied.)
Immediately after the Pachinko comes another change: a permanently rezzed Vasilisa, hosting a copy of Hush. Vasilisa normally has an on-encounter effect, but this is removed by Hush, leaving it with only a single subroutine, which gives the Runner 1 tag. As such, the Runner's tag count will become 1, and remain there throughout the rest of the run unless something happens to increase it further. There are two benefits from doing this: a single tag on the Runner is required for the Archives arithmetic engine to work correctly (and this provides that tag); and it cancels out the removal of 1 tag per turn provided by Boris "Syfr" Kovac: Crafty Veteran, meaning that each tag added in the rest of the run will directly power the tag battery, converting to 3 Runner credits and an instruction pointer increase (whereas if Boris's effect were not cancelled out, exactly one such tag would fail to convert, making the effects of tags harder to reason about).
The bulk of the ICE on HQ is used to store the program. The basic method via which this is accomplished is to represent each instruction using 9 permanently rezzed copies of Congratulations! (which gives the Corp 3 credits and the Runner 1 credit), followed by 3 permanently rezzed copies of Whitespace (which removes 3 Runner credits and ends the run if the Runner has 6 or less), followed by an unrezzed piece of ICE that represents the instruction (hosting a Tranquilizer with two or more virus counters), followed by a unrezzed piece of ICE with the same rez cost that will win the Corp the game if it ever gets encountered. The ICE that represents the instruction will generally have a printed rez cost of 2.
Let's think about what happens when the Runner encounters this sequence of 14 ICE. First, the 9 copies of Congratulations! will give the Corp 27 credits and the Runner 9 credits; then, the 3 copies of Whitespace will remove those 9 Runner credits again (and, assuming the Runner's credit pool never gets too small, will have no other effect). So, in effect, the instruction pointer has moved one line forwards; i has increased by 1 and nothing else has happened. If this moves the instruction pointer past the end of the program, the Corp will now have 27K + a credits, enough to pay the 27K rez cost, so the Corp will be forced to rez the ICE representing the instruction, the subroutines on that ICE will fire, and the instruction pointer will wrap back to the start (i becomes 0).
Now, think about what happens when K of these 14-ICE sections are placed immediately after each other. If i is K − 1, then the first section rezzes and fires the subroutines of its instruction-ICE (setting i to 0), and the other K − 1 sections increase i back to K − 1 with no other side effects. Likewise, if i is K − 2, then the first section increases i to K − 1, the section section wraps i back to 0 and fires the subroutines of the instruction-ICE, and the remaining K − 2 sections will increase i back to K − 2. The same pattern continues for all other values of i, with the final case being the case of i = 0, in which case the first K − 1 sections do nothing but gradually increment i up to K − 1, and the last will fire the subroutines of its instruction-ICE whilst wrapping i back to 0.
The upshot of this is that out of the whole sequence of 14K ICE, only one ICE gets rezzed: the ICE corresponding to the current value of i. Meanwhile, the effect of all the permanently rezzed ICE gets exactly cancelled out: the 9K copies of Congratulations! produce 27K Corp credits and 9K Runner credits, the 3K copies of Whitespace deduct 9K Runner credits, and 27K Corp credits are spent rezzing the instruction-ICE. Thus, the whole section is just a conditional that runs the subroutines of one of K different pieces of ICE based on the value of i, with no other effect involved.
The "programming language" being compiled into Netrunner allows multiple commands per line, but this can be solved using multiple sequences of 14K ICE: the first such sequence runs the first command on the line, the second such sequence runs the second command on the line, and so on. (This does mean that all the lines have to contain the same number of instructions, but this is trivial to arrange by placing extra "do nothing" instructions at the end of the shorter lines to pad them out to the same length as the longest.)
As such, each run on HQ that gets past the Pachinko will end up executing specificially the instructions on the line of code that corresponds to the value of i: we have implemented a method of storing and executing a program. All that's needed for Turing-completeness now is a Turing-complete instruction set.
There is a range of ICE that could potentially do something useful when used as instruction-ICE, but here's a set that's sufficient to do everything that's required:
The instructions in the previous subsection are almost enough to create a Turing-complete programming language, but one problem remains: they're purely control flow instructions, and don't have a way to read data (or indeed do any writing of data other than adding constants to or subtracting constants from the Runner's credit count). In order to complete the Turing-completeness construction, there needs to be some way to do arithmetic using Archives, and there needs to be a sufficiently powerful way to cause the program's control flow to depend on the data being stored.
In order to link the control flow on HQ to the arithmetic on Archives, two changes are made. The first is to place a restriction on the instructions that make up the program: every line other than line 0 will be restricted to contain a run-ending instruction somewhere (either the goto instruction Meru Mati or the halt instruction Diviner), whereas line 0 will be implemented entirely using the do-nothing instruction Bloom. This has the consequence that when passing the Pachinko with i ≠ 0, the run will end before it gets past all the instruction-ICE; whereas when i is 0, the instruction-ICE will do nothing and the run will proceed onto the subsequent ICE on HQ. That then allows a "goto 0" instruction to be special-cased into running different ICE than normal (in particular, it becomes possible to use ICE that is permanently rezzed or has weird costs).
The second change is to place two pieces of permanently rezzed ICE after all the instructions: Susanoo-no-Mikoto and Data Mine. The Data Mine exists purely to prevent the Runner breaking the subroutine on the strength-7 Susanoo-no-Mikoto with D4v1d, and will never normally be encountered. Meanwhile, Susanoo-no-Mikoto causes the run to continue from the first ICE on Archives rather than its current position (and also places some restrictions on jacking out, but those don't matter because the runner can't jack out anyway; they would immediately lose the game due to Ancestral Imager). This means that a "goto 0" instruction will have the effect of triggering the Archives arithmetic device. At that point, because i will be 0, the Corp's credit total will be 27 × 0 + a = a, and thus the choice of a as 0, 2, 20, or 22 will run one of the four arithmetic routines (×2, ×3, ÷3, ÷2 respectively).
In order to make this work as a full programming language, a couple of additional things need to be shown: that there is a way to choose where the program continues executing from after an arithmetic instruction is run (after all, the "goto 0" loses information about where the instruction pointer was), and that there's some way to build a usable conditional statement. For the ×2/×3/÷3/÷2 set of arithmetic commands, what's needed to produce a usable conditional statement is for the behaviour of the program to be able to be influenced by whether the result of a division by 2 is itself divisible by 2 and by whether the result of a division by 3 is itself divisible by 3.
Fortunately, the use of the tag battery naturally ends up solving both of those problems automatically, with no changes to the construction needed. Suppose that before running an arithmetic operation, the program adds a specific number of Runner credits. After the operation runs, then this will produce a predictable change in the result, e.g. adding 30 Runner credits, then dividing by 2, will cause the result of the division to be 15 Runner credits higher than it would otherwise have been; and because the result of the division is stored in the tag battery before being moved to the Runner's credit pool, the process of draining the battery to move the result into the Runner's credit pool will cause the Corp to gain an extra 27×5 credits, or in other words increase i by 5. This solves the first listed problem, by providing a mechanism of remembering which instruction to run after the Archives arithmetic is complete; simply give the Runner a precisely calculated number of extra credits first, then control will be transferred to an instruction based on how many you gave, and that instruction can subsequently remove the extra credits again.
The second problem can be solved by placing a restriction on what forms of numbers can be stored in the Runner's credit pool. In particular, let K = 36L + 6; now, the idea is to ensure that the Runner's credit pool is always 6x + 3, where x is of the form 2m × 3n × (6L + 1) (possibly with a small constant added to remember where to return after performing arithmetic). If m and n are both positive after an arithmetic instruction is performed, then the tag battery size will be divisible by 2 × 3 × (6L + 1) = K; this means that the Corp credit pool increases from the tag battery will end up wrapping back round to 0, except for those that come from the "extra Runner credits" used to remember where to return (because i wraps back to 0 whenever it reaches K). However, if after a division by 2, m is 0 (i.e. x is not divisible by 2), the size of the tag battery will no longer be divisible by K; there will be a remainder of K ÷ 2. A similar principle applies with division by 3, with n being 0 meaning that there will be a remainder of K ÷ 3. These remainders will end up being added onto i as a side effect of the tag battery, transferring control to one of two different places depending on whether the result of a division by 2 or 3 is itself divisible by 2 or 3. In other words, this produces a naturally occuring method of implementing a conditional / "if" statement.
This section explains how it's possible to arrange ICE on HQ so that, depending on the Corp's credit count, a specific selection of ICE will fire its subroutines. This is achieved via increasing the rez cost of ICE on HQ to a very high value, and gradually increasing the Corp's credits using Congratulations!, repeatedly attempting to force an ICE rez in between increases; when the Corp can afford to rez ICE, they must do so, resetting their credits back down to a much smaller number. As such, the Corp will only be able to afford to rez every Kth instruction ICE, but the position from which the rezzes start will depend on the Corp's credit count.
It also explains how HQ and Archives interact in order to allow for the data storage to affect the program's control flow. Transferring control from HQ to Archives is done using Susanoo-no-Mikoto. If this occurs, on the next run, the Corp's credit count will depend on how long the tag battery ran for, which in turn will depend on the result of the arithmetic operation. It is therefore possible for the code on HQ to determine what the Corp's credit count will be by changing the Runner's credit count before the operation is performed, in order to make use of the predictable effect this will have on the Runner's credit count afterwards. This also allows for conditional branches: the Corp's credit count will only have its "usual" value as long as the Runner's credit count is divisible by certain numbers, and if sufficiently many factors of 2 or 3 are divided out of it, this will cause the tag battery to run for a number of turns that is not divisible by K and thus change the piece of ICE at which program execution resumes.
The previous sections cover the entire construction, specifying a Netrunner gamestate that implements a programming language. All that's needed to complete the proof is to show that that language is Turing-complete.
This section will start by describing the language in question – although you could in theory figure it out from the description of the construction, it is likely much more intuitive to see it all in one place – and then prove that the resulting language is Turing-complete.
The language consists of a program made out of K lines, for arbitrary positive K of the form 36L + 6 and integer L. Each of these lines contains one or more instructions, the same number in each line. The lines are numbered from 0 to K − 1 inclusive; each line must contain a Meru Mati instruction, except for line 0 which must consist entirely of Bloom instructions.
Data is stored using five counters, m, n, a, e, t, together with an instruction pointer i that remembers which instruction is currently executing. m and n are general-purpose and remember data from one line to the next, whereas a/e/t are special-purpose counters used to provide the arguments to instructions.
Program execution starts at the start of a line i specified by the programmer, and with t = 0 but with the values of the other counters specified by the programmer.
The following instructions exist:
| Instruction | Behaviour | Requirements |
|---|---|---|
| Bloom | No effect. | Always legal. |
| Diviner | Halts the program. | Always legal. |
| Vasilisa | Increases t by 1. | Always legal. |
| Whitespace | Decreases e by 1. | e must be positive. |
| Harvester | Increases a by 1. | a must be 21 or lower. |
| Meru Mati (t ≠ 0) | Increases e by t and continues execution at the start of line t, resetting t to 0. | t must be nonzero. |
| Meru Mati (a = 0) | Increases m by 1. Doubles e, then continues execution at the start of line e. Resets a to 0. | t = 0; a = 0; n > 0. |
| Meru Mati (a = 2) | Increases n by 1. Triples e, then continues execution at the start of line e. Resets a to 0. | t = 0; a = 2; m > 0. |
| Meru Mati (a = 20) | Decreases n by 1. Divides e by 3, then continues execution at the start of line e (if n is now nonzero) or e + (K ÷ 3) (if n is now zero). Resets a to 0. | t = 0; a = 20; m, n > 0; e is divisible by 6. |
| Meru Mati (a = 22) | Decreases m by 1. Divides e by 2, then continues execution at the start of line e (if m is now nonzero) or e + (K ÷ 2) (if m is now zero). Resets a to 0. | t = 0; a = 22; m, n > 0; e is divisible by 6. |
Here, "requirements" lists conditions that are necessary for the instruction to behave correctly: the instruction's behaviour is undefined if the requirements are not met. The Meru Mati instruction has five variants; it can be used if the requirements of any of the five variants are met, and which variant runs will depend on which of them has its requirements met. Each of the variants cause control flow to move elsewhere; this causes the rest of the instructions in the current line to not run.
An attempt to transfer control to a line specified by t or e, but where the specified line number is greater than K, is not an error (unless the specified line number is divisible by K, which produces undefined behaviour) – the line number wraps modulo K. This fact is a side effect of the way the construction works and not required for Turing-completeness.
(These correspondences hold whenever the Runner is currently running and is at the start of of one of the "instruction blocks" made out of 14K pieces of ICE.)
The Runner's credit total is 6x + 3, where x is 2m × 3n × (6L + 1) + e.
The Corp's credit total is 27i + a.
The Runner has exactly t + 1 tags.
The language above is pretty similar to a counter machine with two counters m, n, and such machines are known to be Turing-complete. The idea is for the values of m and n to store values that are 1 higher than the corresponding values in the counter machine, and to write every line that runs as a consequence of decrementing a counter to 0 in such a way that it immediately increments it back up to 1: this gives "increment" and "decrement, or jump elsewhere if zero" instructions on each counter, which is all that's needed for Turing-completeness in terms of ability to handle data.
As such, all that's required is to be able to produce reliable control flow using the control flow instructions. Although the behaviour of e and t is weird, this is pretty easy to work around. The idea is that for all lines other than lines that are branched to as a consequence of decrementing a variable, e will always be equal to their line number i, a condition which is easy to ensure via decrementing e to 0 immediately before running the t ≠ 0 variant of the Meru Mati instruction. As long as lines that are branched to via decrementing a variable to 0 are never jumped to directly, this means that the values of e and t will be statically known at every point in the program. This in turn makes it possible to branch to arbitrary lines by jumping to a line late in the program using the t ≠ 0 variant of Meru Mati: then e will be high enough that you can decrement it to provide the required value of e for the t = 0 variant. Likewise, there is no reason to increment a at any time other than immediately before a Meru Mati instruction that requires a ≠ 0, which will reset a back to 0, so the value of a will also always be known.
This language can therefore emulate a two-counter machine both in terms of data processing and in terms of control flow, and thus can emulate the entire behaviour of the two-counter machine. Because this sort of two-counter machine is Turing-complete, so is the construction – and thus so is Netrunner.
Although a single proof is all that's needed to show that a language – or a card game – is Turing-complete, that isn't necessarily the end of the topic. Here are some additional thoughts that I've had about Netrunner and Turing-completeness.
With the current version of the proof, there's no way for the Runner to ever win (unless the Corp deviates from the strategy). This is unsatisfying in a sense: the possible outcomes are "Runner loses" or "the game lasts forever without anyone winning", which might induce a hypothetical optimal Runner to concede.
In the "players play optimally" version of the proof, it is possible to add an additional instruction-ICE that allows the Runner to win the game: Tithonium, which destroys two programs and a resource and ends the run, and has a rez cost of 9 (and can also be rezzed for 0 by forfeiting an agenda), and can't host cards. This is an ugly ICE to use for a construction for several reasons: the rez cost is a mess (although you can work around it by setting a to 7 before the Tithonium instruction runs); because it can't host cards, you can't use Tranquilizer (although that theoretically shouldn't matter because once it's rezzed, the game should be over); and the program-trashing messes up the Nerine 2.0 server (although this can likely be worked around via the use of redundant copies of Tracker and Kyuban so that the Corp can't trash enough of them). It also doesn't work in the "follow this simple strategy" version of the proof because, despite being able to run into the Nerine 2.0 remote, the Runner won't run there and will run HQ instead (also, the "follow this simple strategy" Corp won't know which programs to trash).
As such, it would be nice to find some alternative method to allow for a Runner win. I suspect that this is possible by allowing the Runner to actually succeed in a run, which might in turn be possible if Susanoo-no-Mikoto were an instruction-ICE rather than just sitting permanently rezzed on HQ. The rez cost is high, but that can be worked around by letting a go even higher (and by replacing the "27" used throughout the proof with some larger value); and the uniqueness shouldn't be a problem because only one is rezzed at a time. It is hard to make this compatible with D4v1d, but may be doable using Bishop and Ice Carver which are collectively just about capable of getting its strength down below 5. (Normally you could use the combination of Chisel and Rover Algorithm to set an ICE to any desired strength – they cancel each other out – but the difference in timing means that this doesn't work with Susanoo-no-Mikoto in particular.)
Both of these problems make me somewhat dissatisfied with the Nerine 2.0 remote. (The remote has other issues too, like preventing the use of Front Company which would solve a number of problems on its own if not for the conflict.) It would be nice to find an alternative solution to prevent the Corp doing resource trashes and virus purges.
One other reason it would be nice for the construction to be able to produce a Runner win in addition to a Corp win would be that it would allow for the emulated programs to have two different halt states, allowing you to take output from the programs you run. Instead of just having "halts" and "doesn't halt", which is all that's needed in terms of I/O for a language to be Turing-complete, it would provide the ability for a halting program to say "yes" or "no" and thus you could actually get some sort of output from it (other than just looking at the credit totals at the end of the game to see what the program was thinking).
This construction uses draft rules in order to get around the influence and card-limit restrictions. That conveniently gives an excuse to use draft identities too, which makes it possible to use Boris "Syfr" Kovac: Crafty Veteran as a method of removing tags in a choice-free and predictable way. But draft identities aren't a part of Netrunner as it's generally played nowadays, and it's an interesting question as to whether it might be possible to find a working construction without the use of any draft-specific cards.
It seems almost certain that any construction for Netrunner will need to find at least three places to store data between turns (the Turing-completeness constructions that work with only two such locations tend to require the ability to do things that are unlikely to be printed on any Netrunner card). The two players' credit counts are two of the most important values in regular Netrunner play, so it's not surprising that a lot of cards and game mechanics interact with them, and they make obvious choices for data storage. Tags are the "obvious" choice for the third, as the next-most important Netrunner value that persists between turns, but I couldn't find many cards in the regular non-draft card pool that remove tags in a predictable enough way to use in the proof (tag-removal cards are generally designed in such a way that either a player can choose to simply not use them, or else in a way that allows the other player to spend to prevent the removal, and either of these would hurt the proof). The most promising candidate is End of the Line; if the Corp has fewer than 6 cards in their central servers, they have to play it in order to have a card to recycle in order to avoid decking out. There are two problems with that, but at least one is likely to be resolvable. One is that even if the Corp doesn't play it, there is a turn before the Corp actually loses, with the tag and credit counts being messed up during that turn; however, the tag count being too high is likely to produce a harmless turn in which the Runner bounces off Pachinko. The other is that you need to give the Runner a lot of defences to be able to survive being hit by an End of the Line every turn, and those would be likely to mess up other parts of the proof.
A more promising approach is to use something other than tags as the "third number". Most such quantities in Netrunner don't have many cards that interact with them, so the selection is limited, but fortunately there's one card that happens to pretty much form a "natural" battery: Nightdancer. This has two subroutines, each of which cause the Runner to lose a click if they have one (irrelevant to this construction), and the Corp to gain one click next turn. This "extra clicks next turn" quantity can go unboundedly high, and on the Corp's next turn, those extra clicks will turn into credits (because the Corp has been locked down to do nothing with their clicks other than clicking for credits). The key observation is that because the Corp's credit total never actually goes above 27K, the values "above" that can be used in much the same way as tags are in the existing construction, i.e. each extra 27K Corp credits corresponds to one tag. In order to create something that functions like the tag battery, just replace the Bloom and Pachinko with an unrezzed and tranquilized run-ending ICE; that way, as long as "there are tags" (i.e. the Corp has enough money to rez that run-ending ICE), the Runner doesn't get past the point where the Pachinko would have been.
The Nightdancer approach can't be directly dropped into the current proof. Partly, this is because some of the numbers are different. Partly, it's because unlike Bandwidth which has a lower rez cost than Whitespace, Nightdancer's is higher, and this messes up the method for determining which ICE gets rezzed on Archives. There is probably some way to make it work, but I haven't yet looked into this alternative proof technique.
As the quote at the top of this article suggests, I previously analysed Netrunner and decided it probably wasn't Turing-complete at the time. Now, it is. So there must have been some specific point in time at which this changed.
Attempting to determine the exact moment that a Turing-complete construction became possible is a case of looking at progressively smaller and smaller card pools, removing the newest sets from the card pool one at a time until a construction is no longer possible. I've used cards from throughout Netrunner's history in this article, but in many cases there were choices. For example, Hush (from Parhelion) + Vasilisa (from Midnight Sun) is the easy way to create a tagging instruction (it has rez cost 2 and no awkward riders), but involves two very new cards; prior to those sets being released, that approach wouldn't have worked, but it would probably still have been possible to make something viable using Bandwidth. (There are actually surprisingly few tagging cards that give nobody a choice, and most of them are newer cards; most of the older tagging cards involve traces which allow players to choose how many credits they spend, and most of the rest end the run. Bandwidth is almost unique among older cards in having an unconditional tagging subroutine and a complication that doesn't matter for the proof, so it's fortunate that it exists.)
I don't know for certain, but my guess as to when Netrunner first became Turing-complete is the release of System Gateway. That set contained two critical cards: Whitespace which provides a reliable way of reading the Runner's credit total, and Tranquilizer which (when used with Blackguard and GPI Net Tap) provides a reliable way of reading the Corp's credit total (and also allows cards' rezzed/unrezzed status to actually be usable in a construction: I can't think of any derez effects prior to Tranquilizer that work predictably enough to be used in a proof).
The discussion in this article's introduction happened in November 2020, with System Gateway released towards the end of March 2021. That probably isn't enough time for Null Signal Games to have reacted to the conversation, so it's likely just a coincidence that I talked about how there were no reliable ways to do something conditional on the size of the Runner's credit pool, and then Whitespace was printed which does precisely that (in a way that is almost perfectly usable for the proof). However, the subsequent printing of Valentão, which does something very similar for the Corp's credit pool, has certainly got me wondering (even if I didn't need it for the proof) – Null Signal Games are more involved with and reactive to the community than many other games companies would be.
I discussed the issue of "is Netrunner Turing-complete without draft cards?" earlier; an interesting direction for expanding the proof is to try to see if Netrunner is Turing-complete with other restrictions on the card pool.
One of the restrictions I've been most curious about is whether it's possible to prove Netrunner Turing-complete without requiring unlimited influence (which means that all but a small finite number of cards for both players have to belong to a single faction). On the Runner's side, the obvious choice for faction is Criminal (primarily for Tranquilizer, but many of the less critical cards are also Criminal cards); the primary obstacle for a Criminal-only runner is Rook which is an Anarch card that's also needed in large quantities. For the Corp, most of the ICE required in quantity is in NBN (e.g. Congratulations!, Bandwidth) and most of the rest can probably be replaced by NBN equivalents. The primary problem there is that Ancestral Imager cannot be run in an NBN deck at all, not even by making use of your limited ability to run cards from the wrong faction, so some other method would need to be found to prevent the Runner simply just jacking out and messing up the calculations. These faction choices make a lot of flavour sense, being the two factions which are most into the theme of "credits matter", with credit totals being the most critical quantity for the proof.
What about using only newer cards? Fantasy Flight's card pool is not (as far as I can tell) Turing-complete on its own, but Null Signal Games's is expanding. I can't find a way to make the construction work using only Null Signal Games cards; there are too many missing critical cards like Cell Portal, Ancestral Imager and Blackguard. But the omissions in the Fantasy Flight card pool are fairly fundamental (not being able to read data is a huge obstacle to Turing-completeness), whereas the omissions in the Null Signal Games card pool are more superficial, mostly related to making it hard to lock down the players' actions; one way to think of it is that the Netrunner-related part of the construction uses mostly Fantasy Flight cards, but the programming-related part of the construction uses mostly Null Signal Games cards, and the former part seems more replaceable than the latter. So perhaps Null Signal Games' cardpool will be Turing-complete in the future.
The language implemented by this construction is Turing-complete. But it's slow. Really, really slow.
The primary problem is that two-counter machines are already very slow. They can store an arbitrary number of variables, but they do so by storing each variable as the exponent of a prime number within one of the counters (say m); m might be 2 to the power of the first variable, times 3 to the power of the second, times 5 to the power of the third, and so on. The other counter (say n) is used as a temporary in order to actually perform the multiplications and divisions. This means that all operations have exponentially slow performance, because the only way to read m is to gradually decrement it down to 0, changing it by 1 each time (and using n to remember its value while doing so).
This construction is doing something very similar, using two counters to emulate a counter machine with an exponential slowdown; here, it's using two counters (r as the main register and and t as the temporary) in order to store two counters (m and n) via using the exponents of 2 and 3. This means that the performance of the construction as a whole is double-exponential: there is an exponential slowdown when using the Netrunner credit pools to emulate the counters, and another exponential slowdown when using the emulated counters to emulate anything else. There's no point in actually trying out this construction in practice: you'll never get anywhere in any reasonable time.
So an obvious question is as to whether it might be possible to avoid the awkward and slow nested emulation. The obvious approach is to try to encode more than just two factors into r, meaning that the construction could emulate a language that had more than two general-purpose counters rather than being stuck with just m and n. However, it isn't obvious exactly how to do that: it was somewhat tricky as it was to set up Archives in such a way that both division and multiplication by both 2 and 3 were possible using different values of a. Part of the problem is that the rez cost of Whitespace is so similar to that of Bandwidth, which gives very little room for changing the quantity-rezzed of both ICE purely by changing the Corp's credit count.
One approach that would avoid this problem would be to use two different servers for arithmetic: one for division and one for multiplication. That way, only one ICE per server would need to have its rezzing status manipulated, which is easy to accomplish and would allow for multiplication and division by arbitrary ratios. The problem there is in how you redirect the Runner to a specific server; all the redirection cards that are locked to a particular server redirect to Archives. A solution to this problem would probably have to involve using HQ for, e.g., both control flow and multiplications, whereas Archives continued to handle the divisions. That might be achieveable, but would be quite difficult because there are a number of potential obstacles; for example, when you send the runner back to the start of HQ, they would slam back into the tag-battery ICE whilst being tagged and the run would end, so you'd need to make use of an allotted-clicks-next-turn battery instead.
Another possibility would be to avoid the use of a battery altogether, and instead use two different counters that were both able to meaningfully persist between turns, with control flow dependent on each. Although the obvious approach here is to use Runner credits and Corp credits, control flow then becomes very difficult to do as there's nowhere obvious to record the currently executing part of the program. I did look into doing this via using the Runner's current position during a run, but there didn't seem to be enough computational power available to make that work, so some third persistent counter would have to be found; most likely you would need to use tags, but via a mechanism that's more complicated than the tag battery used in this article.
Alternatively, there might be some entirely different way to do the construction which has less disastrous performance properties than this one. It is hard to see how you could produce anything other than a counter machine using Netrunner's current card pool, though, because pretty much all the game has available to store data is counters; it isn't like some other card games where it's possible to add new cards (or card-like objects) to the game in unlimited quantities during play and use those to store data.
This proof is much more involved than most of my
Turing-completeness proofs have been in the past, and it's quite
plausible that I've made mistakes somewhere, either with respect
to the details of the construction or with respect to
the Netrunner rules. If you find something wrong, or
just have comments, you can contact me by email
(ais523 at this domain).
I'll be posting this proof on the Stimhack forums; if you're looking to discuss it with other people, or me in public, that would likely be the best place nowadays.