Machine à accès aléatoire - Random-access machine

En informatique , la machine à accès aléatoire ( RAM ) est une machine abstraite de la classe générale des machines à registres . La RAM est très similaire à la machine de comptage mais avec la capacité supplémentaire d'« adressage indirect » de ses registres. Comme la machine de comptage, la RAM a ses instructions dans la partie à états finis de la machine ( l'architecture dite de Harvard ).

L'équivalent de la RAM de la machine de Turing universelle  – avec son programme dans les registres ainsi que ses données – est appelé la machine à programme stocké à accès aléatoire ou RASP. C'est un exemple de l' architecture dite de von Neumann et est la plus proche de la notion commune d' ordinateur .

Avec les modèles de machine de Turing et de contre-machine , les modèles RAM et RASP sont utilisés pour l' analyse de la complexité de calcul . Van Emde Boas (1990) appelle ces trois modèles plus la machine à pointeurs « machines séquentielles », pour les distinguer des modèles « machines parallèles à accès aléatoire ».

Présentation du modèle

Le concept d'une machine à accès aléatoire (RAM) commence par le modèle le plus simple de tous, le modèle dit de machine de compteur . Deux ajouts l'éloignent cependant de la machine de comptoir. Le premier améliore la machine avec la commodité de l'adressage indirect ; le second déplace le modèle vers l' ordinateur plus conventionnel à base d'accumulateurs avec l'ajout d'un ou plusieurs registres auxiliaires (dédiés), dont le plus courant est appelé "l'accumulateur".

Définition formelle

Une machine à accès aléatoire (RAM) est un modèle abstrait de machine de calcul identique à une machine à compteur à registres multiples avec l'ajout d'un adressage indirect. À la discrétion d'une instruction à partir de la TABLE de sa machine à états finis , la machine dérive l'adresse d'un registre "cible" soit (i) directement à partir de l'instruction elle-même, soit (ii) indirectement à partir du contenu (par exemple numéro, étiquette) de la registre "pointeur" spécifié dans l'instruction.

Par définition : un registre est un emplacement avec à la fois une adresse (une désignation/un localisateur unique et distinguable équivalent à un nombre naturel) et un contenu  – un seul nombre naturel. Pour plus de précision nous utiliserons le symbolisme quasi-formel de Boolos-Burgess-Jeffrey (2002) pour spécifier un registre, son contenu, et une opération sur un registre :

  • [r] signifie "le contenu du registre avec l'adresse r". L'étiquette "r" est ici une "variable" qui peut être remplie d'un nombre naturel ou d'une lettre (par exemple "A") ou d'un nom.
  • → signifie "copier/déposer dans", ou "remplace", mais sans destruction de la source
Exemple : [3] +1 → 3 ; signifie "Le contenu du registre source avec l'adresse "3", plus 1, est mis dans le registre destination avec l'adresse "3" (ici la source et la destination sont au même endroit). Si [3]=37, c'est-à-dire le contenu de le registre 3 est le nombre "37", alors 37+1 = 38 sera mis dans le registre 3.
Exemple : [3] → 5 ; signifie "Le contenu du registre source avec l'adresse "3" est mis dans le registre de destination avec l'adresse "5". Si [3]=38, c'est-à-dire que le contenu du registre 3 est le nombre 38, alors ce nombre sera mis dans registre 5. Le contenu du registre 3 n'est pas perturbé par cette opération, donc [3] reste 38, maintenant le même que [5].

Définition : Une instruction directe est une instruction qui précise dans l'instruction elle - même l'adresse du registre source ou destination dont le contenu fera l'objet de l'instruction. Définition : Une instruction indirecte est une instruction qui spécifie un "registre pointeur", dont le contenu est l'adresse d'un registre "cible". Le registre cible peut être soit une source, soit une destination (les différentes instructions COPY en fournissent des exemples). Un registre peut s'adresser indirectement.

Faute de norme/convention cet article précisera "direct/indirect", abrégé en "d/i", comme paramètre (ou paramètres) dans l'instruction :
Exemple: COPY ( d , A, i , n) des moyens directement d obtenir l'adresse du registre de source (registre "A") de l'instruction elle-même , mais indirectement i obtenir l'adresse de destination à partir de pointeur registre N. Supposons [N] = 3, alors le registre 3 est la destination et l'instruction fera ce qui suit : [A] → 3.

Définition : Le contenu du registre source est utilisé par l'instruction. L'adresse du registre source peut être spécifiée soit (i) directement par l'instruction, soit (ii) indirectement par le registre pointeur spécifié par l'instruction.

Définition : Le contenu du registre pointeur est l' adresse du registre "cible".

Définition : Le contenu du registre pointeur pointe vers le registre cible  – la « cible » peut être soit un registre source, soit un registre de destination.

Définition : Le registre de destination est l'endroit où l'instruction dépose son résultat. L'adresse du registre source peut être spécifiée soit (i) directement par l'instruction, soit (ii) indirectement par le registre pointeur spécifié par l'instruction. Les registres source et destination peuvent ne faire qu'un.

Rafraîchissement : Le modèle de contre-machine

Melzak (1961) fournit une visualisation aisée d'une machine à compteur : ses « registres » sont des trous dans le sol, et ces trous retiennent des cailloux. Par une instruction, dans et hors de ces trous "l'ordinateur" (personne ou machine) ajoute (INCrements) ou supprime (DECrements) un seul caillou. Au besoin, des cailloux supplémentaires proviennent, et les cailloux excédentaires retournent dans une offre infinie; si le trou est trop petit pour accueillir les cailloux, "l'ordinateur" creuse le trou plus gros.
Minsky (1961) et Hopcroft-Ullman 1979 (p. 171) proposent la visualisation d'une machine de Turing multi-bandes avec autant de bandes à gauche que de "registres". La longueur de chaque bande est illimitée vers la droite, et chaque carré est vierge à l'exception de l'extrémité gauche, qui est marquée. La distance de la "tête" d'un ruban à son extrémité gauche, mesurée en nombre de carrés de ruban, représente l'entier naturel dans "le registre". Pour DIMINUER le nombre de carrés, la tête de bande se déplace vers la gauche ; INCrement il se déplace vers la droite. Il n'est pas nécessaire d'imprimer ou d'effacer des marques sur la bande ; les seules instructions conditionnelles sont de vérifier si la tête est à l'extrémité gauche, en testant une marque d'extrémité gauche avec une "instruction Jump-if-marked".
Les instructions suivantes « mnémoniques », par exemple « CLR (r) » sont arbitraires ; aucune norme n'existe.

La machine à registres a, pour une mémoire externe à sa machine à états finis – une collection illimitée (cf: note de bas de page|comptable et illimitée) d'emplacements discrets et étiquetés de manière unique avec une capacité illimitée , appelés "registres". Ces registres ne contiennent que des nombres naturels (zéro et les entiers positifs). Par une liste d'instructions séquentielles dans la TABLE de la machine à états finis, quelques (par exemple 2) types d'opérations primitives opèrent sur le contenu de ces "registres". Enfin, une expression conditionnelle sous la forme d'un IF-THEN-ELSE est disponible pour tester le contenu d'un ou deux registres et "brancher/sauter" la machine à états finis hors de la séquence d'instructions par défaut.

