cellular_automata/finding_all_reversible_rules.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "7c039a4a",
   "metadata": {},
   "source": [
    "## Finding all reversible rules\n",
    "\n",
    "In this Notebook we experimentally find all [Elementary Cellular Automata](https://en.wikipedia.org/wiki/Elementary_cellular_automaton) rules which are reversible. We call rule reversible if it always transforms two different states in two different states.\n",
    "\n",
    "We use brute force approach to find all reversible rules. For this we check all 256 rules and 2 border conditions (fixed and periodic). For every of them we consider all possible $2^N$ initial classical states (encoded as integers from 0 to $2^N-1$), and for every of them consider $f(s)$ - encoded state to which rule takes state $s$. Then we check if sequence $0, 1, \\dots, d(2^N-1)$ is a permutation. \n",
    "\n",
    "We repeat this for N in range $[4, 20]$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "c404ff4c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "BorderCondition.FIXED\n",
      "Rule 51 is reversible when n=[4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]\n",
      "Rule 60 is reversible when n=[4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]\n",
      "Rule 90 is reversible when n=[4, 6, 8, 10, 12, 14, 16, 18, 20]\n",
      "Rule 102 is reversible when n=[4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]\n",
      "Rule 105 is reversible when n=[4, 6, 7, 9, 10, 12, 13, 15, 16, 18, 19]\n",
      "Rule 150 is reversible when n=[4, 6, 7, 9, 10, 12, 13, 15, 16, 18, 19]\n",
      "Rule 153 is reversible when n=[4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]\n",
      "Rule 165 is reversible when n=[4, 6, 8, 10, 12, 14, 16, 18, 20]\n",
      "Rule 195 is reversible when n=[4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]\n",
      "Rule 204 is reversible when n=[4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]\n",
      "BorderCondition.PERIODIC\n",
      "Rule 15 is reversible when n=[4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]\n",
      "Rule 45 is reversible when n=[5, 7, 9, 11, 13, 15, 17, 19]\n",
      "Rule 51 is reversible when n=[4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]\n",
      "Rule 75 is reversible when n=[5, 7, 9, 11, 13, 15, 17, 19]\n",
      "Rule 85 is reversible when n=[4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]\n",
      "Rule 89 is reversible when n=[5, 7, 9, 11, 13, 15, 17, 19]\n",
      "Rule 101 is reversible when n=[5, 7, 9, 11, 13, 15, 17, 19]\n",
      "Rule 105 is reversible when n=[4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20]\n",
      "Rule 150 is reversible when n=[4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20]\n",
      "Rule 154 is reversible when n=[5, 7, 9, 11, 13, 15, 17, 19]\n",
      "Rule 166 is reversible when n=[5, 7, 9, 11, 13, 15, 17, 19]\n",
      "Rule 170 is reversible when n=[4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]\n",
      "Rule 180 is reversible when n=[5, 7, 9, 11, 13, 15, 17, 19]\n",
      "Rule 204 is reversible when n=[4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]\n",
      "Rule 210 is reversible when n=[5, 7, 9, 11, 13, 15, 17, 19]\n",
      "Rule 240 is reversible when n=[4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]\n"
     ]
    }
   ],
   "source": [
    "from quantum_eca import BorderCondition, ECA\n",
    "\n",
    "def is_permutation(p):\n",
    "    return len(set(p))==len(p)\n",
    "\n",
    "for bc in BorderCondition:\n",
    "    print(bc)\n",
    "    for rule in range(256):\n",
    "        good_ns = []\n",
    "        for n in range(4, 21):\n",
    "            ca = ECA(rule, bc)\n",
    "            p = ca.get_explicit_state_transitions(n)\n",
    "            if is_permutation(p):\n",
    "                good_ns.append(n) \n",
    "        if len(good_ns) > 0:\n",
    "            print(\"Rule %d is reversible when n=%s\" % (rule, good_ns))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "19cc782e",
   "metadata": {},
   "source": [
    "So, there are 22 rules which are reversible for at least some values of $N > 3$:    \n",
    "    \n",
    "* Rules 51 and 204 - reversible always.\n",
    "* Rules 15, 85, 170, 240 - reversible for all $N$ at periodic border conditions.\n",
    "* Rules 45,75,89,101,154,166,180,210 - reversible for odd $N$ at periodic border consitions.\n",
    "* Rules 105 and 150 - reversible at periodic border conditions if $N \\not \\equiv 0 (mod 3)$ and at fixed border conditions if $N \\not \\equiv 2 (mod 3)$.\n",
    "* Rules 60, 102, 153, 195 - reversible for all $N$ at fixed border consitions.\n",
    "* Rules 90, 165 - reversible for even $N$ at fixed border conditions.\n",
    "\n",
    "All other rules are not reversible for N >= 3."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}