O termo “Regra 110” se refere a um esquema de numeração de automatas celulares elementares proposto por Stephen Wolfram. Esses tipos de automatas celulares são definidos por regras simples, mas ainda assim podem apresentar comportamento complexo.
De fato, a Regra 110 apresenta universalidade computacional. Isso foi conjecturado por Stephen Wolfram, e apenas provado por um dos jovens pesquisadores que trabalhavam para Wolfram, Matthew Cook.
Wolfram impediu a publicação dessa prova durante anos, mas ela foi finalmente publicada sob o título de Universality in Elementary Cellular Automata. A demonstração funciona ao simular um sistema cíclico de tags, que por sua vez é capaz de simular uma máquina de Turing.