Modèle de base 1 : Le modèle le plus proche de la visualisation de Minsky (1961) et de Lambek (1961) :

  • { INCrement du contenu du registre r, DECrement du contenu du registre r, SI le contenu du registre r est nul ALORS sauter à l'instruction I z AUTREMENT passer à l'instruction suivante } :
Instruction Mnémonique Action sur le(s) registre(s) "r" Action sur le registre d'instructions de la machine à états finis, IR
Incrément INC ( r ) [r] + 1 → r [IR] + 1 → IR
DIMINUER DEC ( r ) [r] - 1 → r [IR] + 1 → IR
Sauter si zéro JZ ( r, z ) rien SI [r] = 0 ALORS z → IR SINON [IR] + 1 → IR
Arrêt H rien [IR] → IR

Modèle de base 2 : Le modèle "successeur" (du nom de la fonction successeur des axiomes de Peano ) :

  • { INCremente le contenu du registre r, EFFACER le contenu du registre r, SI le contenu du registre r j est égal au contenu du registre r k ALORS sauter à l'instruction I z AUTREMENT aller à l'instruction suivante }
Instruction Mnémonique Action sur le(s) registre(s) "r" Action sur le registre d'instructions de la machine à états finis, IR
Dégager CLR ( r ) 0 → r [IR] + 1 → IR
Incrément INC ( r ) [r] + 1 → r [IR] + 1 → IR
Sauter si égal JE (r1, r2, z) rien SI [r1] = [r2] ALORS z → IR SINON [IR] + 1 → IR
Arrêt H rien [IR] → IR

Modèle de base 3 : utilisé par Elgot-Robinson (1964) dans son enquête sur les RASP bornées et non bornées – le modèle « successeur » avec COPY à la place de CLEAR :

  • {Incrémenter le contenu du registre R, copier le contenu du registre r j pour enregistrer r k , IF contenu du registre r j est égal au contenu du registre r k puis Aller à l' instruction I z ELSE GOTO pour instruction suivante}
Instruction Mnémonique Action sur le(s) registre(s) "r" Action sur le registre d'instructions de la machine à états finis, IR
COPIE COPIER (r1, r2) [r1] → r2 [IR] + 1 → IR
Incrément INC ( r ) [r] + 1 → r [IR] + 1 → IR
Sauter si égal JE (r1, r2, z) rien SI [r1] = [r2] ALORS z → IR SINON [IR] + 1 → IR
Arrêt H rien [IR] → IR

Créer des « instructions pratiques » à partir des ensembles de base

Les trois ensembles de base 1, 2 ou 3 ci-dessus sont équivalents dans le sens où l'on peut créer les instructions d'un ensemble en utilisant les instructions d'un autre ensemble (un exercice intéressant : un indice de Minsky (1967) – déclarer un registre réservé, par exemple appeler il "0" (ou Z pour "zéro" ou E pour "effacer") pour contenir le nombre 0). Le choix du modèle dépendra de celui qu'un auteur trouvera le plus facile à utiliser dans une démonstration, ou une preuve, etc.

De plus, à partir des ensembles de base 1, 2 ou 3, nous pouvons créer n'importe laquelle des fonctions récursives primitives ( cf Minsky (1967), Boolos-Burgess-Jeffrey (2002) ). (Comment élargir le réseau pour capturer les fonctions récursives totales et partielles mu sera discuté dans le contexte de l'adressage indirect). Cependant, construire les fonctions récursives primitives est difficile car les jeux d'instructions sont tellement... primitifs (minuscules). Une solution consiste à étendre un ensemble particulier avec des "instructions de commodité" à partir d'un autre ensemble :

Il ne s'agira pas de sous-programmes au sens conventionnel du terme mais plutôt de blocs d'instructions créés à partir de l'ensemble de base et dotés d'un mnémonique. Dans un sens formel, pour utiliser ces blocs, nous devons soit (i) les "étendre" dans leurs équivalents d'instructions de base - ils nécessiteront l'utilisation de registres temporaires ou "auxiliaires" afin que le modèle doit en tenir compte, ou ( ii) concevoir nos machines/modèles avec les instructions « intégrées ».
Exemple : Ensemble de base 1. Pour créer CLR (r), utilisez le bloc d'instructions pour décompter le registre r jusqu'à zéro. Observez l'utilisation de l'astuce mentionnée ci-dessus :
  • CLR (r) = équiv
  • boucle : JZ (r, sortie )
  • DEC (r)
  • JZ (0, boucle )
  • sortie : etc.

Encore une fois, tout cela est pour plus de commodité seulement ; rien de tout cela n'augmente la puissance intrinsèque du modèle.

Par exemple : l'ensemble le plus étendu inclurait chaque instruction unique des trois ensembles, plus le saut inconditionnel J (z) c'est-à-dire :

  • {CLR (r), DEC (r), INC (r), CPY (r s , r d ), JZ (r, z), JE (r j , r k , z), J (z)}

La plupart des auteurs choisissent l'un ou l'autre des sauts conditionnels, par exemple Shepherdson-Sturgis (1963) utilise l'ensemble ci-dessus moins JE (pour être parfaitement précis, ils utilisent JNZ - Jump if Not Zero à la place de JZ ; encore une autre instruction de commodité possible).

L'opération "indirecte"

Exemple d'adressage indirect

Dans notre vie quotidienne, la notion d'« opération indirecte » n'est pas inhabituelle.

Exemple : une chasse au trésor.
À l'emplacement "Tom_&_Becky's_cave_in_pirate_chest" sera l'endroit où nous pouvons trouver une carte nous dirigeant vers "le trésor":
(1) Nous allons à l'emplacement "Tom_&_Becky's_cave..." et creusons jusqu'à ce que nous trouvions une boîte en bois
(2) À l'intérieur de la boîte se trouve une carte indiquant l'emplacement du trésor : "under_Thatcher's_front_porch"
(3) Nous allons à l'emplacement "under_Thatcher's_front_porch", martelons le béton et découvrons "le trésor": un sac de poignées de porte rouillées.

L'indirection spécifie un emplacement identifié comme le coffre de pirate dans "Tom_&_Becky's_cave..." qui agit comme un pointeur vers tout autre emplacement (y compris lui-même) : son contenu (la carte au trésor) fournit l'"adresse" de l' emplacement cible "under_Thatcher 's_front_porch" où se déroule la véritable action.

Pourquoi la nécessité d'une opération indirecte : Deux problèmes majeurs avec le modèle de contre-machine

