5 ms·

Basic question but what does being Turing complete actually signify? I get the concept but don't know why it matters.

UncleMeat 7y ago
It means telling whether the game is a draw or a win is undecidable. So magic strategy is not computable.
zahrc 7y ago
General and obvious answer: That means something can (theoretically) compute on it’s own, on the highest computing level. Personal importance: something like mgtg and duplo train tracks, which isn’t intended to build a Turing computer, is used to build one, it’s challenging and a creative outlet of tech knowledge. My favorite example is red stone in Minecraft.
mankyd 7y ago
In theory, if you can perform a computation/algorithm on one turing-complete device, you can transform it to run on another. That is to say, anything your desktop computer can do, Magic can do as well (albeit much much _much_ slower).
- vectorEQ 7y ago
  saying anything your computer can do in such a sentence is misleading. computers are far far away from turing machines these days. they can do much more. for example, good luck making a socket connection on Magic the gathering. even if you can compute everything you need with it, you will never succeed to connect...
  - mankyd 7y ago
    That's a statement about the practical engineering involved, yes. However, saying a computer is "Turing complete" is not misleading. It is purely a statement of its mathematical properties. If sockets were given absurd timeouts and/or you could run MtG at much higher speeds, (and it was given a medium through which it could communicate), it would have no problem making a socket connection. It is only the practicality of the matter that becomes a barrier.
  - arbitrage 7y ago
    You're missing the point.
- magicalhippo 7y ago
  To be more accurate: anything your desktop computer can compute, Magic can compute (disregarding resource constraints).
- thatoneuser 7y ago
  Hm so the mechanics within the game provide all the logical basis that a cpu requires?
  - mankyd 7y ago
    Setup the correct way, yes.
calf 7y ago
Technically it means if you're trying to write an algorithm to play Magic the same algorithm could translated and applied to solving the halting problem (i.e. a reduction of Halt to Magic exists). So your task is that difficult. Thus the theory says it is a logical contradiction for any algorithm to exist that can solve Magic. In practice, this can be different because we are routinely successful in special cases for example we still have anti virus programs in practice, just no one perfect anti virus program can exist for the same reason.
- hinkley 7y ago
  What happens in Magic when you run out of cards? If the tape isn't infinite then there are lots of algorithms that halt. The halting problem is like the pigeonhole principle. Just because there is no general compression algorithm doesn't mean we don't use compression all day every day. We have solutions for many interesting subsets of the problem domain, and that's good enough. We can also tell if a program will halt in no more than N clock cycles by providing the analysis with a budget. If the budget is exhausted then the program would keep running for an unknown duration longer than the limit. Possibly 1 cycle. For third party code, you could just refuse to run that code at all. There are some useful programs that would get rejected but there are many useful ones that would not. So implementing an "infinite loop detector" as a "really big loop detector" wouldn't be the dumbest thing to try, anymore than implementing video compression is.
  - hannasanarion 7y ago
    In magic, if you run out of cards, you lose, but there are ways to restore your cards so you never run out, so games can continue theoretically forever.
    - thiagoharry 7y ago
      And even if you don't, it's possible to create infinite resources combining a finite number of cards. Like creating infinite tokens, infinite mana. The paper uses an infinite number of creature tokens to represent an infinite tape.

It means telling whether the game is a draw or a win is undecidable. So magic strategy is not computable.

General and obvious answer: That means something can (theoretically) compute on it’s own, on the highest computing level. Personal importance: something like mgtg and duplo train tracks, which isn’t intended to build a Turing computer, is used to build one, it’s challenging and a creative outlet of tech knowledge. My favorite example is red stone in Minecraft.

mankyd 7y ago

In theory, if you can perform a computation/algorithm on one turing-complete device, you can transform it to run on another. That is to say, anything your desktop computer can do, Magic can do as well (albeit much much _much_ slower).

vectorEQ 7y ago
saying anything your computer can do in such a sentence is misleading. computers are far far away from turing machines these days. they can do much more. for example, good luck making a socket connection on Magic the gathering. even if you can compute everything you need with it, you will never succeed to connect...
- mankyd 7y ago
  That's a statement about the practical engineering involved, yes. However, saying a computer is "Turing complete" is not misleading. It is purely a statement of its mathematical properties. If sockets were given absurd timeouts and/or you could run MtG at much higher speeds, (and it was given a medium through which it could communicate), it would have no problem making a socket connection. It is only the practicality of the matter that becomes a barrier.
- arbitrage 7y ago
  You're missing the point.
magicalhippo 7y ago
To be more accurate: anything your desktop computer can compute, Magic can compute (disregarding resource constraints).
thatoneuser 7y ago
Hm so the mechanics within the game provide all the logical basis that a cpu requires?
- mankyd 7y ago
  Setup the correct way, yes.

calf 7y ago

Technically it means if you're trying to write an algorithm to play Magic the same algorithm could translated and applied to solving the halting problem (i.e. a reduction of Halt to Magic exists). So your task is that difficult. Thus the theory says it is a logical contradiction for any algorithm to exist that can solve Magic. In practice, this can be different because we are routinely successful in special cases for example we still have anti virus programs in practice, just no one perfect anti virus program can exist for the same reason.

hinkley 7y ago
What happens in Magic when you run out of cards? If the tape isn't infinite then there are lots of algorithms that halt. The halting problem is like the pigeonhole principle. Just because there is no general compression algorithm doesn't mean we don't use compression all day every day. We have solutions for many interesting subsets of the problem domain, and that's good enough. We can also tell if a program will halt in no more than N clock cycles by providing the analysis with a budget. If the budget is exhausted then the program would keep running for an unknown duration longer than the limit. Possibly 1 cycle. For third party code, you could just refuse to run that code at all. There are some useful programs that would get rejected but there are many useful ones that would not. So implementing an "infinite loop detector" as a "really big loop detector" wouldn't be the dumbest thing to try, anymore than implementing video compression is.
- hannasanarion 7y ago
  In magic, if you run out of cards, you lose, but there are ways to restore your cards so you never run out, so games can continue theoretically forever.
  - thiagoharry 7y ago
    And even if you don't, it's possible to create infinite resources combining a finite number of cards. Like creating infinite tokens, infinite mana. The paper uses an infinite number of creature tokens to represent an infinite tape.