Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Kirian]

Via BoingBoing, via Slashdot:

http://www.toothycat.net/~hologram/Turing/index.html

Anyone want to set this up as a solo challenge for Dominion?

[Titandrake]

Unfortunately, Dominion has finite space, and can't rely on triggered effects to compute everything by itself.

Maybe with Graverobber + some play rules you can do something? The computation doesn't have to happen over the course of 1 turn either, but there's a limit on how many actions that can be played each turn. But what if you assume infinite supply piles...

[/semi-serious-comment]

[jotheonah]

side note: his Magic Card generator is highly hilarious.

[ConMan]

One of the things that the Magic Turing Machine makes use of is the ability to generate effectively infinite tokens that you can then manipulate. With Dominion, while some of the tokens can be generated infinitely, they tend to only accumulate and are hard to manipulate. To have a chance at Turing Completeness you'd probably need something that behaved a little like Trade Route tokens, but which you could move back and forth between at least two places rather than the current one-way movement it has. Then the number of coins generated by the tokens could be used as a state measure somehow, which would then feed back into the game.

[theory]

For CS people: why do people care about Turing-completeness?  Can you explain the importance of the concept to me?  Because I only ever hear about systems that are Turing-complete, and never about something that is not Turing-complete.

[DStu]

For CS people: why do people care about Turing-completeness?  Can you explain the importance of the concept to me?  Because I only ever hear about systems that are Turing-complete, and never about something that is not Turing-complete.

IANACS, but as I understand it. When something is Turing complete, it's powerfull enough to compute anything that a turing machine can compute. On the other hand, there is the Church-Turing thesis which states that every function you can compute "somehow", you can compute with a Turing machine.
Which is of course not proveable, but has hold until now (as far as I know)

[jotheonah]

isn't it just (and I'm not a CS person) a landmark of complexity?

[Cuzz]

Reminds me of this paper:

http://arxiv.org/abs/1203.1895

[Kirian]

Essentially, a Turing-complete machine is equivalent to a Turing machine, and a Turing machine can run any program that requires no user input other than the initial state and the program itself.  For instance, one could run a Dominion simulator on a Turing machine, as once the program is in motion, no further input is required.

Actually programming a Turing machine is incredibly difficult for all but the most simple tasks.  See for instance:  http://www.google.com/doodles/alan-turings-100th-birthday

[ConMan]

A Turing machine takes a single integer as input, and calculates the result of an arithmetic pseudo-function on that input. Which doesn't sound particularly exciting, but that roughly defines "problems we can solve with a computer, given sufficient storage space and running time". So anything that *isn't* Turing complete will be unable to solve some of these problems, while a theoretical machine that was *stronger* than Turing complete could solve problems that no computer today can, which would have some amazing implications in the field of Logic.

One of the biggest aspects of computer science and Turing machines is the Halting Problem - every Turing machine takes an input, and then either halts running to provide an output, or never stops running. Is there a computable algorithm with which, for any given Turing machine, we could determine beforehand whether a particular input will cause it to halt or run forever? The answer is no, because we can encode such an algorithm in a Turing machine itself, and then we can feed that machine a *copy* of itself, but rigged to provide a paradoxical inability to determine its own halting status (vast oversimplification, read up on it elsewhere if you want to learn the gory details).

So what? Well, first it generates a class of uncomputable numbers - numbers whose derivation is such that they can never be computed. Secondly, if we assume the Church-Turing Thesis, we can use a similar argument to prove Godel's First Incompleteness Theorem, which states that in a mathematical system sophisticated enough to contain all of arithmetic, there are statements such that either (a) they are true but you can never prove them to be so in that system, or (b) they are true, but so is their negative, and hence the system is broken and you can't actually do anything useful with it.

The thing is, if we had a "Super-Turing-Complete" machine, particularly one capable of performing an infinite number of steps in finite time, we could essentially prove a whole bunch of things that we suspect are true but are currently unable to prove.

Also, it's cool to prove that something's Turing Complete because it means you can use it to do arithmetic (which includes things like proving something involving induction), usually against all expectations.

[Donald X.]

A Turing machine made using the Life cellular automaton, incoming.

[DStu]

Actually programming a Turing machine is incredibly difficult for all but the most simple tasks.  See for instance:  http://www.google.com/doodles/alan-turings-100th-birthday

I don't think this is true.  There a tons of compilers C->Turing machine, so just write in C (or your favourite language an compile to C) and compile to Turing machine.

Edit: Forgot what I wanted to post in the first place:
http://vimeo.com/44202270#