Dans ce qui suit, il faut se rappeler que ces modèles sont des modèles abstraits avec deux différences fondamentales par rapport à tout ce qui est physiquement réel : des nombres illimités de registres chacun avec des capacités illimitées. Le problème apparaît le plus dramatiquement lorsque l'on essaie d'utiliser un modèle de contre-machine pour construire un RASP équivalent à Turing et ainsi calculer toute fonction récursive mu partielle :

  • Melzak (1961) a ajouté l'indirection à son modèle "trou et caillou" afin que son modèle puisse se modifier avec un "goto calculé" et donne deux exemples de son utilisation ("Représentation décimale à l'échelle de d" et "Tri par magnitude", si ceux-ci sont utilisés dans sa preuve que le modèle est équivalent à Turing n'est pas clair puisque "le programme lui-même est laissé au lecteur comme exercice" (p. 292)). Minsky (1961, 1967) a pu démontrer qu'avec un codage numérique de Gödel approprié (mais difficile à utiliser) , le modèle de registre n'avait pas besoin d'indirection pour être équivalent à Turing ; mais il fallait au moins un registre non borné. Comme indiqué ci-dessous, Minsky (1967) fait allusion au problème d'un RASP mais n'offre pas de solution. Elgot et Robinson (1964) ont prouvé que leur modèle RASP P 0  - il n'a pas de capacité d'indirection - ne peut pas calculer toutes les "fonctions séquentielles récursives" (celles qui ont des paramètres de longueur arbitraire) s'il n'a pas la capacité de modifier ses propres instructions, mais il le peut via les nombres de Gödel s'il le fait (p. 395-397 ; en particulier figure 2 et note de bas de page p. 395). D'autre part leur modèle RAPE P » 0 équipé d'un « registre d'index »(adressage indirect) peut calculer toutes les « fonctions séquentielles partielles récursives »(les mu fonctions récursives) (p. 397-398).
Cook et Reckhow (1973) le disent très succinctement :
Les instructions indirectes sont nécessaires pour qu'un programme fixe accède à un nombre illimité de registres car les entrées varient." (p. 73)
  • Unbounded capacités des registres par rapport aux capacités bornées d'instructions à la machine d'état : Le soi-disant finie partie de l' état de la machine est censé être - par la définition normale de l' algorithme - très finis à la fois dans le nombre de « états » (instructions) et la la taille des instructions (leur capacité à contenir des symboles/signes). Alors, comment une machine à états déplace-t-elle une constante arbitrairement grande directement dans un registre, par exemple MOVE (k, r) (Déplacer la constante k vers le registre r) ? Si d'énormes constantes sont nécessaires, elles doivent soit commencer dans les registres eux-mêmes, soit être créées par la machine à états en utilisant un nombre fini d'instructions, par exemple multiplier et ajouter des sous-programmes en utilisant INC et DEC (mais pas un nombre quasi infini de ceux-ci !).
Parfois, la constante k sera créée en utilisant CLR ( r ) suivi de INC ( r ) répété k fois – par exemple pour mettre la constante k=3 dans le registre r, c'est-à-dire 3 → r, donc à la fin de l'instruction [r ]=3 : CLR (r), INC (r), INC (r), INC (r). Cette astuce est mentionnée par Kleene (1952) p. 223. Le problème se pose lorsque le nombre à créer épuise le nombre d'instructions disponibles pour la machine à états finis ; il y a toujours une constante plus grande que le nombre d'instructions disponibles pour la machine à états finis .
  • Unbounded nombre de registres par rapport bornées instructions à la machine d'état : Ceci est plus grave que le premier problème. En particulier, ce problème se pose lorsque nous essayons de construire ce qu'on appelle une RASP, une "machine universelle" (voir plus sur Universal Turing machine ) qui utilise sa machine à états finis pour interpréter un "programme d'instructions" situé dans ses registres - c'est-à-dire que nous construisons ce qu'on appelle aujourd'hui un ordinateur avec l' architecture von Neumann .
Observez que la machine à états finis de la machine de compteur doit appeler un registre explicite (directement) par son nom / numéro: INC (65,356) appelle le numéro de registre « 65365 » explicitement . Si le nombre de registres dépasse la capacité de la machine à états finis à les adresser, alors les registres en dehors des limites seront inaccessibles. Par exemple, si la machine à états finis ne peut atteindre que 65 536 = 2 16 registres, alors comment peut-elle atteindre le 65 537e ?

Alors , comment ne nous abordons un registre au - delà des limites de la machine à états finis? Une approche serait de modifier les instructions du programme (celles stockées dans les registres) afin qu'elles contiennent plus d'une commande. Mais cela aussi peut être épuisé à moins qu'une instruction soit de taille (potentiellement) illimitée. Alors pourquoi ne pas utiliser une seule "über-instruction" - un très très gros nombre - qui contient toutes les instructions du programme codées dedans ! C'est ainsi que Minsky résout le problème, mais la numérotation de Gödel qu'il utilise représente un grand inconvénient pour le modèle, et le résultat ne ressemble en rien à notre notion intuitive d'un "ordinateur à programme stocké".

Elgot et Robinson (1964) arrivent à une conclusion similaire en ce qui concerne un RASP qui est "définiment déterminé". En effet il peut accéder à un nombre illimité de registres (par exemple pour en extraire des instructions) mais seulement si le RASP autorise "l'auto-modification" de ses instructions de programme , et a encodé ses "données" dans un nombre de Gödel (Fig. 2 p. 396). ).

Dans le contexte d'un modèle plus informatique utilisant son instruction RPT (répétition) Minsky (1967) nous tente avec une solution au problème (cf p. 214, p. 259) mais n'offre pas de résolution ferme. Il affirme :

"En général, une opération RPT ne peut pas être une instruction dans la partie finie de la machine... cela pourrait épuiser toute quantité particulière de stockage autorisée dans la partie finie de l'ordinateur [sic, son nom pour ses modèles de RAM]. Les opérations RPT nécessitent leurs propres registres infinis." (p. 214).

Il nous propose un RPT borné qui, avec CLR (r) et INC (r) peut calculer n'importe quelle fonction récursive primitive , et il propose le RPT non borné cité ci-dessus comme jouant le rôle de l'opérateur μ ; il peut, avec CLR (r) et INC (r), calculer les mu fonctions récursives. Mais il ne discute pas de "l'indirection" ou du modèle RAM en soi.

D'après les références de Hartmanis (1971), il apparaît que Cook (dans ses notes de cours alors qu'il était à UC Berkeley, 1970) a confirmé la notion d'adressage indirect. Cela devient plus clair dans l'article de Cook et Reckhow (1973) - Cook est le directeur de thèse de Reckhow. Le modèle de Hartmanis – assez similaire au modèle de Melzak (1961) – utilise des additions et des soustractions à deux et trois registres et deux copies de paramètres ; Le modèle de Cook et Reckhow réduit le nombre de paramètres (registres appelés dans les instructions du programme) à un appel en utilisant un accumulateur "AC".

