5
$\begingroup$

This is a bit of a weird question, but I was wondering earlier if QR codes are Turing-complete when interpreted as initial states for Conway's Game of Life.

My intuition is "yes", as there are infinitely many QR codes (they just get bigger as you add more information), and the Game of Life itself is Turing-complete. However, it's not inconceivable that the restrictions imposed by the QR code format mean that no QR codes are Turing-complete.

Another way to phrase the question would be "can all Turing machines be encoded as a string which, when converted into a QR code and used as the initial state for Conway's Game of Life, produces equivalent output to the original Turing machine"

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ Perhaps a better formulation of the question is: "Is Conway's Game of Life still Turing complete if the initial configurations of cells must be valid QR codes?" $\endgroup$
    – Vor
    Commented Oct 5, 2013 at 0:30
  • 2
    $\begingroup$ First of all there should be a standard to build a QR code of arbitrary size (to represent an arbitrary large input); but looking at Wikipedia the max supported size is 172x172 (storage: 1852 chars, version 40). $\endgroup$
    – Vor
    Commented Oct 5, 2013 at 0:42

1 Answer 1

Reset to default
8
$\begingroup$

QR codes are limited to a maximum size 172x172, which is not nearly large enough to built a Turing complete state machine in.
A current implementation of a Turing machine in GoL takes 1714 by 1647 cells. It is undoubtedly sub optimal, but compressing it to 172x172 seems a stretch.

However let's assume the QR code is a little larger than 1714 square.
All of the elements in the listed Turing machine are constructable using gliders and besides much larger universal Turing machines have been constructed that are fully replicable. Given a large enough QR code most of the key space is arbitrary.
There are some fixed elements that would have to be destroyed.
There are no known patterns that cannot be destroyed by a well timed glider salvo and certainly the fixed patterns in the QR codes have been explored.

Given the amount of redundant parent patterns that reduce to the same child pattern it is quite likely it is possible.
Furthermore the error correction only has a local effect, so changing a pattern in the top corner does not affect data at the bottom.

If you change the question to:

If I stamp my GoL grid with many QR codes, can I built a turing machine?

Then the answer is yes, because its trivial to collapse a QR code to a glider and a Turing machine can be constructed using gliders and only gliders.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.