Machine à compter

Une machine à compteurs ou un automate à compteurs est une machine abstraite utilisée dans une logique formelle et dans l'informatique théorique pour modéliser le calcul . C'est le plus primitif des quatre types de machines à registres . Une machine à compteurs comprend un ensemble d'un ou plusieurs registres non bornés , chacun pouvant contenir un seul entier non négatif, et une liste d'instructions arithmétiques et de contrôle (généralement séquentielles) que la machine doit suivre. La machine à compteurs est généralement utilisée dans le processus de conception d'algorithmes parallèles en relation avec le principe d'exclusion mutuelle. Lorsqu'elle est utilisée de cette manière, la machine à compteurs est utilisée pour modéliser les pas de temps discrets d'un système de calcul en relation avec les accès à la mémoire. En modélisant les calculs en relation avec les accès à la mémoire pour chaque étape de calcul respective, des algorithmes parallèles peuvent être conçus de manière à éviter le verrouillage, l'opération d'écriture simultanée par deux (ou plusieurs) threads à la même adresse mémoire.

Les machines à compteurs avec trois compteurs peuvent calculer n'importe quelle fonction récursive partielle d'une seule variable. Les machines à compteurs avec deux compteurs sont complètes au sens de Turing : elles peuvent simuler n'importe quelle machine de Turing correctement codée, mais il existe certaines fonctions simples qu'elles ne peuvent pas calculer. Les machines à compteurs avec un seul compteur peuvent reconnaître un sur-ensemble approprié des langages réguliers et un sous-ensemble des langages déterministes sans contexte .

Pour un modèle de machine à compteur donné, le jeu d'instructions est minuscule, d'une à six ou sept instructions seulement. La plupart des modèles contiennent quelques opérations arithmétiques et au moins une opération conditionnelle (si la condition est vraie, alors sautez). Trois modèles de base , chacun utilisant trois instructions, sont tirés de la collection suivante. (Les abréviations sont arbitraires.)

• CLR (r) : CLeaR le registre r . (Définir r à zéro.)
• INC (r) : incrémente le contenu du registre r .
• DEC(r) : DECremment le contenu du registre r .
• CPY (r _j , _rk ) : Copie le contenu du registre r _j dans le registre _rk en laissant le contenu de r _j intact.
• JZ (r, z) : SI le registre r contient zéro ALORS passer à l'instruction z SINON continuer en séquence.
• JE (r _j , r _k , z) : SI le contenu du registre r _j est égal au contenu du registre r _k ALORS passer à l'instruction z SINON continuer en séquence.

De plus, une machine dispose généralement d'une instruction HALT, qui arrête la machine (normalement après que le résultat a été calculé).

En utilisant les instructions mentionnées ci-dessus, divers auteurs ont discuté de certaines machines de comptage :