La solution en un mot : Concevez notre machine/modèle avec une indirection illimitée  – fournissez un registre « d'adresse » illimité qui peut potentiellement nommer (appeler) n'importe quel registre, quel que soit son nombre. Pour que cela fonctionne, en général, le registre illimité nécessite une capacité à être effacé puis incrémenté (et, éventuellement, décrémenté) par une boucle potentiellement infinie. En ce sens, la solution représente l' opérateur μ non borné qui peut, si nécessaire, chasser à l'infini le long de la chaîne de registres non bornée jusqu'à ce qu'il trouve ce qu'il cherche. Le registre pointeur est exactement comme n'importe quel autre registre à une exception près : dans les circonstances appelées « adressage indirect », il fournit son contenu, plutôt que l'opérande d'adresse dans la TABLE de la machine d'état, pour être l'adresse du registre cible (y compris éventuellement lui-même !).

L'indirection bornée et les fonctions récursives primitives

Si nous évitons l'approche de Minsky d'un nombre monstre dans un registre, et spécifions que notre modèle de machine sera "comme un ordinateur", nous devons faire face à ce problème d'indirection si nous voulons calculer les fonctions récursives (également appelées les fonctions μ-récursives fonctions ) – variétés totales et partielles.

Notre modèle de contre-machine plus simple peut faire une forme "limitée" d'indirection - et ainsi calculer la sous-classe de fonctions récursives primitives  - en utilisant un "opérateur" récursif primitif appelé "définition par cas" (défini dans Kleene (1952) p 229 et Boolos-Burgess-Jeffrey p.74). Une telle "indirection bornée" est une affaire laborieuse et fastidieuse. La "définition par cas" exige que la machine détermine/distingue le contenu du registre de pointeurs en essayant, à maintes reprises jusqu'au succès, de faire correspondre ce contenu à un numéro/nom que l'opérateur de cas déclare explicitement . Ainsi, la définition par cas commence par exemple à partir de l'adresse de limite inférieure et continue jusqu'à l'adresse de limite supérieure en essayant de faire une correspondance :

Le nombre dans le registre N est-il égal à 0 ? Sinon, est-il égal à 1 ? 2 ? 3 ? ... 65364 ? Sinon, nous sommes au dernier numéro 65365 et il vaut mieux que ce soit celui-ci, sinon nous avons un problème !

L'indirection "limitée" ne nous permettra pas de calculer les fonctions récursives partielles - pour celles-ci, nous avons besoin d' une indirection non limitée aka l' opérateur μ .

Supposons que nous ayons pu continuer jusqu'au numéro 65367, et qu'en fait ce registre ait ce que nous cherchions. Nous aurions alors pu terminer notre calcul avec succès ! Mais supposons que 65367 n'ait pas ce dont nous avions besoin. Jusqu'où doit-on continuer d'aller ?

Pour être équivalente à Turing, la machine à compteur doit soit utiliser la malheureuse méthode des nombres à registre unique de Minsky Gödel , soit être augmentée d'une capacité à explorer les extrémités de sa chaîne de registres, à l'infini si nécessaire. (Un échec à trouver quelque chose "là-bas" définit ce que cela signifie pour un algorithme d'échouer à se terminer ; cf Kleene (1952) pp. 316ff Chapitre XII Fonctions Récursives Partielles , en particulier p. 323-325.) Voir plus à ce sujet dans l'exemple ci-dessous.

L'indirection non bornée et les fonctions récursives partielles

Pour une indirection illimitée, nous avons besoin d'un changement "matériel" dans notre modèle de machine. Une fois ce changement effectué, le modèle n'est plus une machine à compteur, mais plutôt une machine à accès aléatoire.

Maintenant, lorsque, par exemple, INC est spécifié, l'instruction de la machine à états finis devra spécifier d' où viendra l'adresse du registre d'intérêt. Ce où peut être (i) l'instruction de la machine d'état qui fournit une étiquette explicite , ou (ii) le pointeur registre dont le contenu est l'adresse d'intérêt. Chaque fois qu'une instruction spécifie une adresse de registre, elle devra désormais également spécifier un paramètre supplémentaire "i/d" - "indirect/direct". Dans un sens, ce nouveau paramètre "i/d" est un "commutateur" qui bascule dans un sens pour obtenir l'adresse directe comme spécifié dans l'instruction ou dans l'autre pour obtenir l'adresse indirecte du registre pointeur (quel registre pointeur - dans certains modèles chaque registre peut être un registre pointeur - est spécifié par l'instruction). Ce "choix mutuellement exclusif mais exhaustif" est encore un autre exemple de "définition par cas", et l'équivalent arithmétique montré dans l'exemple ci-dessous est dérivé de la définition de Kleene (1952) p. 229.

Exemple : CPY ( source indirecte , r source , destination directe , r destination )
Attribuez un code pour spécifier l'adressage direct comme d="0" et l'adressage indirect comme i="1". Ensuite, notre machine peut déterminer l'adresse source comme suit :
i*[r s ] + (1-i)*r s
Par exemple, supposons que le contenu du registre 3 soit "5" (c'est-à-dire [3]=5 ) et que le contenu du registre 4 soit "2" (c'est-à-dire [4]=2 ) :
Exemple : CPY ( 1, 3, 0, 4 ) = CPY ( indirect, reg 3, direct, reg 4 )
1*[3] + 0*3 = [3] = adresse du registre source 5
0*[4] + 1*4 = 4 = adresse de registre de destination 4
Exemple : CPY ( 0, 3, 0, 4 )
0*[3] + 1*3 = 3 = adresse du registre source 3
0*[4] + 1*4 = 4 = adresse de registre de destination 4
Exemple : CPY ( 0, 3, 1, 4 )
0*[3] + 1*3 = 3 = adresse du registre source 3
1*[4] + 0*4 = [4] = adresse du registre de destination 2

L'instruction COPIE indirecte

La plus utile des instructions ajoutées est probablement COPY. En effet, Elgot-Robinson (1964) fournit à leurs modèles P 0 et P' 0 les instructions COPY, et Cook-Reckhow (1973) fournit leur modèle basé sur l'accumulateur avec seulement deux instructions indirectes - COPY to accumulator indirectement, COPY from accumulateur indirectement .

Une pléthore d'instructions : Parce que toute instruction agissant sur un seul registre peut être augmentée de son "double" indirect (y compris les sauts conditionnels et inconditionnels, cf le modèle d'Elgot-Robinson), l'inclusion d'instructions indirectes doublera le nombre de paramètres simples/ enregistrer des instructions (par exemple INC (d, r), INC (i, r)). Pire, chaque instruction de deux paramètres/registres aura 4 variétés possibles, par exemple :

CPY (d, r s , d, r d ) = COPIER directement du registre source directement au registre de destination
CPY (i, r sp , d, r d ) = COPIER vers le registre de destination indirectement en utilisant l'adresse source qui se trouve dans le registre de pointeur de source r sp .
CPY (d, r s , i, r dp ) = COPIE le contenu du registre source indirectement dans le registre en utilisant l'adresse de destination qui se trouve dans le registre pointeur de destination r dp .
CPY (i, r sp , i, r dp ) = COPIE indirectement le contenu du registre source dont l'adresse se trouve dans le registre pointeur source r sp , dans le registre destination dont l'adresse se trouve dans le registre pointeur destination r dp )

De la même manière, chaque instruction à trois registres qui implique deux registres source r s1 r s2 et un registre de destination r d entraînera 8 variétés, par exemple l'addition :

