I don’t know the details, and suspect I wouldn’t fully understand it having never played Magic the Gathering, but I recently learned that someone found a card combo in the game that deals infinite damage… if and only if the twin prime conjecture is true… and I thought it was mind blowing when I found out MtG is Turing Complete. Also laughed my arse off for like 5 minutes straight when I first heard about it.
4 Likes
Yes. The amount of logic needed for a system to be Turing-complete is smaller than most people think. After all, a Turing Machine proper is a simple mechanism. A striking example: Minesweeper is Turing-complete, on an unbounded board at least. But even finite board versions of Minesweeper are NP-complete from a solution computation standpoint. The interesting thing about this is not so much the proof of the fact itself, but the engineering that is needed to build logic gates using Minesweeper configurations.
MtG is much more complex than Minesweeper or a Turing machine, so the fact that its logic can be used to build computational devices shouldn’t be that surprising.
This misperception is similar to the one about Gödel incompleteness: the amount of logic machinery that a formal system needs to automatically fall into the scope of both first and second incompleteness theorems is quite small: the Peano axioms do qualify, after all. This means that any consistent axiomatic framework capable of describing the positive integers can also generate true statements which are not provable within it. Worse still: if such a system can prove it is consistent, it’s because it is actually inconsistent.
5 Likes
Vaguely topical, made long ago for a bring-your-own-cards MTG draft:
Card text for those using screen readers
Georg Friedrich Bernhardt Riemann 1U
Creature - Human Mathematician
1, name a non-trivial root of the Riemann zeta function with real part not equal to one half: Draw any number of cards, then put one million +1/+1 counters on Georg Friedrich Bernhardt Riemann and he gains flying, vigilance, lifelink, hexproof, trample and indestructible.
1/4
4 Likes
Yes! It’s a hilarious combo, though it doesn’t quite deal infinite damage.
My layman’s explanation would be:
- In a game of Magic, players have “life totals”, and you win if you do enough damage to reduce your opponent’s life total to zero.
- Nothing in Magic can ever truly be infinite: you can have a combo that gains you an arbitrary amount of life, or deals an arbitrary amount of damage, but you have to choose a finite number (though it can be something like “seventy million googolplex” or “Graham’s number” or “TREE(3)” if you want).
- There’s a certain combination of cards that will let you deal damage equal to the number of “lands” you control, if and only if that number of lands is prime. (The key is the card Zimone, All-Questioning.) But it only works once.
- Alice has that combination, plus a way to make an arbitrary number of lands. Bob, meanwhile, has a combo to gain an arbitrary amount of life.
- Alice also has a way to disrupt Bob’s combo on her turn, which forces him to use it on his turn—that is, he now has to choose what that arbitrary number will be, and once it’s locked in, he can’t change it. So Alice can then win if she chooses a higher number! And since there are infinitely many primes, she can always choose a prime number higher than what Bob chose.
- But not so fast—Bob has a way to destroy one (and only one) of Alice’s lands. He can wait until her combo is going, then destroy one of her lands, leaving her with a non-prime number, and the whole thing will fizzle out!
- But wait, there’s more! Alice also has a way to destroy one (and only one) of her own lands. This means that her combo will still work, if and only if she can choose a twin prime larger than Bob’s arbitrarily large life total—then, if he destroys one land, she’ll destroy another land, and still end up with a prime number of lands (letting her win).
- So the question is: can Alice always win? Or can Bob choose a number that lets him win—that is, a natural number larger than the largest twin prime?
- By the rules of Magic, Bob just needs to describe his number with sufficient detail that everyone can agree on what it is: you can say “TREE(3)” without listing all the digits. So if the twin prime conjecture is false, he can name “the largest twin prime plus one”, and he wins. But if the twin prime conjecture is true, Alice can name “the smallest twin prime that’s larger than Bob’s number plus two”, and she wins.
- Thus, who wins the game depends on the twin prime conjecture!
4 Likes
This is trickier than it sounds. Bob could name “the busy beaver function value BB(748)”, which undoubtedly exists and is computable (as is every individual integer), but nobody can ever prove within the usual set theory framework that any given integer equals that function value.* I would immediately object to Bob that I can’t agree what that number is, unless he can show me code that computes it given enough time. Good luck with that.
*From this paper, quoting Section 4.2:
One of the most striking facts about the Busy Beaver function: that for any axiomatic theory (for example, ZF set theory), there exists a constant c such that the theory determines at most c values of BB(n).
3 Likes
I found this: 1-bit-art.
https://quiltro.org/site/blit.html
There mathematical formulas are used to draw a black-and-white picture. It fascinates me. The example displayed there looks a bit like an Escher picture.
Edit: While (unsuccessfully) trying to implement a Mandelbrot set, I came to understand imaginary and complex numbers! 
3 Likes
True, the Turing Machine is ridiculously simple in its construction, so it shouldn’t be surprising something with even a bit of complexity is turing complete. Still, as far as I know, Magic the Gathering is the only card game that’s been proven Turing complete and I’m not aware of any others have even been conjectured as such, though, as the rationalist proverb states, “That which can be destroyed by the truth should be”, so if you know of other card games that are conjectured/proven to be Turing Complete, or even other types of game, I’d love to hear about it. Also, had no idea minesweeper was Turing Complete.
Though, now I’m curious, how hard is it to prove a system is Turing complete? And are there systems that intuitively look more complex than a Turing machine, yet are Turing Incomplete?
And shifting a bit from computational theory to game theory, something I’ve been wondering for a while is whether it’s possible to have a 3-player game where, if a player is will to take last place, they can force a tie between the other two players or if such a question actually makes sense within game theory… or if there have even been any significant results in game theory regarding 3-player games since it feels like whenever I stumble on a article or video on game theory, it’s always about either a zero, 1, or 2 player game. Persumably every extra player ups the complexity significantly, but does a third player really make everything so intractable?
1 Like
And are there systems that intuitively look more complex than a Turing machine, yet are Turing Incomplete?
If you want to be nitpicky, then arguably C is Turing incomplete because any given implementation of C has a hard limit on how much memory can be accessed (due to needing to define a specific size for the void* type), and Turing completeness requires unbounded memory.
Of course, if we’re talking about actual physical hardware then no computer can have infinite memory, but the difference between C and (e.g.) Python is that the nature of the C language itself requires there to be some fixed size for pointers, whereas in principle, if a machine with infinite memory existed, you could implement a Python interpreter that’s capable of using all of that space while still being fully compatible with the Python language reference.
More close to the IF sphere, I’m pretty sure Ink is not Turing complete either (assuming no external functions), despite being a fairly powerful scripting language, for similar reasons. Ink simply doesn’t offer any data type that would allow you to simulate an unbounded tape. (EDIT: On second thought, technically you can do it with strings, it would just be wildly inefficient because the string processing abilities in Ink are super limited)
1 Like
I’m not that knowledgeable on CS theory, so I’ll focus on this part, which I can answer. As far as we know, the answer is yes to both questions.
Such games do exist, but the literature on them is very technical. The magic incantation you need to search for is “Nash equilibria in congestion games”.
3-player games are intractable in general, but some subsets of N-player games with certain restrictions have been studied. The main problem with general 3-player theory is the possibility of coalitions / collusions. Conditions for equilibrium can get very hairy unless you limit the type of game boundaries. Typically, the payoff space for a 3-player game is an algebraic variety given by a polynomial in 3 variables. Equilibrium is given by solving for zero slope on all three axes, but equations being nonlinear, there is no general nice expression for such roots. The moment the game is even slightly involved, solutions may exist but don’t have closed expressions.
It gets worse: in 2-player games, there is a large subset of them called sparse games, in which almost all of the pay-off matrix entries are zeros. These are polynomial-time algos for “solving” these games, but with 3-players, no such things are possible: the situation has been proven to be PPAD-hard. This means that solutions for 3-player sparse games may be obtained computationally, but there is no chance of feasibility in a general sense for time bounds on getting those.
3 Likes
I’m currently reading a pop-math book. It’s about graph theory. I first wanted to post this in the ‘reading’ thread, but I think the general interest in a math book is much higher in this thread.
It’s originally in French “L’Agrapheur” and I’m reading it in German “Der Graf der Graphen”. It’s by Professor Alain Hertz, and I fear it is not available in English. 
(It’s from 2010 so maybe there’s a translation to English now.)
It’s about applying graph theory to real life problems, written as a story. In real life, in his job, the author applies graphs to police work, finding criminals with this tool! I’m not far in this book yet, so I don’t know if he also talks about criminalistic graph theory in the book.
I also think with Euler’s revelations about graphs one can prove the 4-colour-map theory.
1 Like
Partially true, depending on what you mean by “prove”. The 4-colour conjecture became a theorem in 1976, when it was proven for the first time after more than a century of unsuccessful attempts by very illustrious mathematicians. The original proof involved computer verification, since it requires painstaking checking of a taxonomy of 1936 possible cases. Since then better proofs have been achieved: a simpler proof was published in 1997 and another one in 2005, this one using general purpose theorem-proving software.
The fact is that Euler’s discovery that the characteristic of every connected planar graph is 2 can be used easily to prove that 6 colours suffice to paint a map in the plane so that no two regions with a common boundary have the same colour. I did this when I was a student; it’s a good exercise. This of course is far weaker than the best possible result, which is that only 4 colours suffice, but even proving this for 5 colours (not done until 1890) is much more difficult, let alone 4. Euler’s observations are only marginally tangential to the core of these proofs, which need much more sophisticated techniques only developed in the second half of the 20th century (such as quantization of moduli algebras).
3 Likes
I am reading a pop science magazin about quants. And it mentions the heavy involvement of math (even theoretical math) in physics. Just like someone said here. It mentions Jean Ecalle and his “resurgence”. Quite cool stuff.
Edit: Found a gratis online version of the text:
1 Like
Here is a pair of questions for the mathematicians on here. I remember years ago doing a practice GRE test. One of the questions on there had only a 13% chance of people getting it right. People did horrible on it! I’m going to reproduce it here for our mathematicians to try. Because knowing it’s a hard problem makes it easier, I’ll post two problems and you won’t know which one is hard.
Problem 1:
Let G be a graph such that every two distinct vertices in G are connected by exactly one edge and every edge connects two distinct vertices. If G has 190 edges, how many vertices does G have?
Problem 2:
How many times do e^x and x^12 intersect?
[I got both of these problems wrong originally, one due to just a dumb mistake and the other due to a really dumb mistake]
Sorry, deleted previous comment semi-unintentionally.
Unless I’m missing something obvious, the answer for Problem 1 is 20 (easy) and Problem 2 is 3 (hard-ish?)?
(giving myself minor anxiety by committing to an answer under my real name on a public forum indexed by google.)
1 Like
Both are right! I mixed up n Choose 2 with the sum of 1 … n, and for the second one most people going fast answer 2 instead of the correct answer (which you gave).
Great job!
Problem 1:
You’re just describing a complete graph. So it has 20 vertices.
Problem 2:
There’s obviously one intersection where x < 0. But the real question is, are there 0 or 2 positive values? Since e^2 is clearly less than 2^12, the answer to this one must be 3.
2 Likes
Very natural, because the sum of 1…n is (n+1 choose 2). Both expressions equal n(n+1)/2. A less known fact is that n in this expression is called a “triangular root”, which makes sense because the partial sums of the positive integers are called triangular numbers (since they are the counts of things that can be arranged in equilateral triangles) and is a tongue-in-cheek take on “square root”. So Problem 1 is reduced to asking “what is the triangular root of 190?”, which sounds a bit whimsical but is actually a proper question.
By the way, the expression for the triangular root of m is n=(sqrt(8m+1)+1)/2. If m=190, then n=20. Knowing this by heart is more useful that appears, especially in combinatorial coding.
1 Like
To be fair, I probably would have got it wrong if I was rushing & hadn’t been warned that one of the questions was hard. So including the other question didn’t really resolve that issue.
1 Like
An article about an interesting result involving the menger sponge and knots landed in my inbox recently:
As if I didn’t already have plenty of reason to love this fractal.
Though, two things I’ve been wondering about lately that I’m not sure how to tackle:
-
sin(x), cos(x), -sin(x), and cos(x) form a cycle of derivatives and if you graph them simultaneously, they resemble a braid… If each of the functions is treated as a strand, is there a four strand braid such that each strand always crosses over its derivative and that removing any one strand undoes the braid?
Also, e^x forms an infinite cycle of derivatives of period 1 and the above mentioned functions form a cycle of period 4. Are there any other well known functions where repeated differentiation gives the original function with other period lengths? -
The classic example of a linked pair of toruses is a pair of congruent toruses where band radius equals hole radius, though such a snug fitting pair can be generalized to pair where hole radius of one torus equals band radius of the other… But I got to thinking about making the hole of one torus larger to let two or more toruses slide along it’s band… Assuming a starting band radius of 1 and hole radius of 1, if I’m doing my math right, such a torus would have a volume of 4pi^2, and increasing the hole radius to two to allow a second unenlarged torus to be added, the larger torus now has a volume of6pi^2… But can things be kept snug while making the main torus have a volume equal to the smaller toruses combined? The ratio of the smaller torus’s band radius to the larger torus’s hole radius is fixed, and would be for larger numbers of satellite toruses as well, and the main torus’s band radius is equal to the satellite torus’s hole radius, so I think there’s only one degree of freedom here, namely the ratio of main torus band ratio to it’s hole radius and satellite torus band radius… though the related question of how large a circle has to be to fit a ring of n pairwise tangent unit circles that are tangent to the larger circle(I know the larger circle has radius 2 for n=2 and 3 for n=6, but no idea for other values of n.
1 Like
I think you were probably hoping for something more exciting, but I will note that the constant-zero function also gives a cycle of derivatives with period 1.