Une fonction est calculable à condition que, pour un argument donné, il existe une procédure algorithmique qui donne la valeur de la fonction pour cet argument. Une fonction est récursivement calculable quand il existe un ensemble fini d'opération pouvant s'appliquer à la première donnée, puis au résultat de cette opération, et ainsi de suite jusqu'à obtention du résultat.

Sur la base de ces connaissances, Turing démontra qu'une machine universelle (disposant d'une mémoire infinie) peut calculer n'importe quelle fonction récursivement calculable (= exprimable à l'aide de règles formelle donc sous la forme d'un algorithme) si cette machine est pourvue du programme adéquat. Il démontra également l'équivalence des machines à état discret qui disposent d'une mémoire infinie : ainsi, la machine universelle de Turing peut effectuer tout ce que peut effectuer le plus puissant des ordinateur existant ou à venir. Il décrivit sa machine simplement avec une unité de calcul se déplaçant sur une bande sur laquelle sont stockés les informations et le programme, que l'unité de calcul peut à loisir lire, et y déposer des informations temporaires. Cette description abstraite est proche du principe de nos ordinateurs.

Toutes les informations en mémoire sont codées en binaire (à l'origine, Turing pensait prendre un système de mémoire plus complexe, mais tout symbole peut de toute façon être décomposé en binaire. Cette machine rappelle tout à fait nos ordinateurs, qui sont en fait des machines universelles finies (limitées). L'ordinateur seul est un paquet de matière qui n'évolue pas, qui ne fait rien. Mais si on le soumet à un programme simulant un processus, alors il se conduira comme le processus, c'est ce qui fait de lui un outil capable d'émuler (ça veut a peu près dire simuler ou reproduire) n'importe quelle autre machine ou processus. Ce fait permettra à la Vie Artificielle de réaliser des modèles abstraits de ce que nous penser être la vie.

Source : Diverses dont J-C. Heudin (1994) La Vie Artificielle