2018-08-19 Snapshot

Advertisements

John Conway (Group Theory & “Game of Life”) Best Wishes

Princeton Emeritus mathematician Professor John Conway sends his best wishes

Professor Conway created the Game of Life cellular automata, which is Turing-Complete (similar to Ethereum). 

http://web.stanford.edu/~cdebs/GameOfLife/

cellular automata, as they appear in the Game of Life, have the same computational capacity as Turing machines. The Church-Turing thesis that states:

“No method of computation carried out by a mechanical process can be more powerful than a Turing machine.”

Therefore, as the Game of Life is Turing complete, it is one of the most powerful models of computation. In other words, no mechanical form of computation can solve a problem that a Turing machine or cellular automata cannot solve, given sufficient time and space. The following reasons lead researchers to determine the Game of Life has all the computational capability of Turing Machines, meaning it is Turing complete:

https://plato.stanford.edu/entries/cellular-automata/

CA are computational systems: they can compute functions and solve algorithmic problems. Despite functioning in a different way from traditional, Turing machine-like devices, CA with suitable rules can emulate a universal Turing machine (see entry), and therefore compute, given Turing’s thesis (see entry on Church-Turing thesis), anything computable.

unlike Turing machines and von Neumann-architecture conventional computers, CA compute in a parallel, distributed fashion.

Using CA for Cryptography

Cellular automata yield a surprisingly diverse range of practical applications. We focus here on one particular example of a real-life application of cellular automata – the design of a public-key cryptosystem.

A public-key cryptosystem is a cryptographic protocol that relies on two keys – an enciphering key E, which is made public, and a deciphering key D, which is kept private. Such a system should contain two important properties:

1) Security. For attackers who have no access to the private key, the protocol should be so designed such that it would take a prohibitively large amount of time to recover the plain text from the cipher text.

2) Signature. The receiver should be able to tell who the sender is. In other words, if person A, say Alice, wants to send a message, she should be able to sign her message in a way that nobody but she could.

Public-Key Crypotography.

In the system, each piece of plain text consists of binary digit blocks of a certain length, say N. In turn, each set of, for example, k bits in the block can be viewed as an element of some ground set S. For instance, we can have a cryptosystem where each block contained 5 bits and each bit takes a value in a field of 2 elements.

Suppose now each block contains N bits and represents m elements of S. To satisfy the security requirement, we require an invertible function which maps Sm to Sm that satisfies the following conditions:

a) Easy to compute (for enciphering)

b) Hard to obtain its inverse without certain key pieces of information which only the receiver has access to (deterring would-be attackers)

The complexity of cellular automata lends itself nicely to applications in cryptography. In particular, cellular automaton rules that are invertible are prime candidates for the invertible function we require to construct a public-key cryptosystem. To succinctly represent the rules whilst preserving a large neighborhood-size, we can associate the ground set S with a mathematical structure such as a field or a ring. This way, addition and multiplication are well defined on S, and we can thus represent cellular automaton rules as polynomial functions.

Here is a sketch of how a cellular automaton cryptosystem might work. Let the ground set be a field. The enciphering key, E, is a composition of inhomogeneous and time-varying linear invertible rules which is made public (the observant reader might note that the fact that the rules are inhomogeneous and time-varying distinguishes the resulting cellular automaton from elementary cellular automata). The deciphering key, D, is the set of individual rules in the composite enciphering function.

The crucial factor that enables such a cellular automaton cryptosystem to work is the fact that it is extremely computationally expensive to unravel the original state from the cipher state without prior knowledge of the individual rules used in the composite enciphering function. This guarantees the security of the system.

Signing a message in our cryptosystem works in exactly the same way as signing a message in the RSA cryptosystem. All the sender has to do is to apply the secret decryption key D to her name and then include that coded signature at the end of her message. This way, when the receiver receives the message, he can simply use the public key E to decipher the coded signature and see if the name matches the presumed sender.

Glider

Gosper Gliding Gun

Pulsar

Puffer

Game of Life on the Surface of Trefoil Knot

Red glider on the square lattice with periodic boundary conditions.

a 48-step oscillator along with a 2-step oscillator and a 4-step oscillator from a 2-D hexagonal Game of Life (rule H:B2/S34)