Bio

Emmanuel Gárces Medina is a computer scientist and software developer from the National Autonomous University of Mexico and Autonomous University of Mexico City. He has been interested in pure NKS since he attended the 2006 NKS Summer School. His main concerns are description of simple programs, equivalences and emulation of systems, and computational irreducibility.

Project: Irreducibility for Short Boolean Functions

Computational irreducibility is the inability for computer programs to be computed by reducing the amount of computational resources.

Computational irreducibility occurs even for short programs and comes into play when one tries to shortcut them.

The aim of this work consists of showing how computational irreducibility prevents reduction of simple boolean formulas by imposing constraints on different computer resources like time, space, and size of the primitive operations set.

The basic idea is to start an exploration on the computational universe consisting of all of those graphs that perform boolean function computation. Given a lower bound for a resource such as the size or depth of the graph, one can try to find all minimal formulas that can be computed given those constraints. There is a trade-off between computational resources.

This exhaustive exploration along all possible programs of this kind shows how computational irreducibility holds for very short boolean formulas. One is able to see how reducing time and space for a program compromises the length and number of primitive operations. How fast this happens and what the thresholds are for each constrained resource are also investigated.

Favorite Radius 3/2 Rule

Rule 47025

It’s interesting how two different kinds of behavior emerge in the evolution of this CA from a simple initial condition.