.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/vm/foundations/plot_04_busy_beaver.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

    .. note::
        :class: sphx-glr-download-link-note

        :ref:`Go to the end <sphx_glr_download_api_gallery_vm_foundations_plot_04_busy_beaver.py>`
        to download the full example code or to run this example in your browser via JupyterLite.

.. rst-class:: sphx-glr-example-title

.. _sphx_glr_api_gallery_vm_foundations_plot_04_busy_beaver.py:


The busy beaver: the longest a small machine can run (Radó 1962)
================================================================

Radó asked: among all Turing machines with n states that halt when started
on a blank tape, which runs longest? Call that number of steps S(n). For
n = 2, a search over every machine gives S(2) = 6. But S grows faster than
any computable function: S(3) = 21, S(4) = 107, and S(5) = 47,176,870,
proved only in 2024. Knowing S(n) would solve the halting problem for
n-state machines, so no algorithm computes it.

What to look for
----------------

The exhaustive search finds the 2-state champion, which halts after 6 steps
with 4 ones on the tape. Its step count is reached long before the search's
budget, but proving that the remaining "unknown" machines never halt is
exactly what the search cannot do.

The history behind this experiment: :doc:`/history/vm_breakthroughs`.
See :doc:`/exercises/vm` for a worked solution to the exercise.

.. GENERATED FROM PYTHON SOURCE LINES 25-27

Search all 20,736 two-state machines
------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 27-37

.. code-block:: Python

    import matplotlib.pyplot as plt
    import numpy as np

    import blockchainkit as bk

    result = bk.vm.busy_beaver(2, max_steps=50)
    print(result.steps, "steps,", result.ones, "ones:", result.machine)
    print(result.counts)
    assert (result.steps, result.ones) == (6, 4)





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    6 steps, 4 ones: {('A', 0): (1, -1, 'B'), ('A', 1): (1, 1, 'B'), ('B', 0): (1, 1, 'A'), ('B', 1): (1, -1, 'H')}
    {'halted': 9784, 'looping': 430, 'unknown': 10522}




.. GENERATED FROM PYTHON SOURCE LINES 38-40

How long halting machines run
-----------------------------

.. GENERATED FROM PYTHON SOURCE LINES 40-57

.. code-block:: Python

    lengths = [
        run.steps
        for run in (
            bk.vm.run_turing_machine(rules, max_steps=50) for rules in bk.vm.enumerate_machines(2)
        )
        if run.outcome == "halted"
    ]
    assert max(lengths) == 6

    fig, (left, right) = plt.subplots(1, 2, figsize=(10, 4))
    left.hist(lengths, bins=np.arange(0.5, 7.5), color="#7c3aed", edgecolor="white")
    left.set(xlabel="steps to halt", ylabel="machines", title="Halting 2-state machines")
    known = {1: 1, 2: 6, 3: 21, 4: 107, 5: 47_176_870}
    right.semilogy(list(known), list(known.values()), "o-")
    right.set(xlabel="states n", ylabel="S(n)", title="Busy beaver values (known)")
    fig.tight_layout()




.. image-sg:: /api/gallery/vm/foundations/images/sphx_glr_plot_04_busy_beaver_001.png
   :alt: Halting 2-state machines, Busy beaver values (known)
   :srcset: /api/gallery/vm/foundations/images/sphx_glr_plot_04_busy_beaver_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 58-64

Exercise
--------
``bk.vm.run_turing_machine`` reproduces the 3-state champion's 21 steps
from its rule table (see the history page). Why does a gas limit of 22
steps let you *run* it but not *know* that no other 3-state machine runs
longer?


.. rst-class:: sphx-glr-timing

   **Total running time of the script:** (0 minutes 2.574 seconds)


.. _sphx_glr_download_api_gallery_vm_foundations_plot_04_busy_beaver.py:

.. only:: html

  .. container:: sphx-glr-footer sphx-glr-footer-example

    .. container:: lite-badge

      .. image:: images/jupyterlite_badge_logo.svg
        :target: ../../../../lite/lab/index.html?path=api/gallery/vm/foundations/plot_04_busy_beaver.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

    .. container:: sphx-glr-download sphx-glr-download-jupyter

      :download:`Download Jupyter notebook: plot_04_busy_beaver.ipynb <plot_04_busy_beaver.ipynb>`

    .. container:: sphx-glr-download sphx-glr-download-python

      :download:`Download Python source code: plot_04_busy_beaver.py <plot_04_busy_beaver.py>`

    .. container:: sphx-glr-download sphx-glr-download-zip

      :download:`Download zipped: plot_04_busy_beaver.zip <plot_04_busy_beaver.zip>`


.. only:: html

 .. rst-class:: sphx-glr-signature

    `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_