Connexion entre les portes NAND et l'exhaustivité de Turing

Je sais que les portes NAND peuvent être utilisées pour créer des circuits qui implémentent chaque table de vérité, et les ordinateurs modernes sont constitués de portes NAND. Quel est le lien théorique entre les portes NAND et l'exhaustivité de Turing? Il me semble que les circuits de porte NAND sont plus proches des automates finis que les machines de Turing. Mon intuition est que je peux construire des bascules, et donc des registres et de la mémoire, à partir de portes NAND, et la mémoire illimitée est une propriété cruciale des systèmes complets de Turing. Je cherche une explication plus théorique ou mathématique, ou des conseils sur ce qu'il faut lire.

turing-machines turing-completeness digital-circuits bsm
la source

"Les ordinateurs modernes sont constitués de portes NAND" Je suis presque sûr que c'est faux. Les bibliothèques de cellules typiques pour les conceptions numériques contiennent des dizaines et non des centaines de portes et leur fonction varie (recherchez les portes AOI) ainsi que les entrées et sorties.

Programmeur

Vous avez raison, je voulais dire dans un sens théorique que toute la logique numérique peut être constituée de NANDS, qui sont considérés comme fonctionnellement complets

bsm

Réponses:

Il y a en effet peu de connexion. Pour une compréhension approfondie, permettez-moi d'expliquer le lien entre les programmes et les circuits .

Un programme (ou algorithme ou machine ) est un mécanisme de calcul d'une fonction. Pour être précis, supposons que l' entrée est une chaîne binaire et que la sortie est une sortie booléenne . La taille de l'entrée est potentiellement illimitée. Un exemple est un programme qui détermine si l'entrée est le codage binaire d'un nombre premier. $x$ $b$

Un circuit (booléen) est une collection d'instructions pour calculer une fonction finie . Nous pouvons imaginer le circuit comme un circuit électrique, ou le considérer comme une séquence d'instructions (cette vue est appelée confusément un programme en ligne droite ). Concrètement, nous pouvons supposer que l' entrée est une chaîne binaire de longueur et que la sortie est booléenne. Un exemple est un circuit qui détermine si l'entrée code pour un nombre premier (comme auparavant, seulement maintenant l'entrée doit être de longueur ). $x$ $n$ $n$

On peut convertir un programme en un circuit qui simule sur des entrées de longueur . La séquence correspondante des circuits n'est pas arbitraire - ils peuvent tous être construits par un programme qui a donné sorties . Nous appelons une telle séquence de circuits un circuit uniforme (de manière confuse, nous considérons souvent la séquence comme un circuit "unique" pour un indéfini ). $P$ $P_n$ $P$ $n$ $P_0,P_1,P_2,\ldots$ $n$ $P_n$ $P_n$ $n$

Toutes les séquences de circuits ne sont pas uniformes. En effet, une séquence de circuits peut calculer toutes les fonctions, des chaînes aux booléens, calculables ou non calculables! Néanmoins, dans la théorie de la complexité, nous nous intéressons à de tels modèles non uniformes dans lesquels les circuits sont restreints. Par exemple, la question P = NP indique que les problèmes NP-complets ne peuvent pas être résolus par des algorithmes de temps polynomiaux. Cela implique que les problèmes NP-complets ne peuvent pas être résolus par des circuits uniformes de taille polynomiale. On suppose en outre que les problèmes NP-complets ne peuvent pas être résolus par des circuits de taille polynomiale sans l'exigence d'uniformité .

Les modèles de calcul complets de Turing sont des modèles qui réalisent toutes les fonctions calculables (et pas plus). En revanche, des systèmes complets de portes (tels que AND, OR, NOT ou NAND) permettent de calculer des fonctions finies arbitraires en utilisant des circuits constitués de ces portes. De tels systèmes complets peuvent calculer des fonctions complètement arbitraires en utilisant des séquences (illimitées) de circuits.

Yuval Filmus
la source

Pouvez-vous expliquer "une séquence de circuits peut calculer toutes les fonctions, des chaînes aux booléens, calculables ou non calculables"? Leur capacité à calculer des fonctions non calculables (du point de vue de l'intégralité de Turing) provient-elle de la restriction de la taille d'entrée?

bsm

n

$n$

n

$n$

Pouvez-vous expliquer cela, @YuvalFilmus? Il semble étrange qu'une fonction non calculable telle que la complexité de Kolmogorov soit soudainement "calculable" en utilisant des circuits.

Cort Ammon

f

$f$

n

$n$

Vous avez en fait raison. Un circuit logique combinatoire équivaut à un automate fini. Les portes NAND ne les rendent pas plus puissantes; ils sont utilisés parce qu'il est tout simplement moins cher de construire un circuit logique numérique avec un seul type de porte que de le construire avec toutes les portes différentes. En fait, une porte NAND peut être construite à partir d'une seule porte ET et d'une porte NON. Les tongs rendent le circuit de Turing complet. Voici une clé pratique:

Circuits combinés ~ Automates finis ~ Langues régulières ~ Expressions régulières ~ Calcul propositionnel ~ Programmes en ligne droite

$\mu$

Si vous voulez en savoir plus, il y a un très bon livre que vous pouvez télécharger gratuitement au format PDF qui explique tout cela:

https://cs.brown.edu/people/jes/book/pdfs/ModelsOfComputation.pdf

user628544
la source