[r s1 ] + [r s2 ] → r d

donnera :

  • AJOUTER ( d, r s1 , d, r s2 , d, r d )
  • AJOUTER ( i, r sp1 , d, r s2 , d, r d )
  • AJOUTER ( d, r s1 , i, r sp2 , d, r d )
  • AJOUTER ( i, r sp1 , i, r sp2 , d, r d )
  • AJOUTER ( d, r s1 , d, r s2 , i, r dp )
  • AJOUTER ( i, r sp1 , d, r s2 , i, r dp )
  • AJOUTER ( d, r s1 , i, r sp2 , i, r dp )
  • AJOUTER ( i, r sp1 , i, r sp2 , i, r dp )

Si nous désignons un registre comme étant "l'accumulateur" (voir ci-dessous) et imposons de fortes restrictions sur les diverses instructions autorisées, nous pouvons alors réduire considérablement la pléthore d'opérations directes et indirectes. Cependant, il faut être sûr que le jeu d'instructions réduit résultant est suffisant, et nous devons être conscients que la réduction se fera au détriment de plus d'instructions par opération "significative".

La notion d'« accumulateur A »

La convention historique consacre un registre à l'accumulateur, un « organe arithmétique » qui accumule littéralement son nombre au cours d'une séquence d'opérations arithmétiques :

"La première partie de notre organe arithmétique... devrait être un organe de stockage parallèle qui peut recevoir un nombre et l'ajouter à celui qui s'y trouve déjà, qui est également capable d'effacer son contenu et qui peut stocker ce qu'il contient. Nous allons appelons un tel organe un accumulateur . Il est assez conventionnel en principe dans les machines informatiques passées et présentes des types les plus variés, par exemple les multiplicateurs de bureau, les compteurs IBM standard, les machines relais plus modernes, l'ENIAC" (en gras dans l'original : Goldstine et von Neumann , 1946 ; p. 98 dans Bell et Newell 1971).

Cependant, l'accumulateur se fait au détriment de plus d'instructions par "opération" arithmétique, notamment en ce qui concerne ce qu'on appelle des instructions "lecture-modification-écriture" telles que "Incrémenter indirectement le contenu du registre pointé par le registre r2". "A" désigne le registre "accumulateur" A :

Étiqueter Instruction UNE r2 378 426 r La description
. . . 378 426 17
INCi ( r2 ): CPY ( i, r2, d, A ) 17 378 426 17 Le contenu de r2 pointe vers r378 426 avec le contenu "17": copiez-le dans A
INC ( A ) 18 378 426 17 Inciment contenu de A
CPY ( d, A, i, r2 ) 18 378 426 18 Le contenu de r2 pointe vers r378 426 : copie le contenu de A dans r378 426

Si nous nous en tenons à un nom spécifique pour l'accumulateur, par exemple "A", nous pouvons impliquer l'accumulateur dans les instructions, par exemple,

INC ( A ) = INCA

Cependant, lorsque nous écrivons les instructions CPY sans que l'accumulateur soit appelé, les instructions sont ambiguës ou doivent avoir des paramètres vides :

CPY ( d, r2, d, A ) = CPY (d, r2, , )
CPY ( d, A, d, r2 ) = CPY ( , , d, r2)

Historiquement, ce qui s'est passé, c'est que ces deux instructions CPY ont reçu des noms distinctifs ; cependant, aucune convention n'existe. La tradition (par exemple l' ordinateur imaginaire MIX de Knuth (1973) ) utilise deux noms appelés LOAD et STORE. Ici, nous ajoutons le paramètre "i/d":

LDA ( d/i, r s ) = def CPY ( d/i, r s , d, A )
STA ( d/i, r d ) = def CPY ( d, A, d/i, r d )

Le modèle typique basé sur l'accumulateur aura toutes ses opérations arithmétiques et constantes à deux variables (par exemple ADD (A, r), SUB (A, r) ) utilisera (i) le contenu de l'accumulateur, ainsi que (ii) le contenu d'un registre spécifié . Les opérations à une variable (par exemple INC (A), DEC (A) et CLR (A) ) ne nécessitent que l'accumulateur. Les deux types d'instruction déposent le résultat (par exemple somme, différence, produit, quotient ou reste) dans l'accumulateur.

Exemple : INCA = [A] +1 → A
Exemple : ADDA (r s ) = [A] + [r s ] → A
Exemple : MULA (r s ) = [A] * [r s ] → A

Si on le souhaite, on peut abréger les mnémoniques car au moins un registre source et le registre destination est toujours l'accumulateur A. On a donc :

{ LDA (i/d, r s ), STA (i/d, r d ), CLRA, INCA, DECA, ADDA (r s ), SUBA (r s ), MULA (r s ), DIVA (r s ) , etc.)

La notion de registre d'adresse indirecte "N"

Si notre modèle a un accumulateur non borné, pouvons-nous borner tous les autres registres ? Pas tant que nous n'aurons pas fourni au moins un registre illimité à partir duquel nous dérivons nos adresses indirectes.

L'approche minimaliste consiste à s'utiliser (Schönhage le fait).

Une autre approche (Schönhage le fait aussi) consiste à déclarer un registre spécifique le "registre d'adresse indirecte" et à confiner l'indirection relative à ce registre (le modèle RAM0 de Schönhage utilise à la fois les registres A et N pour les instructions indirectes et directes). Encore une fois, notre nouveau registre n'a pas de nom conventionnel – peut-être « N » de « iNdex », ou « iNdirect » ou « numéro d'adresse ».

Pour une flexibilité maximale, comme nous l'avons fait pour l'accumulateur A - nous considérerons N juste un autre registre sujet à incrémenter, décrémenter, effacer, tester, copier directement, etc. Encore une fois, nous pouvons réduire l'instruction à un seul paramètre qui fournit la direction et l'indirection, par exemple.

LDAN (i/d) = CPY (i/d, N, d, A); Accumulateur de charge via le registre iNdirection
STAN (i/d) = CPY (d, A, i/d, N). Accumulateur de magasin via le registre iNdirection

Pourquoi est-ce une approche si intéressante ? Au moins deux raisons :

(1) Un jeu d'instructions sans paramètres :

Schönhage fait cela pour produire son jeu d'instructions RAM0. Voir la section ci-dessous.

(2) Réduire une RAM à une machine Post-Turing :

En se présentant comme des minimalistes, nous réduisons tous les registres à l'exception de l'accumulateur A et du registre d'indirection N eg r = { r0, r1, r2, ... } à une chaîne illimitée de casiers à capacité (très) bornée. Ceux-ci ne feront rien d'autre que contenir des nombres (très) limités, par exemple un bit isolé avec la valeur { 0, 1 }. De même, nous réduisons l'accumulateur à un seul bit. Nous restreignons toute arithmétique aux registres { A, N }, utilisons des opérations indirectes pour extraire le contenu des registres dans l'accumulateur et écrivons 0 ou 1 de l'accumulateur dans un registre :

