April 18, 2023

TIL (Today I learned)

Magic the Gathering is Turing Complete

I came across a Hacker News post that discussed the Prolog programming language. I had read about Prolog years ago and thought it sounded interesting and cool. I had forgotten about it in the years since. As I read the linked article about Prolog, I realized I needed a refresher on what "Turing Complete" meant, and in the process of reading about Turing completeness on wikipedia, I saw a few examples of different games - both video games and table top games - that are Turing complete. I shouldn't have been surprised that Magic: The Gathering is Turing complete, but of the listed games in the wikipedia article, it was least obvious. The others being of the Minecraft variety.

Here are the breadcrumbs I followed: Hacker News -> Prolog -> Turing Complete -> Magic the Gathering is Turing Complete

Specifically:

Hacker News

https://die-partei.social/@hackernews/110223537084765209

Prolog

https://www.kmjn.org/notes/prolog_lost_steam.html
https://en.wikipedia.org/wiki/Prolog

Datalog

https://en.wikipedia.org/wiki/Datalog

Turing Complete

https://en.wikipedia.org/wiki/Turing_completeness
https://en.wikipedia.org/wiki/Turing_machine

Magic the Gathering is Turing Complete

https://arstechnica.com/science/2019/06/its-possible-to-build-a-turing-machine-within-magic-the-gathering/
https://www.toothycat.net/~hologram/Turing/index.html
https://www.toothycat.net/~hologram/Turing/HowItWorks.html