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. Each cell C has a number N. The head content an "internal state" S (S ∈ {A,B,...}). For this visualization, only 2 symbols {0,1} 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 S(T+1), the new content of C(N) (that can be unchanged) and at last the elementary translation of the head on the Right (N --> N+1) or on the Left (N --> N-1). 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=47176870 -top-) and each time step uses 2 horizontal lines: the first one for the current tape content (dark grey: C(N)=0, light grey: C(N)=1) and the second one for the state S(T). On the bottom left corner, the 5+1 color squares display the code used for each possible state (S ∈ {A,B,...} from left to right), the right 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).


cwCurrent StateAABBCCDDEE
Bit Read0101010101
Bit Read1111101100
Elementary TranslationRightLeftRightRightRightLeftLeftLeftRightLeft
Next StateBCCBDEADHaltA



Here are the first steps of the computation (47176870 time steps): 
                    A0 --> 1LB
                    B0 --> 1LC
                    C0 --> 1LD
                    D0 --> 1RA
                    A1 --> 1RC
                    C1 --> 0RE
                    E1 --> 0RA
                    A0 --> 1LB
                    B0 --> 1LC
                    C0 --> 1LD
                    D1 --> 1RD
                    D1 --> 1RD
                    D1 --> 1RD
                    D1 --> 1RD
                    D0 --> 1RA
                    A0 --> 1LB
                    B1 --> 1LB
                    B1 --> 1LB
                    B1 --> 1LB
                    B1 --> 1LB
                    B1 --> 1LB
                    B1 --> 1LB
                    B0 --> 1LC
                    C0 --> 1LD
                    D0 --> 1RA
                    A1 --> 1RC
                    C1 --> 0RE
                    E1 --> 0RA
                    A1 --> 1RC
                    C1 --> 0RE
                    E1 --> 0RA
                    A1 --> 1RC
                    C1 --> 0RE
                    E1 --> 0RA
                    A0 --> 1LB
                    B0 --> 1LC
                    C0 --> 1LD
                    D1 --> 1RD
                    D1 --> 1RD
                    D1 --> 1RD
                    D1 --> 1RD
                    D0 --> 1RA
                    A0 --> 1LB
                    B1 --> 1LB
                    B1 --> 1LB
                    B1 --> 1LB
                    B1 --> 1LB
                    B1 --> 1LB
                    B0 --> 1LC
                    C0 --> 1LD
                    D1 --> 1RD
                    D1 --> 1RD
                    D1 --> 1RD
                    D1 --> 1RD
                    D1 --> 1RD
                    D1 --> 1RD
                    D1 --> 1RD
                    D1 --> 1RD
                    D1 --> 1RD
                    D0 --> 1RA
                    A0 --> 1LB
                    B1 --> 1LB
                    B1 --> 1LB
                    (...)


See some related pictures (including this one):




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 04/18/2025 09:25:45 -CEST-)



[See the generator of this picture [Voir le générateur de cette image]]

[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.