Mark Gritter (markgritter) wrote,
Mark Gritter
markgritter

At least one CCG is Turing-Complete

How to implement a Turing Machine with M:tG cards. This is a pretty impressive reduction.

It's not an extremely surprising result. Once you have pattern-matching and some mechanism for unbounded state, you're pretty close to universal computation. In fact, one of the themes I picked up from reading "Games of No Chance" is how hard it is to prove that many games are actually in PSPACE or EXPTIME instead of something worse (EXPSPACE or uncomputable.)

But a very impressive engineering effort; his "widgets" are quite clever.
Tags: complexity, games, geek, theory
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 0 comments