Magic: The Gathering is Turing complete. In a new scientific paper, researchers "present a methodology for embedding an arbitrary Turing machine into a game of Magic such that the first player is guaranteed to win the game if and only if the Turing machine halts." From Ars Technica:

Furthermore, (software engineer Alex Churchill) and his co-authors -- Stella Biderman of the Georgia Institute of Technology and Austin Herrick of the University of Pennsylvania -- have concluded that Magic might be as computationally complex as it's possible for any tabletop game to be. In other words, "This is the first result showing that there exists a real-world game [of Magic] for which determining the winning strategy is non-computable," the authors write...

A universal Turing machine is one capable of running any algorithm, while "Turing completeness" is a term "used to indicate that a system has a particular degree of complexity," said Churchill. "Any Turing-complete system is theoretically able to emulate any other." Being able to determine whether a given problem can be solved in principle is a key task in computer science. If Magic is Turing complete, then there should exist within the game a scenario where it's impossible to determine a winning strategy—equivalent to the famous "halting problem" in computer science.

One way to demonstrate that a system is Turing complete is to create a Turing machine within it, and that's just what Churchill et al. have done with their work

"It’s possible to build a Turing machine within Magic: The Gathering" (Ars Technica)

Read the rest

Synthetic biology researchers at MIT are creating simple analog computers in living cells, complete with fluorescent "displays." Rahul Sarpeshkar and Timothy K. Lu engineered genetic circuits in E. coli so that the bacteria glows with a brightness determined by the amount of certain chemicals surrounding it. From Science News:

By making bacteria glow more or less brightly depending on the number of different chemicals around, the new circuit can compute answers to math problems, Lu’s team reports May 15 in Nature. To add 1 plus 1, for example, the circuit would detect two chemicals and crank up the bacteria’s glow to “2.”

"Analog circuits boost power in living computers" (Science News)

"Cell-Based Computing Goes Analog" (The Scientist)

"Synthetic analog computation in living cells" (Nature) Read the rest

Lazcraft has completed his continued work on his Minecraft CPU project (not to be confused with theInternetFTW's remarkable 8-bit Minecraft computer project). He now has a full, working 8-bit computer made of Minecraft blocks and other gubbins, "with 8 bytes of RAM, an output register, a code-loader and the ability to branch conditionally and unconditionally."

You can't see the code loader as it's on the other side and is shorter than everything else. The clock is the shorter thing at the bottom right of screen. ALU on the left, memory at the top right, and the rest is registers for the accumulator, program counter, code and addresses.

This is the list of op codes:

0 NOT 1 - memory 2 + memory 3 OR memory 4 WRITE memory 5 BRANCH if Accumulator = 0 6 AND memory 7 LOAD memory 8 NOT 9 - constant 10 + constant 11 OR constant 12 WRITE out 13 BRANCH unconditionally 14 AND constant 15 LOAD constant

Working CPU with RAM, branching, etc... (video added)

(Thanks, Fipi Lele!)