• ensemble 1 : { INC (r), DEC (r), JZ (r, z) }, (Minsky (1961, 1967), Lambek (1961))
• ensemble 2 : { CLR (r), INC (r), JE (r _j , r _k , z) }, (Ershov (1958), Peter (1958) tel qu'interprété par Shepherdson–Sturgis (1964) ; Minsky (1967) ; Schönhage (1980))
• ensemble 3 : { INC (r), CPY (r _j , r _k ), JE (r _j , r _k , z) }, (Elgot-Robinson (1964), Minsky (1967))

Les trois modèles de base de machines à compteurs ont la même puissance de calcul puisque les instructions d'un modèle peuvent être dérivées de celles d'un autre. Tous sont équivalents à la puissance de calcul des machines de Turing . En raison de leur style de traitement unaire, les machines à compteurs sont généralement exponentiellement plus lentes que les machines de Turing comparables.

Les modèles de machines de comptage portent plusieurs noms différents qui peuvent aider à les distinguer par leurs particularités. Dans ce qui suit, l'instruction "JZDEC(r)" est une instruction composée qui teste si un registre r est vide ; si c'est le cas, passez à l'instruction Iz _, sinon, si ce n'est pas le cas, DECremment le contenu de r :

• Machine de Shepherdson–Sturgis , car ces auteurs ont formellement énoncé leur modèle dans une exposition facilement accessible (1963). Utilise le jeu d'instructions (1) augmenté d'instructions de commodité supplémentaires (JNZ signifie "Jump if Not Zero", utilisé à la place de JZ) :

  { INC ( r ), DEC ( r ), CLR ( r ), CPY ( r _j , rk ₎ , JNZ ( r, z ), J ( z ) }

• Machine de Minsky , car Marvin Minsky (1961) a formalisé le modèle. Utilise généralement le jeu d'instructions (1), mais l'exécution des instructions n'est pas séquentielle par défaut, donc le paramètre supplémentaire « z » semble spécifier l'instruction suivante après INC et comme alternative dans JZDEC :

  { INC ( r, z ), JZDEC ( r, z _vrai , z _faux ) }

• Machine à programmer , ordinateur à programmer , les noms que Minsky (1967) a donné au modèle car, comme un ordinateur, ses instructions se déroulent de manière séquentielle à moins qu'un saut conditionnel ne réussisse. Utilise (généralement) le jeu d'instructions (1) mais peut être augmenté de manière similaire au modèle Shepherson–Sturgis. JZDEC est souvent divisé en deux :

  { INC ( r ), DEC ( r ), JZ ( r, z _vrai )}

• Machine à boulier , nom donné par Lambek (1961) à sa simplification du modèle de Melzak (1961), et ainsi que Boolos–Burgess–Jeffrey (2002) l'appelle. Utilise le jeu d'instructions (1) mais avec un paramètre supplémentaire z pour spécifier l'instruction suivante à la manière du modèle de Minsky (1961) ;

  { INC ( r, z ), JZDEC (r, z _vrai , z _faux ) }

• Machine de Lambek , un autre nom donné par Boolos–Burgess–Jeffrey (2002) à la machine à boulier. Utilise un jeu d'instructions (réduit à 1) avec un paramètre supplémentaire pour spécifier l'instruction suivante :

  { INC ( r, z ), JZDEC ( r, z _vrai , z _faux ) }

• Machine successeur , car elle utilise l'opération successeur des axiomes de Peano et y ressemble beaucoup. Utilisée comme base pour le modèle de RAM successeur . Utilise le jeu d'instructions (2) de Schönhage, par exemple, comme base pour ses modèles RAM0 et RAM1 qui conduisent à son modèle de machine à pointeurs SMM, également brièvement discuté dans van Emde Boas (1990) :

  { CLR ( r ), INC ( r ), JE ( r _j , r _k , z ) }

• Modèle d'Elgot–Robinson , utilisé pour définir leur modèle RASP (1964). Ce modèle nécessite un registre vide au départ (par exemple [r0] = 0). (Ils ont complété le même modèle avec un adressage indirect en utilisant un registre supplémentaire à utiliser comme registre « d'index ».)

  { INC (r), CPY ( rs _, rd ₎ , JE ( rj _, rk _, z ) }

• Autres machines à compter : Minsky (1967) montre comment construire les trois modèles de base (programme/Minsky/Lambek-abacus, successeur et Elgot–Robinson) à partir du sur-ensemble d'instructions disponibles décrites dans le premier paragraphe de cet article. Le modèle de Melzak (1961) est assez différent du précédent car il inclut « ajouter » et « soustraire » plutôt qu'« incrémenter » et « décrémenter ». Les preuves de Minsky (1961, 1967) selon lesquelles un seul registre suffira pour l'équivalence de Turing nécessitent les deux instructions { MULtiply k, et DIV k } pour encoder et décoder le nombre de Gödel dans le registre qui représente le calcul. Minsky montre que si deux ou plusieurs registres sont disponibles, les plus simples INC, DEC etc. sont adéquats (mais le nombre de Gödel est toujours nécessaire pour démontrer l'équivalence de Turing ; également démontré dans Elgot–Robinson 1964).

Une machine de comptage se compose de :

1. Registres étiquetés à valeur entière non bornée : un ensemble fini (ou infini dans certains modèles) de registres r ₀ ... r _n dont chacun peut contenir n'importe quel entier non négatif (0, 1, 2, ... - c'est-à-dire non borné). Les registres effectuent leur propre arithmétique ; il peut y avoir ou non un ou plusieurs registres spéciaux, par exemple un « accumulateur » (voir Machine à accès aléatoire pour plus d'informations à ce sujet).
2. Un registre d'état qui stocke/identifie l'instruction en cours à exécuter. Ce registre est fini et distinct des registres ci-dessus ; ainsi, le modèle de machine à compteur est un exemple de l' architecture Harvard
3. Liste d'instructions séquentielles étiquetées : Liste finie d'instructions I ₀ ... I _m . Le magasin de programmes (instructions de la machine à états finis ) ne se trouve pas dans le même « espace » physique que les registres. En général, mais pas toujours, comme dans les programmes informatiques , les instructions sont répertoriées dans l'ordre séquentiel ; à moins qu'un saut ne réussisse, la séquence par défaut continue dans l'ordre numérique. Chacune des instructions de la liste provient d'un (très) petit ensemble, mais cet ensemble n'inclut pas l'indirection. Historiquement, la plupart des modèles tiraient leurs instructions de cet ensemble :

{ Incrémenter (r), Décrémenter (r), Effacer (r); Copier (r _j ,r _k ), Saut conditionnel si le contenu de r=0, Saut conditionnel si r _j =r _k , Saut inconditionnel, ARRÊT }

Certains modèles ont soit atomisé davantage certaines des instructions ci-dessus en instructions sans paramètre, soit les ont combinées en une seule instruction telle que « Decrement » précédée d'un saut conditionnel à zéro « JZ(r,z) ». L'atomisation des instructions ou l'inclusion d'instructions de commodité n'entraîne aucun changement dans la puissance conceptuelle, car tout programme d'une variante peut être directement traduit dans l'autre.

Des jeux d'instructions alternatifs sont décrits dans le supplément Modèles de machines à registres .

Cet exemple montre comment créer trois autres instructions utiles : clear , unconditional jump et copy .

• CLR ( j ) : Efface le contenu du registre r _j à zéro.
• J ( z ) : Saut inconditionnel vers l'instruction I _z .
• CPY ( s, d ) : Copie le contenu du registre source r _s vers le registre de destination r _d . (Voir Ordinateur à un jeu d'instructions#Architecture déclenchée par transport )

Par la suite, r _s contiendra son compte d'origine (contrairement à MOVE qui vide le registre source, c'est-à-dire le remet à zéro).

L'ensemble de base (1) est utilisé tel que défini ici :

Instruction	Effet sur le registre « j »	Effet sur le registre du compteur d'instructions ICR	Résumé
INC ( j )	[j] +1 → j	[IC] +1 → IC	Incrémenter le contenu du registre j ; instruction suivante
DÉC ( j )	[j] -1 → j	[IC] +1 → IC	Décrémenter le contenu du registre j ; instruction suivante
JZ (j, z)		SI [j] = 0 ALORS I z → IC SINON [IC] +1 → IC	Si le contenu du registre j=0 alors instruction z sinon instruction suivante
ARRÊT

Au départ, le registre n°2 contient « 2 ». Les registres n°0, n°1 et n°3 sont vides (contiennent « 0 »). Le registre n°0 reste inchangé tout au long des calculs car il est utilisé pour le saut inconditionnel. Le registre n°1 est un bloc-notes. Le programme commence par l'instruction 1.

Le programme s'arrête avec le contenu du registre n°2 à son compte d'origine et le contenu du registre n°3 égal au contenu d'origine du registre n°2, c'est-à-dire,

[2] = [3].

Le programme COPY ( #2, #3) comporte deux parties. Dans la première partie, le programme déplace le contenu du registre source #2 vers le bloc-notes #1 et vers le registre de destination #3 ; ainsi, #1 et #3 seront des copies l'une de l'autre et du compte original dans #2, mais #2 est effacé lors du processus de décrémentation à zéro. Les sauts inconditionnels J (z) sont effectués par des tests du registre #0, qui contient toujours le nombre 0 :

[#2] →#3 ; [#2] →#1 ; 0 →#2

Dans la deuxième partie, le programme déplace (renvoie, restaure) le contenu du bloc-notes n°1 vers le n°2, effaçant ainsi le bloc-notes n°1 :

[#1] →#2; 0 →#1

Le programme, surligné en jaune, est affiché écrit de gauche à droite en haut à droite.

Une « exécution » du programme est présentée ci-dessous. Le temps s'écoule sur la page. Les instructions sont en jaune, les registres en bleu. Le programme est inversé à 90 degrés, avec les numéros d'instruction (adresses) en haut, les mnémoniques d'instruction sous les adresses et les paramètres d'instruction sous les mnémoniques (un par cellule) :

															1	2	3	4	5	6	7	8	9	10	← Numéro d'instruction (adresse)
															JZ	DÉC	INC	INC	JZ	JZ	DÉC	INC	JZ	H	← Instructions
															2	2	3	1	0	1	1	2	0		← Numéro de registre
															6				1	10			6		← Passer au numéro d'instruction
étape		CI	Inst #	enregistrement #	J-adr		reg0	reg1	reg2	reg3	reg4		CI
commencer							0	0	2	0	0		1												déplacer [#2] vers #1 et #3 :
1		1	JZ	2	6		0	0	2	0	0		1→2		JZ										Le saut échoue : le registre n° 2 contient 2
2		2	DÉC	2	0		0	0	2→1	0	0		2→3			DÉC									Décrémenter le registre n°2 de 2 à 1
3		3	INC	3	0		0	0	1	0→1	0		3→4				INC								Incrémenter le registre n°3 de 0 à 1
4		4	INC	1	0		0	0→1	1	1	0		4→5					INC							Incrémenter le registre n°1 de 0 à 1
5		5	JZ	0	1		0	1	1	1	0		5→1						JZ						U-Jump : le registre #0 est vide
6		1	JZ	2	6		0	1	1	1	0		1→2		JZ										Le saut échoue : le registre n° 2 contient 1
7		2	DÉC	2	0		0	1	1→0	1	0		2→3			DÉC									Décrémenter le registre n°2 de 1 à 0
8		3	INC	3	0		0	1	0	1→2	0		3→4				INC								Incrémenter le registre n°3 de 1 à 2
9		4	INC	1	0		0	1→2	0	2	0		4→5					INC							Incrémenter le registre n°1 de 1 à 2
10		5	JZ	0	1		0	2	0	2	0		5→1						JZ						U-Jump : le registre #0 est vide
11		1	JZ	2	6		0	2	0	2	0		1→6		JZ										Saut ! : le registre n°2 est vide
																									déplacer [1] vers 2 :
12		6	JZ	1	10		0	2	0	2	0		6→7							JZ					Le saut échoue : le registre n°1 contient 2
13		7	DÉC	1	0		0	2→1	0	2	0		7→8								DÉC				Décrémenter le registre n°1 de 2 à 1
14		8	INC	2	0		0	1	0→1	2	0		8→9									INC			Incrémenter le registre n°2 de 0 à 1
15		9	JZ	0	6		0	1	1	2	0		9→6										JZ		U-Jump : le registre #0 est vide
16		6	JZ	1	10		0	1	1	2	0		6→7							JZ					Le saut échoue : le registre n°1 contient 1
17		7	DÉC	1	0		0	1→0	1	2	0		7→8								DÉC				Décrémenter le registre n°1 de 1 à 0
18		8	INC	2	0		0	0	1→2	2	0		8→9									INC			Incrémenter le registre n°2 de 1 à 2
19		9	JZ	0	6		0	0	2	2	0		9→6										JZ		U-Jump : le registre #0 est vide
20		6	JZ	1	10		0	0	2	2	0		6→10							JZ					Saut ! : le registre n°1 est vide
21		10	H	0	0		0	0	2	2	0		10→10											H	ARRÊT

L'exemple ci-dessus montre comment les premières instructions de base { INC, DEC, JZ } peuvent créer trois instructions supplémentaires : saut inconditionnel J, CLR, CPY. Dans un sens, CPY utilise à la fois CLR et J plus l'ensemble de base. Si le registre n°3 avait eu un contenu au départ, la somme du contenu de n°2 et n°3 aurait fini dans n°3. Donc, pour être tout à fait précis, le programme CPY aurait dû précéder ses déplacements de CLR (1) et CLR (3).

Cependant, nous voyons que l'ADD aurait été possible, facilement. Et en fait, ce qui suit est un résumé de la façon dont les fonctions récursives primitives telles que ADD, MULtiply et EXPonent peuvent être créées (voir Boolos–Burgess–Jeffrey (2002) p. 45-51).

• Ensemble d'instructions de début : { DEC, INC, JZ, H }
• Définir le « Saut J (z) » inconditionnel en termes de JZ ( r0, z ) étant donné que r0 contient 0.

{ J, DEC, INC, JZ, H }

• Définissez « CLeaR(r) » en fonction de ce qui précède :

{ CLR, J, DEC, INC, JZ, H }

• Définissez « CoPY ( r _j , r _k ) » tout en préservant le contenu de r _j en termes de ce qui précède :

{ CPY, CLR, J, DEC, INC, JZ, H }

Ce qui précède est l’ensemble d’instructions de Shepherdson–Sturgis (1963).

• Définissez « ADD ( r _j , _rk , r _i ) », (en préservant éventuellement le contenu de r _j et _rk ), en utilisant ce qui précède :

{ AJOUTER, CPY, CLR, J, DÉC, INC, JZ, H }

• Définissez « MULtiply ( r _j , r _k , r _i ) » (MUL) (en préservant peut-être le contenu de r _j , r _k ), en termes de ce qui précède :

{ MUL, ADD, CPY, CLR, J, DÉC, INC, JZ, H }

• Définir « EXPonentiel ( r _j , _rk , r _i ) » (EXP) (en préservant peut-être le contenu de r _j , rk ₎ en termes de ce qui précède,

{ EXP, MUL, AJOUTER, COMPTER, CLR, J, DÉC, INC, JZ, H }

En général, nous pouvons construire n'importe quelle fonction récursive primitive partielle ou totale que nous souhaitons, en utilisant les mêmes méthodes. En effet, Minsky (1967), Shepherdson–Sturgis (1963) et Boolos–Burgess–Jeffrey (2002) montrent comment former les cinq « opérateurs » de fonctions récursives primitives (1 à 5 ci-dessous) à partir de l'ensemble de base (1).

Mais qu'en est-il de l'équivalence totale de Turing ? Il faut ajouter le sixième opérateur, l' opérateur μ , pour obtenir l'équivalence totale, capable de créer les fonctions récursives totales et partielles :

1. Fonction zéro (ou fonction constante)
2. Fonction successeur
3. Fonction d'identité
4. Fonction de composition
5. Récursivité primitive (induction)
6. Opérateur μ (opérateur de recherche non borné)

Les auteurs montrent que cela est facilement réalisable dans n'importe lequel des ensembles de base disponibles (1, 2 ou 3) (un exemple peut être trouvé dans l'opérateur μ ). Cela signifie que toute fonction récursive mu peut être implémentée comme une machine à compteurs, malgré le jeu d'instructions fini et la taille du programme de la conception de la machine à compteurs. Cependant, la construction requise peut être contre-intuitive, même pour des fonctions relativement faciles à définir dans des machines à registres plus complexes telles que la machine à accès aléatoire . En effet, l'opérateur μ peut itérer un nombre illimité de fois, mais une machine à compteurs donnée ne peut pas adresser un nombre illimité de registres distincts en raison de la taille finie de sa liste d'instructions.

Par exemple, la hiérarchie ci-dessus des opérateurs récursifs primitifs peut être étendue au-delà de l'exponentiation dans les opérations de flèches d'ordre supérieur dans la notation de flèche vers le haut de Knuth . Pour tout , la fonction est récursive primitive et peut être implémentée comme une machine à compteurs de manière simple. Mais la fonction n'est pas récursive primitive. On peut être tenté d'implémenter l'opérateur de flèche vers le haut en utilisant une construction similaire aux instructions de successeur, d'addition, de multiplication et d'exponentiation ci-dessus, en implémentant une pile d'appels afin que la fonction puisse être appliquée de manière récursive sur des valeurs plus petites de . Cette idée est similaire à la façon dont on peut implémenter la fonction en pratique dans de nombreux langages de programmation. Cependant, la machine à compteurs ne peut pas utiliser un nombre illimité de registres dans son calcul, ce qui serait nécessaire pour implémenter une pile d'appels qui peut devenir arbitrairement grande. L'opération de flèche vers le haut peut toujours être implémentée comme une machine de comptage car elle est très récursive, cependant la fonction serait implémentée en codant une quantité illimitée d'informations dans un nombre fini de registres, comme en utilisant la numérotation de Gödel .

Les problèmes sont discutés en détail dans l'article Random-access machine . Les problèmes se répartissent en deux grandes catégories et une troisième catégorie « d'inconvénients » :

(1) Capacités illimitées des registres versus capacités limitées des instructions de la machine à états : comment la machine va-t-elle créer des constantes supérieures à la capacité de sa machine à états finis ?

(2) Nombre illimité de registres versus nombre limité d'instructions de machine à états : comment la machine accédera-t-elle aux registres avec des numéros d'adresses hors de portée/capacité de sa machine à états finis ?

(3) Les modèles entièrement réduits sont encombrants :

Shepherdson et Sturgis (1963) ne s'embarrassent pas de leur jeu d'instructions à 6. Ils ont fait leur choix en se basant sur « la facilité de programmation... plutôt que sur l'économie » (p. 219 note de bas de page 1).

Instructions de Shepherdson et Sturgis ([r] indique « contenu du registre r ») :

• • INCRÉMENT ( r ) ; [r] +1 → r
  • DÉCRÉMENTATION ( r ) ; [r] -1 → r
  • CLAIR ( r ) ; 0 → r
  • COPIE ( r _s à r _d ) ; [ r _s ] → r _d
  • SAUT INCONDITIONNEL à l'instruction I _z
  • SAUTER SI [r] = 0 à l'instruction I _z

Minsky (1967) a étendu son jeu de 2 instructions { INC (z), JZDEC (r, I _z ) } à { CLR (r), INC (r), JZDEC (r, I _z ), J (I _z ) } avant sa preuve qu'une « machine à programme universelle » peut être construite avec seulement deux registres (p. 255 et suivantes).

Pour chaque machine de Turing , il existe une machine 2CM qui la simule, à condition que l'entrée et la sortie de la machine 2CM soient correctement codées. Ceci est prouvé dans le livre de Minsky ( Computation , 1967, p. 255-258), et une preuve alternative est esquissée ci-dessous en trois étapes. Tout d'abord, une machine de Turing peut être simulée par une machine à états finis (FSM) équipée de deux piles. Ensuite, deux piles peuvent être simulées par quatre compteurs. Enfin, quatre compteurs peuvent être simulés par deux compteurs. La machine à deux compteurs utilise l'ensemble d'instructions { INC ( r, z ), JZDEC ( r, z _true , z _false ) }.

Une machine de Turing se compose d'un FSM et d'une bande infinie, initialement remplie de zéros, sur laquelle la machine peut écrire des uns et des zéros. À tout moment, la tête de lecture/écriture de la machine pointe vers une cellule de la bande. Cette bande peut être conceptuellement coupée en deux à ce stade. Chaque moitié de la bande peut être considérée comme une pile , où le haut est la cellule la plus proche de la tête de lecture/écriture, et le bas est à une certaine distance de la tête, avec tous les zéros sur la bande au-delà du bas. En conséquence, une machine de Turing peut être simulée par un FSM plus deux piles. Déplacer la tête vers la gauche ou vers la droite équivaut à extraire un bit d'une pile et à le pousser sur l'autre. Écrire équivaut à changer le bit avant de le pousser.

Une pile contenant des zéros et des uns peut être simulée par deux compteurs lorsque les bits de la pile sont considérés comme représentant un nombre binaire (le bit le plus haut de la pile étant le bit le moins significatif). Pousser un zéro sur la pile équivaut à doubler le nombre. Pousser un un équivaut à doubler et ajouter 1. Faire sauter équivaut à diviser par 2, où le reste est le bit qui a été fait sauter. Deux compteurs peuvent simuler cette pile, dans laquelle l'un des compteurs contient un nombre dont la représentation binaire représente les bits de la pile, et l'autre compteur est utilisé comme bloc-notes. Pour doubler le nombre du premier compteur, le FSM peut initialiser le deuxième compteur à zéro, puis décrémenter à plusieurs reprises le premier compteur une fois et incrémenter le deuxième compteur deux fois. Cela continue jusqu'à ce que le premier compteur atteigne zéro. À ce stade, le deuxième compteur contiendra le nombre doublé. La réduction de moitié est effectuée en décrémentant un compteur deux fois et en incrémentant l'autre une fois, et en répétant jusqu'à ce que le premier compteur atteigne zéro. Le reste peut être déterminé par le fait qu'il a atteint zéro après un nombre pair ou impair d'étapes, où la parité du nombre d'étapes est codée dans l'état du FSM.

Comme précédemment, l'un des compteurs est utilisé comme bloc-notes. L'autre contient un entier dont la factorisation première est 2 ^a 3 ^b 5 ^c 7 ^d . Les exposants a , b , c et d peuvent être considérés comme quatre compteurs virtuels qui sont regroupés (via la numérotation de Gödel ) dans un seul compteur réel. Si le compteur réel est mis à zéro puis incrémenté une fois, cela équivaut à mettre tous les compteurs virtuels à zéro. Si le compteur réel est doublé, cela équivaut à incrémenter a , et s'il est divisé par deux, cela équivaut à décrémenter a . Par une procédure similaire, il peut être multiplié ou divisé par 3, ce qui équivaut à incrémenter ou décrémenter b . De même, c et d peuvent être incrémentés ou décrémentés. Pour vérifier si un compteur virtuel tel que c est égal à zéro, il suffit de diviser le compteur réel par 5, de voir quel est le reste, puis de multiplier par 5 et d'ajouter le reste. Cela laisse le compteur réel inchangé. Le reste aurait été différent de zéro si et seulement si c était nul.

En conséquence, un FSM avec deux compteurs peut simuler quatre compteurs, qui simulent à leur tour deux piles, qui simulent une machine de Turing. Par conséquent, un FSM plus deux compteurs est au moins aussi puissant qu'une machine de Turing. Une machine de Turing peut facilement simuler un FSM avec deux compteurs, les deux machines ont donc une puissance équivalente.

Ce résultat, ainsi qu'une liste d'autres fonctions de N qui ne sont pas calculables par une machine à deux compteurs — lorsqu'elles sont initialisées avec N dans un compteur et 0 dans l'autre — telles que N ² , sqrt( N ), log ₂ ( N ), etc., apparaît dans un article de Schroeppel (1972). Le résultat n'est pas surprenant, car le modèle de la machine à deux compteurs a été prouvé (par Minsky) comme étant universel uniquement lorsque l'argument N est codé de manière appropriée (par Gödelization) pour simuler une machine de Turing dont la bande initiale contient N codé en unaire ; de plus, la sortie de la machine à deux compteurs sera codée de manière similaire. Ce phénomène est typique des très petites bases de calcul dont l'universalité n'est prouvée que par simulation (par exemple, de nombreux tarpits de Turing , les plus petites machines de Turing universelles connues , etc.).

La preuve est précédée de quelques théorèmes intéressants :

• « Théorème : Une machine à trois compteurs peut simuler une machine de Turing » (p. 2, cf. aussi Minsky 1967 : 170-174)
• "Théorème : Une machine à trois compteurs peut calculer n'importe quelle fonction récursive partielle d'une variable. Elle commence avec l'argument [c'est-à-dire N ] dans un compteur, et (si elle s'arrête) laisse la réponse [c'est-à-dire F( N )] dans un compteur." (p. 3)
• « Théorème : Une machine à compteurs peut être simulée par une 2CM [machine à deux compteurs], à condition qu'un codage obscur soit accepté pour l'entrée et la sortie » [p. 3 ; le « codage obscur » est : 2 ^W 3 ^X 5 ^Y 7 ^Z où les compteurs simulés sont W, X, Y, Z]
• « Théorème : Toute machine à compteur peut être simulée par un 2CM, à condition qu'un codage obscur soit accepté pour l'entrée et la sortie. » (p. 3)
  • « Corollaire : le problème d’arrêt des 2CM est insoluble.
  • "Corollaire : un 2CM peut calculer n'importe quelle fonction récursive partielle d'un argument, à condition que l'entrée soit codée comme 2 ^N et que la sortie (si la machine s'arrête) soit codée comme 2 ^réponse ." (p. 3)
• « Théorème : Il n'existe pas de machine à deux compteurs qui calcule 2 ^N [si un compteur est initialisé à N ] » (p. 11)

En ce qui concerne le deuxième théorème selon lequel « une machine à 3 compteurs peut calculer n'importe quelle fonction récursive partielle », l'auteur lance au lecteur un « problème difficile : multiplier deux nombres en utilisant seulement trois compteurs » (p. 2). La principale preuve repose sur l'idée que les machines à deux compteurs ne peuvent pas calculer de séquences arithmétiques avec des taux de croissance non linéaires (p. 15), c'est-à-dire que « la fonction 2 ^X croît plus rapidement que n'importe quelle progression arithmétique » (p. 11).

La calculatrice Friden EC-130 n'avait pas de logique additionneuse en tant que telle. Sa logique était hautement sérielle, effectuant l'arithmétique en comptant. En interne, les chiffres décimaux étaient en base 1 — par exemple, un six était représenté par six impulsions consécutives dans l'intervalle de temps alloué à ce chiffre. Chaque intervalle de temps comportait un chiffre, le moins significatif en premier. Les retenues définissaient une bascule qui provoquait l'ajout d'un compte au chiffre dans l'intervalle de temps suivant.

L'addition était effectuée par un compteur ascendant, tandis que la soustraction était effectuée par un compteur descendant, avec un schéma similaire pour traiter les emprunts.

Le schéma de créneaux horaires définissait six registres de 13 chiffres décimaux, chacun avec un bit de signe. La multiplication et la division se faisaient essentiellement par addition et soustraction répétées. La version à racine carrée, l'EC-132, soustrayait efficacement des entiers impairs consécutifs, chaque décrément nécessitant deux soustractions consécutives. Après la première, le minuend était incrémenté d'une unité avant la deuxième soustraction.