{ LDA (i, N), STA (i, N), CLR (A/N), INC (A/N), DEC(N), JZ (A/N, I z ), JZ (I z ), H}

Nous poussons plus loin et éliminons complètement A par l'utilisation de deux registres « constants » appelés « ERASE » et « PRINT » : [ERASE]=0, [PRINT]=1.

{ CPY (d, ERASE, i, N), CPY (d, PRINT, i, N), CLR (N), INC (N), DEC (N), JZ (i, N, I z ), JZ ( Je z ), H }

Renommez les instructions COPY et appelez INC (N) = RIGHT, DEC (N) = LEFT et nous avons les mêmes instructions que la machine Post-Turing, plus un CLRN supplémentaire :

{ EFFACER, IMPRIMER, CLRN, DROITE, GAUCHE, JZ (i, N, I z ), JZ (I z ), H }

Equivalence de Turing de la RAM avec indirection

Dans la section ci-dessus, nous avons montré de manière informelle qu'une RAM avec une capacité d'indirection illimitée produit une machine Post-Turing . La machine Post-Turing est équivalente à Turing, nous avons donc montré que la RAM avec indirection est équivalente à Turing.

Nous donnons ici une démonstration un peu plus formelle. Commencez par concevoir notre modèle avec trois registres réservés "E", "P" et "N", plus un ensemble illimité de registres 1, 2, ..., n à droite. Les registres 1, 2, ..., n seront considérés comme "les carrés de la bande". Le registre "N" pointe vers "le carré scanné" que "la tête" observe actuellement. La "tête" peut être considérée comme étant dans le saut conditionnel – notez qu'elle utilise l'adressage indirect (cf. Elgot-Robinson p. 398). Au fur et à mesure que nous décrémentons ou incrémentons "N", la tête (apparente) "se déplacera à gauche" ou "à droite" le long des carrés. Nous déplacerons le contenu de "E"=0 ou "P"=1 vers le "carré scanné" comme indiqué par N, en utilisant le CPY indirect.

Le fait que notre bande soit à extrémité gauche nous pose un problème mineur : chaque fois que LEFT se produit, nos instructions devront tester pour déterminer si le contenu de « N » est égal ou non à zéro ; si c'est le cas, nous devrions laisser son compte à "0" (c'est notre choix en tant que concepteurs - par exemple, nous pourrions avoir la machine/le modèle "déclencher un événement" de notre choix).

Jeu d'instructions 1 (augmenté) : { INC (N), DEC (N), CLR (N), CPY (d, r s ,i, N), JZ ( i, r, z ), HALT }

Le tableau suivant définit à la fois les instructions de Post-Turing en termes d'instructions équivalentes en RAM et donne un exemple de leur fonctionnement. L'emplacement (apparent) de la tête le long de la bande des registres r0-r5 . . . est représenté en grisé :

Mnémonique étiqueter: E P N r0 r1 r2 r3 r4 r5 etc. Action sur les registres Action sur la machine à états finis Instruction Registre IR
début: 0 1 3 1 0
R droit: INC ( N ) 0 1 4 1 0 [N] +1 → N [IR] +1 → IR
P imprimer: CPY ( d, P, i, N ) 0 1 4 1 1 [P]=1 → [N]=r4 [IR] +1 → IR
E effacer: CPY ( d, E, i, N ) 0 1 4 1 0 [E]=0 → [N]=r4 [IR] +1 → IR
L la gauche: JZ ( je, N, fin ) 0 1 4 1 0 rien SI N =r4] =0 ALORS "fin" → IR sinon [IR]+1 → IR
DEC ( N ) 0 1 3 1 0 [N] -1 → N
J0 (arrêt) jump_if_blank : JZ ( je, N, fin ) 0 1 3 1 0 rien SI N =r3] =0 ALORS "fin" → IR sinon [IR]+1 → IR
J1 (arrêt) jump_if_mark : JZ ( i, N, arrêt ) 0 1 3 1 0 N =r3] → A SI N =r3] =0 ALORS "fin" → IR sinon [IR]+1 → IR
finir . . . etc. 0 1 3 1 0
arrêt: H 0 1 3 1 0 rien [IR] +1 → IR

Exemple : l'indirection bornée donne une machine qui n'est pas équivalente à Turing

Tout au long de cette démonstration, nous devons garder à l'esprit que les instructions de la machine à états finis TABLE sont bornées , c'est-à-dire finies :

"En plus d'être simplement un ensemble fini de règles qui donne une séquence d'opérations pour résoudre un type spécifique de problème, un algorithme a cinq caractéristiques importantes [finité, précision, entrée, sortie, efficacité]" (italiques ajoutés, Knuth p. 4 -7).
La difficulté vient du fait que les registres ont des "noms" (numéros) explicites et notre machine doit appeler chacun par son nom pour "y accéder".

Nous allons construire le CPY indirect ( i, q, d, φ ) avec l'opérateur CASE. L'adresse du registre cible sera précisée par le contenu du registre "q" ; une fois que l'opérateur CASE a déterminé quel est ce numéro, CPY déposera directement le contenu du registre avec ce numéro dans le registre "φ". Nous aurons besoin d'un registre supplémentaire que nous appellerons "y" - il sert de compteur.

Ce qui suit est donc en fait une démonstration ou une preuve constructive que nous pouvons effectivement simuler le CPY indirect ( i, q, d, φ ) sans modification de conception "matérielle" de notre compteur/modèle. Cependant, notez que parce que ce CPY indirect est "limité" par la taille/l'étendue de la machine à états finis, un RASP utilisant ce CPY indirect ne peut calculer que les fonctions récursives primitives , pas la suite complète des fonctions récursives mu .

L'« opérateur » CASE est décrit dans Kleene (1952) (p. 229) et dans Boolos-Burgess-Jeffrey (2002) (p. 74) ; ces derniers auteurs soulignent son utilité. La définition suivante est celle de Kleene mais modifiée pour refléter la construction familière "IF-THEN-ELSE".

L'opérateur CASE "retourne" un nombre naturel dans φ en fonction du "cas" satisfait, en commençant par "case_0" et en passant successivement par "case_last" ; si aucun cas n'est satisfait, le nombre appelé "default" (alias "woops") est renvoyé dans φ (ici x désigne une sélection de paramètres, par exemple le registre q et la chaîne r0, ... rlast )):

Définition par les cas ( x , y) :

  • case_0 : SI Q 0 ( x , y) est vrai ALORS 0 ( x , y) SINON
  • case_1 : SI Q 1 ( x , y) est vrai ALORS 1 ( x , y) SINON
  • cases_2 à case_next_to_last : etc. . . . . . . . . AUTRE
  • case_last : SI Q dernier ( x , y) est vrai ALORS dernier ( x , y) SINON
  • par défaut : faire φ par défaut ( x , y)

Kleene exige que les « prédicats » Q n qui effectuent les tests soient tous mutuellement exclusifs – les « prédicats » sont des fonctions qui produisent uniquement { vrai, faux } pour la sortie ; Boolos-Burgess-Jeffrey ajoutent l'exigence que les cas soient "exhaustifs".

