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. 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=11 -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 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 some 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


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/01/2025 17:17:27 -CEST-)



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


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