## Introduction

A Genetic Algorithm is broadly considered as a “black box” of software; it literally emulates the way Natural Evolution has used billions of years to evolve. Starting from a Prokaryote, given the time and the proper evolutionary conditions, Natural Evolution managed to produce Eukaryotes through DNA replication, Cell Division, Random Mutations and trillion replications and recombinations [1], [2]. The goal of such an initiative would be no other than reach what we now describe as “Artificial Intelligence”.

There is a distinct difference between Genetic Algorithms and Classical Algorithms in two key points. Classical Algorithms generate only one instance that has a specific goal of solving a problem by approaching the optimal solution, while using deterministic computation. On the other hand, Genetic Algorithms create a population of instances with each iteration. It is the swarm intelligence of those instances that approach the solution of the problem on the best possible way. Genetic Algorithms are not using deterministic computation, but a computation based on Random Number Generators [3]. One of the most common implementation of Genetic Algorithms is the Cellular Automaton.

The concept of a Cellular Automaton (plural: Cellular Automata) was first introduced by John von Neumann in the Hixon Symposium in 1951 [4]. It was described as a discrete model that consists of a simple two-state, one dimensional grid of cells that can be either on or off. Later, in the 1970s a two-state, two-dimensional cellular automaton named “Game of Life” by John Conway, became widely known [5] but it wasn’t until the 1980s with the work of Stephen Wolfram when a systematic study of two-state, one-dimension of Cellular Automata was done [6], presenting the implementation of a Cellular Automaton based on specific set of rules. Wolfram named those “Elementary Cellular Automata” and his research assistant Mathew Cook showed that one of these rules is Turing-Complete. Their work has been published in 2002 in the bestselling book “A New Kind of Science” [7].

In computability theory [8], a Cellular Automaton can be Turing Complete, if it can be used to simulate any single-taped Turing Machine. The term was named after the Computer Scientist and Mathematician Alan Turing. A typical example of such an implementation is the Lambda Calculus which was introduced in 1930 by Alonzo Church [9].

As an extension to the above notion, if such an Automaton is formed, then a swarm of Cellular Automata of similar origin could possibly form what is described as a Church-Turing thesis [10]. Furthermore, above a certain point of computational evolution, they could form what is described by the Church–Turing–Deutsch principle. The principle states that a Universal Computing Device can simulate every physical process [11], [12]. In this paper we present that it is theoretically possible for a Turing-Complete algorithm, like a Cellular Automaton based on rule 110, to be implemented on an Unbounded Single Taped Turing Medium such as a Blockchain.

[1] Alberts B, Johnson A, Lewis J, Raff M, Roberts K, Walter P (2002). Molecular Biology of the Cell. Garland Science. ISBN 0-8153-3218-1. Chapter 5: DNA Replication Mechanisms

[2] Article: “What is DNA Replication?". yourgenome.org. Welcome Genome Campus. Retrieved 24 February 2017.

[3] Article: “Genetic Algorithms”, Mathworks, 2017.

[4] John von Neumann, "The general and logical theory of automata," in L.A. Jeffress, ed., Cerebral Mechanisms in Behavior – The Hixon Symposium, John Wiley & Sons, New York, 1951, pp. 1–31.

[5] Gardner, Martin (1970). "Mathematical Games: The fantastic combinations of John Conway's new solitaire game "life"". Scientific American (223): 120–123.

[6] Wolfram, Stephen (1983). "Statistical Mechanics of Cellular Automata". Reviews of Modern Physics. 55 (3): 601–644.

[7] Wolfram, Stephen (2002). “A New Kind of Science”. ISBN 1-57955-008-8

[8]Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Part Two: Computability Theory, Chapters 3–6, pp. 123–222.

[9] Church, A. (1932). "A set of postulates for the foundation of logic". Annals of Mathematics. Series 2. 33 (2): 346–366. JSTOR 1968337. doi:10.2307/1968337.

[10]Rabin, Michael O. (June 2012). Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View.

[11]Nielsen, Michael. "Interesting problems: The Church–Turing–Deutsch Principle". Retrieved 10 May 2014.

[12]Deutsch, D. (1985). "Quantum theory, the Church–Turing principle and the universal quantum computer" (PDF). Proceedings of the Royal Society. London. 400: 97–117. doi:10.1098/rspa.1985.0070.