Nous commençons par un nombre dans le registre q qui représente l'adresse du registre cible. Mais quel est ce numéro ? Les "prédicats" vont le tester pour le savoir, un essai après l'autre : JE (q, y, z) suivi de INC (y). Une fois le numéro identifié explicitement, l'opérateur CASE copie directement/explicitement le contenu de ce registre dans φ :

Définition par cas CPY (i, q, d, φ) = def φ (q, r0, ..., rlast, y) =
  • case_0 : SI CLR (y), [q] - [y]=0 ALORS CPY ( r0, φ ), J (sortie) SINON
  • case_1 : SI INC (y), [q] = [y]=1 ALORS CPY ( r1, φ ), J (sortie) SINON
  • case_2 à case n : SI . . . ALORS . . . AUTRE
  • case_n : SI INC (y), [q] = [y]=n ALORS CPY ( rn, φ ), J (sortie) SINON
  • case_n+1 à case_last : SI . . . ALORS . . . AUTRE
  • case_last : IF INC (y), [q] = [y]="last" ALORS CPY ( rlast, φ ), J (exit) ELSE
  • par défaut : oups

Case_0 (le pas de base de la récursivité sur y) ressemble à ceci :

  • case_0 :
  • CLR ( y ) ; définir le registre y = 0
  • JE ( q, y, _φ0 )
  • J ( case_1 )
  • _φ0 : CPY ( r0, φ )
  • J ( sortie )
  • case_1 : etc.

Case_n (l'étape d'induction) ressemble à ceci ; rappelez-vous, chaque instance de "n", "n+1", ..., "last" doit être un nombre naturel explicite :

  • case_n :
  • INC ( y )
  • JE ( q, y, _φn )
  • J ( case_n+1 )
  • _φn : CPY ( rn, φ )
  • J ( sortie )
  • case__n+1 : etc.

