Mark Gritter (markgritter) wrote,
Mark Gritter

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
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.