Click to download and possibly see the movie [Cliquez pour télécharger et voir éventuellement le film]

The execution of a very simple program on a Turing Machine [L'exécution d'un programme très simple sur une machine de Turing].




The Turing Machine is a mathematical model of computation.

It is made on one hand of an infinite discrete cell tape and on the other hand of a head that can read and write one tape cell at each time step.

The head contents an "internal state" S (S ∈ {A,B,...}).

Each cell C has a number N (an address...).

For these visualizations, only 2 symbols {0,1} (that recall our binary computers...) are used in order to define the content of each cell.

Let's assume that at time T the head is in state S(T) and is located over the cell C(N). Then S(T) and the symbol B=C(N) are defining: At last there exists a special state "Halt" that means the end of the computation.

On this picture the vertical axis displays the time T (from T=0 -bottom- to T=11 -top-) and each time step uses 2 horizontal lines: On the bottom right corner, the 3+1 color squares display vertically the code used for each possible state (S ∈ {A,B,...} from bottom to top), the higher one -white- being for the "Halt" state (both bold below).

At T=0, the "Current State" is 'A' and the "Bit Read" is 0 (bold below).


Current StateAABBCC
Bit Read010101
Bit Written101010
Elementary TranslationRightLeftLeftRightRightRight
Next StateBCACAHalt



Here are the full steps of the computation (11 time steps): 
                    A0 -> 1LB
                    B0 -> 1RA
                    A1 -> 0RC
                    C0 -> 1LA
                    A0 -> 1LB
                    B1 -> 0LC
                    C0 -> 1LA
                    A0 -> 1LB
                    B0 -> 1RA
                    A1 -> 0RC
                    C1 -> Halt


See some related pictures (including this one):

The execution of a very simple program on a Turing Machine The execution of a very simple program on a Turing Machine The execution of a very simple program on a Turing Machine
The execution of a very simple program on a Turing Machine The execution of a very simple program on a Turing Machine The execution of a very simple program on a Turing Machine

See the related animations (possibly including this one):

The execution of a very simple program on a Turing Machine The execution of a very simple program on a Turing Machine The execution of a very simple program on a Turing Machine
The execution of a very simple program on a Turing Machine The execution of a very simple program on a Turing Machine The execution of a very simple program on a Turing Machine

Depending on the used navigator, it could be possible to display these animations step by step. After starting the movie, ask for a PAUSE. Then put the mouse cursor on the white video progression bar (bottom of the picture). At last using the two arrow keyboard keys "<--" and "-->" it is possible to travel backward (T=T-1) and forward (T=T+1) in time.


More information on this subject is available in the april 2025 issue (#570) of PLS (Pour La Science) with the Jean-Paul Delahaye's paper Le "cinquième castor affairé": une victoire collective.


(CMAP28 WWW site: this page was created on 04/17/2025 and last updated on 05/20/2025 11:42:32 -CEST-)



[See all related pictures (including this one) [Voir toutes les images associées (incluant celle-ci)]]

[Please visit the related NumberTheory picture gallery [Visitez la galerie d'images NumberTheory associée]]

[Go back to AVirtualMachineForExploringSpaceTimeAndBeyond [Retour à AVirtualMachineForExploringSpaceTimeAndBeyond]]

[The Y2K Bug [Le bug de l'an 2000]]

[Site Map, Help and Search [Plan du Site, Aide et Recherche]]
[Mail [Courrier]]
[About Pictures and Animations [A Propos des Images et des Animations]]


Copyright © Jean-François COLONNA, 2025-2025.
Copyright © CMAP (Centre de Mathématiques APpliquées) UMR CNRS 7641 / École polytechnique, Institut Polytechnique de Paris, 2025-2025.