Case_last arrête l'induction et délimite l'opérateur CASE (et délimite ainsi l'opérateur "copie indirecte") :

  • case_last :
  • INC ( y )
  • JE ( q, y, _φdernier )
  • J ( oups )
  • _φlast : CPY ( rlast, φ )
  • J ( sortie )
  • oups : comment gérer une tentative de hors-limites ?
  • sortie : etc.

Si le CASE pouvait continuer à l'infini, ce serait l' opérateur mu . Mais il ne peut pas – le "registre d'état" de sa machine à états finis a atteint son nombre maximum (par exemple 65365 = 11111111,11111111 2 ) ou sa table est à court d'instructions ; c'est une machine finie , après tout.

Exemples de modèles

Modèle de registre à registre ("lecture-modification-écriture") de Cook et Reckhow (1973)

Le modèle de Cook et Rechkow couramment rencontré est un peu comme le modèle de registre ternaire de Malzek (écrit avec les mnémoniques de Knuth - les instructions originales n'avaient pas de mnémoniques à l'exception de TRA, Read, Print).

  • LOAD ( C, rd ) ; C → rd, C est un entier quelconque
Exemple : LOAD ( 0, 5 )effacera le registre 5.
  • ADD ( rs1, rs2, rd ) ; [rs1] + [rs2] → rd, les registres peuvent être identiques ou différents ;
Exemple : ADD ( A, A, A )doublera le contenu du registre A.
  • SUB ( rs1, rs2, rd ) ; [rs1] - [rs2] → rd, les registres peuvent être identiques ou différents :
Exemple : SUB ( 3, 3, 3 )effacera le registre 3.
  • COPY ( i, rp, d, rd ) ; [[rp] ] → rd, Copiez indirectement le contenu du registre source pointé par le registre pointeur r p dans le registre de destination.
  • COPY ( d, rs, i, rp ) ; [rs] → [rp]. Copiez le contenu du registre source r s dans le registre de destination pointé par le registre pointeur r p .
  • JNZ ( r, Iz ) ;Saut conditionnel si [r] est positif ; c'est-à-dire SI [r] > 0 ALORS sauter à l'instruction z sinon continuer en séquence (Cook et Reckhow appellent ceci : "Transférer le contrôle à la ligne m si Xj > 0")
  • READ ( rd ) ;copier "l'entrée" dans le registre de destination r d
  • PRINT ( rs ) ;copier le contenu du registre source r s dans "la sortie".

RAM0 et RAM1 de Schönhage (1980)

Schönhage (1980) décrit un modèle atomisé très primitif choisi pour sa preuve de l'équivalence de son modèle de machine à pointeur SMM :

"Afin d'éviter tout adressage explicite, la RAM0 a l'accumulateur avec le contenu z et un registre d'adresse supplémentaire avec le contenu actuel n (initialement 0)" (p. 494)

Modèle RAM1 : Schönhage démontre comment sa construction peut être utilisée pour former la forme la plus courante et utilisable de RAM de type "successeur" (en utilisant les mnémoniques de cet article):

  • LDA k ; k --> A , k est une constante, un nombre explicite tel que "47"
  • LDA ( d, r ) ; [r] → A ; charger directement A
  • LDA ( i, r ) ; [[r]] → A ; charger indirectement A
  • STA ( d, r ) ; [A] → r ; stocker directement A
  • STA ( i, r ) ; [A] → [r] ; stocker indirectement A
  • JEA ( r, z ) ; IF [A] = [r] then Iz else continue
  • INCA ; [A] + 1 --> A

Modèle RAM0 : La machine RAM0 de Schönhage a 6 instructions indiquées par une seule lettre (le 6ème "C xxx" semble impliquer 'sauter le paramètre suivant'. Schönhage a désigné l'accumulateur avec "z", "N" avec "n", etc. Plutôt que les mnémoniques de Schönhage, nous utiliserons les mnémoniques développés ci-dessus.

  • (Z), CLRA: 0 → A
  • (A), INCA: [A] +1 → A
  • (N), CPYAN: [A] → N
  • (A), LDAA: [[A]] → A ; le contenu de A indique l'adresse d'enregistrement ; mettre le contenu du registre dans A
  • (S), STAN: [A] → [N] ; contenu de N points pour enregistrer l'adresse ; mettre le contenu de A dans le registre pointé par N
  • (C), JAZ ( z ): [A] = 0 then go to Iz ; ambigu dans son traitement

L'indirection provient (i) de CPYAN (copier/transférer le contenu A vers N) travaillant avec store_A_via_N STAN, et de (ii) l'instruction particulière d'indirection LDAA ( [[A]] → [A] ).

Notes de bas de page

Finit vs illimité

Le fait définitionnel que toute sorte de machine de comptage sans registre illimité - registre "d'adresse" doit spécifier un registre "r" par son nom indique que le modèle exige que "r" soit fini , bien qu'il soit "illimité" dans le sens où le modèle n'implique aucune limite supérieure au nombre de registres nécessaires pour faire son travail. Par exemple, nous n'exigeons pas r < 83 617 563 821 029 283 746 ni r < 2^1 000 001, etc.

Ainsi notre modèle peut « étendre » le nombre de registres, si nécessaire pour effectuer un certain calcul. Cependant , cela ne moyenne que quel que soit le numéro du modèle se développe pour doit être fini  - il doit être indexable avec un nombre naturel: ω est pas une option .

Nous pouvons échapper à cette restriction en fournissant un registre non borné pour fournir l'adresse du registre qui spécifie une adresse indirecte.

Voir également

Liens externes

Les références

À quelques exceptions près, ces références sont les mêmes que celles de Register machine .

    • Goldstine, Herman H., et von Neumann, John, "Planning and Coding of the Problems for an Electronic Computing Instrument", Rep. 1947, Institute for Advanced Study , Princeton. Réimprimé aux pages 92–119 dans Bell, C. Gordon et Newell, Allen (1971), Computer Structures: Readings and Examples , McGraw-Hill Book Company, New York. ISBN  0-07-004357-4 }.
  • George Boolos , John P. Burgess , Richard Jeffrey (2002), Calculabilité et logique : quatrième édition , Cambridge University Press, Cambridge, Angleterre. Le texte original de Boolos-Jeffrey a été largement révisé par Burgess : plus avancé qu'un manuel d'introduction. Le modèle « Abacus machine » est largement développé dans le chapitre 5 Abacus Computability ; c'est l'un des trois modèles largement traités et comparés – la machine de Turing (toujours sous la forme originale à 4 tuples de Boolos) et la récursivité les deux autres.
  • Arthur Burks , Herman Goldstine , John von Neumann (1946), Discussion préliminaire sur la conception logique d'un instrument informatique électronique , réimprimé pp. 92ff dans Gordon Bell et Allen Newell (1971), Computer Structures: Readings and Examples , mcGraw-Hill Book Compagnie, New York. ISBN  0-07-004357-4 .
  • Stephen A. Cook et Robert A. Reckhow (1973), Machines à accès aléatoire limité dans le temps , Journal of Computer Systems Science 7(4):354-375.
  • Martin Davis (1958), Calculabilité et insolvabilité , McGraw-Hill Book Company, Inc. New York.
  • Calvin Elgot et Abraham Robinson (1964), Random-Access Stored-Program Machines, an Approach to Programming Languages , Journal de l'Association for Computing Machinery, Vol. 11, n° 4 (octobre 1964), pp. 365-399.
  • J. Hartmanis (1971), "Computational Complexity of Random Access Stored Program Machines," Mathematical Systems Theory 5, 3 (1971) pp. 232-245.
  • John Hopcroft , Jeffrey Ullman (1979). Introduction à la théorie des automates, aux langages et au calcul , 1ère édition, Reading Mass: Addison-Wesley. ISBN  0-201-02988-X . Un livre difficile centré sur les questions d'interprétation machine des "langages", NP-Complétude, etc.
  • Stephen Kleene (1952), Introduction to Metamathematics , North-Holland Publishing Company, Amsterdam, Pays-Bas. ISBN  0-7204-2103-9 .
  • Donald Knuth (1968), L'art de la programmation informatique , deuxième édition 1973, Addison-Wesley, Reading, Massachusetts. Cf pages 462-463 où il définit "un nouveau type de machine abstraite ou 'automate' qui traite des structures liées".
  • Joachim Lambek (1961, reçu le 15 juin 1961), How to Program an Infinite Abacus , Mathematical Bulletin, vol. 4, non. 3. Septembre 1961 pages 295-302. Dans son Annexe II, Lambek propose une "définition formelle du 'programme'. Il fait référence à Melzak (1961) et Kleene (1952) Introduction to Metamathematics .
  • ZA Melzak (1961, reçu le 15 mai 1961), Une approche arithmétique informelle de la calculabilité et du calcul , Bulletin mathématique du Canada , vol. 4, non. 3. Septembre 1961 pages 279-293. Melzak n'offre aucune référence mais reconnaît "l'avantage de conversations avec les Drs R. Hamming, D. McIlroy et V. Vyssots des Bell Telephone Laborators et avec le Dr H. Wang de l'Université d'Oxford".
  • Marvin Minsky (1961). « Insolvabilité récursive du problème de « Tag » de Post et d'autres sujets dans la théorie des machines de Turing ». Annales de mathématiques . Les Annales des Mathématiques, Vol. 74, n° 3. 74 (3) : 437-455. doi : 10.2307/1970290 . JSTOR  1970290 .
  • Marvin Minsky (1967). Calcul: Machines finies et infinies (1ère éd.). Englewood Cliffs, NJ : Prentice-Hall, Inc.Voir en particulier le chapitre 11 : Modèles similaires aux ordinateurs numériques et le chapitre 14 : Bases très simples de calcul . Dans le premier chapitre, il définit les "machines à programme" et dans le dernier chapitre, il traite des "machines à programme universel à deux registres" et "... à un registre", etc.
  • John C. Shepherdson et HE Sturgis (1961) ont reçu en décembre 1961 Computabilité des fonctions récursives , Journal of the Association of Computing Machinery (JACM) 10:217-255, 1963. Un document de référence extrêmement précieux. Dans leur annexe A, les auteurs en citent 4 autres en référence à « Minimalité des instructions utilisées en 4.1 : comparaison avec des systèmes similaires ».
  • Kaphengst, Heinz, Eine Abstrakte programmgesteuerte Rechenmaschine' , Zeitschrift fur mathematische Logik und Grundlagen der Mathematik: 5 (1959), 366-379.
  • Ershov, AP Sur les algorithmes des opérateurs , (russe) Dok. Akad. Nauk 122 (1958), 967-970. Traduction anglaise, Automat. Express 1 (1959), 20-23.
  • Péter, Rózsa Graphschemata und rekursive Funktionen , Dialectica 12 (1958), 373.
  • Hermes, Hans Die Universalität programmgesteuerter Rechenmaschinen. Math.-Phys. Semsterberichte (Göttingen) 4 (1954), 42-53.
  • Arnold Schönhage (1980), Storage Modification Machines , Society for Industrial and Applied Mathematics, SIAM J. Comput. Vol. 9, n° 3, août 1980. Dans lequel Schōnhage montre l'équivalence de son SMM avec le "successeur RAM" (Random Access Machine), etc. resp. Machines de modification de stockage , dans Theoretical Computer Science (1979), pp. 36-37
  • Peter van Emde Boas , "Machine Models and Simulations" pp. 3-66, dans : Jan van Leeuwen , éd. Manuel d'informatique théorique. Volume A : Algorithmes et complexité , The MIT PRESS/Elsevier, 1990. ISBN  0-444-88071-2 (volume A). QA 76.H279 1990. Le traitement des SMM par van Emde Boas apparaît aux pages 32-35. Ce traitement clarifie Schōnhage 1980 – il suit de près mais élargit légèrement le traitement Schōnhage. Les deux références peuvent être nécessaires pour une compréhension efficace.
  • Hao Wang (1957), A Variant to Turing's Theory of Computing Machines , JACM (Journal of the Association for Computing Machinery) 4; 63-92. Présenté à la réunion de l'Association, 23-25 ​​juin 1954.