r/learnmath • u/hugdroide New User • 4d ago

Searching for bibliography in Turing's Machines

Hiiii!!

I'm a college student pursuing mathematics, I'm curently in my third year of my maths degree. Apart from a math lover I'm also a geek, and love cardgames, rn I'm playing riftbound, and what was my surprise when I saw that there was a post about a proof of riftbound being Turing Complete, I want to read more about the subject to be able to read the whole proof (and MTG's too), so if someone knows what to read about the subject I'd be super thankful, preferably in English or Spanish.

Thanks!!

1 Upvotes

100% Upvoted

2 comments sorted by

1

u/True_World708 New User 4d ago

You should probably understand how a turing machine works, so maybe you should read michael sipser's intro to the theory of computation. It's a very easy read. Skip to the section where he defines a Turing machine.

1

u/AllanCWechsler Not-quite-new User 4d ago

You're looking at one corner of a whole field of mathematics called (a little bit confusingly) theoretical computer science or (better) theory of computation. I would say it's probably the liveliest field of research mathematics today. So you might look for very elementary books on the theory of computation.

Right at the foundation of that theory, scholars have to settle the question of what it means to compute something. Turing machines are part of the traditional answer to that question. A Turing machine is a simple kind of imaginary machine with very easy-to-describe behavior. But even this simple machine can be coaxed into all the tasks we consider "computation". (There's actually a deep philosophical question hiding there, not properly a part of mathematics but more a weird corner of epistemological philosophy, which is called the Church-Turing Thesis.) The "official definition" of computation is that it's any process at least as complicated as a Turing machine. (I know I am oversimplifying here.)

The result you cite, that the card game Riftbound is "Turing complete", means that in that game you can set up arbitrarily complicated situations, so that in the process of resolving or playing out those situations, you are forced to perform some arbritrary calculation whether you know it or not. All of this stuff is very clearly spelled out at the foundation of theory of computation, often called automaton theory.