.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/vm/foundations/plot_02_halting_problem.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_02_halting_problem.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_02_halting_problem.py:


The halting problem: why every call needs a budget (Turing 1936)
================================================================

Turing defined computation with a machine that reads and writes a tape, and
proved that no program can decide, for every machine and input, whether it
eventually halts. Running a machine longer never settles the question: a
machine that has not halted yet may halt later, or never. A blockchain that
lets anyone submit programs therefore cannot check in advance that they
terminate. It bounds them instead, with a step budget.

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

All 20,736 two-state Turing machines are run from a blank tape with growing
step budgets. Those that halt do so within six steps; some are caught
repeating a configuration, which proves they loop. But a large group stays
*unknown* at every budget: no finite budget sorts them.

The history behind this experiment: :doc:`/history/vm_breakthroughs`.

.. GENERATED FROM PYTHON SOURCE LINES 24-26

Classify every two-state machine
--------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 26-43

.. code-block:: Python

    import matplotlib.pyplot as plt

    import blockchainkit as bk

    machines = list(bk.vm.enumerate_machines(2))
    budgets = [2, 4, 6, 10, 20, 50]
    counts = {outcome: [] for outcome in ("halted", "looping", "unknown")}
    for budget in budgets:
        tally = {outcome: 0 for outcome in counts}
        for rules in machines:
            tally[bk.vm.run_turing_machine(rules, max_steps=budget).outcome] += 1
        for outcome in counts:
            counts[outcome].append(tally[outcome])
    print(counts)
    assert counts["halted"][2] == counts["halted"][-1]  # Nothing halts after step 6...
    assert counts["unknown"][-1] > 0  # ...yet many machines are still undecided.





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

 .. code-block:: none

    {'halted': [9216, 9728, 9784, 9784, 9784, 9784], 'looping': [0, 336, 418, 430, 430, 430], 'unknown': [11520, 10672, 10534, 10522, 10522, 10522]}




.. GENERATED FROM PYTHON SOURCE LINES 44-47

A machine the budget cannot classify
------------------------------------
This one writes 1s rightward forever without repeating a configuration.

.. GENERATED FROM PYTHON SOURCE LINES 47-63

.. code-block:: Python

    runner = {
        ("A", 0): (1, 1, "A"),
        ("A", 1): (1, 1, "A"),
        ("B", 0): (0, 1, "A"),
        ("B", 1): (0, 1, "A"),
    }
    for budget in (10, 100, 1000):
        print(budget, bk.vm.run_turing_machine(runner, max_steps=budget).outcome)

    fig, ax = plt.subplots(figsize=(7, 4))
    for outcome, values in counts.items():
        ax.plot(budgets, values, "o-", label=outcome)
    ax.set(xlabel="step budget", ylabel="machines", title="20,736 two-state machines")
    ax.legend()
    fig.tight_layout()




.. image-sg:: /api/gallery/vm/foundations/images/sphx_glr_plot_02_halting_problem_001.png
   :alt: 20,736 two-state machines
   :srcset: /api/gallery/vm/foundations/images/sphx_glr_plot_02_halting_problem_001.png
   :class: sphx-glr-single-img


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

 .. code-block:: none

    10 unknown
    100 unknown
    1000 unknown




.. GENERATED FROM PYTHON SOURCE LINES 64-69

Exercise
--------
Write a cheap test that proves the ``runner`` machine never halts: what
property of its state and the blank tape ahead makes the future repeat?
Why can no such collection of tests cover every machine?


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

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


.. _sphx_glr_download_api_gallery_vm_foundations_plot_02_halting_problem.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_02_halting_problem.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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