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 left corner, the 3+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).
| Current State | A | A | B | B | C | C |
| Bit Read | 0 | 1 | 0 | 1 | 0 | 1 |
| Bit Written | 1 | 0 | 1 | 0 | 1 | 0 |
| Elementary Translation | Right | Left | Left | Right | Right | Right |
| Next State | B | C | A | C | A | Halt |
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):
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/19/2025 08:51:18 -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.