Circuits logiques combinatoires et théorie du calcul

8

J'essaie de relier les circuits logiques multinationaux (ordinateurs basés uniquement sur des portes logiques) avec tout ce que j'ai appris récemment dans la théorie du calcul.

Je me demandais si les circuits logiques combinatoires peuvent implémenter des calculs de la même manière que les machines à états finis. Ils semblent radicalement différents:

Les machines à états finis, cependant, ont une mémoire bien définie sous la forme des états dans lesquels elle peut se trouver. Les circuits logiques combinatoires, cependant, n'ont pas de mémoire bien définie, donc pour implémenter des algorithmes qui ont besoin de mémoire, ils en utilisent un peu méthode bizarre de connexion série (voir comment Cout de l'additionneur précédent est connecté à Cjen de l'additionneur actuel dans l'image ci-dessous).

Aussi radicalement différents puissent-ils paraître, ils semblent tous deux effectuer des calculs. Par exemple, les deux peuvent implémenter un algorithme pour l'addition binaire (et même la multiplication binaire), mais différentes ces implémentations peuvent être:

FSM:
entrez la description de l'image ici

Circuit logique multinational (C, comme dansCjen et Cout, signifie Carry):
entrez la description de l'image ici

Je pense même (bien que très incertain) que nous pouvons convertir chaque FSM en un circuit logique combiné correspondant.

Alors je me demande:

Les circuits logiques multinationaux peuvent-ils également être considérés comme un type instantané de modèle de calcul? Pouvons-nous lui appliquer tous les concepts que nous apprenons dans la théorie de la calculabilité et la théorie de la complexité informatique, comme la complexité de l'espace et la calculabilité?

D'une part, il semble qu'ils ne conviennent pas comme modèle de calcul car ils n'ont pas d'opérations élémentaires (comme la lecture / écriture d'une bande, la réduction de fonction, les étapes de la recherche de preuve du paradigme de programmation logique), ils implémentent leurs calculs instantanément.
Mais d'un autre côté, ils semblent convenir comme modèle de calcul car nous pouvons modéliser toutes sortes de calculs avec eux (l'addition binaire en est un exemple), et ils peuvent être vus de manière abstraite (en se concentrant uniquement sur les tables de vérité et les portes logiques et oublier le circuit physique qui pourrait le mettre en œuvre).
Alors, qu'en pensez-vous?

De plus, s'il peut en effet être considéré comme un modèle de calcul (de type instantané), avez-vous des exemples d'autres modèles de calcul similaires (également de type instantané)?

Merci beaucoup d'avance

ringard
la source
Vous voudrez peut-être regarder ceci: stackoverflow.com/questions/4908893/…
Utilisateur

Réponses:

9

Les circuits logiques sont courants dans la théorie de la complexité, où ils passent par le nom de circuits . Il existe une grande différence entre les circuits et les modèles de calcul tels que la machine de Turing: chaque circuit ne peut gérer que des entrées de taille fixe. Afin de résoudre ce problème, sous le modèle de calcul de circuit, pour chaque longueur d'entréen il y a un circuit Cn, et ensemble, ils calculent une fonction sur des chaînes de longueur arbitraire. Ce modèle de calcul, comme indiqué, est trop fort: il peut calculer des fonctions non calculables, voire toutes les fonctions. Le problème est qu'une séquence infinie de circuits n'a pas nécessairement une description finie. Afin de résoudre ce problème, nous exigeons généralement que les circuits soient uniformes , c'est-à-dire qu'ils soient générés par une machine de Turing, qui en entréen génère Cn.

Le modèle de circuit est particulièrement populaire dans la théorie de la complexité, même sans restriction d'uniformité. La raison en est l'observation suivante: une machine de Turing fonctionnant en temps polynomial peut être convertie en une séquence (uniforme) de circuits de taille polynomiale, en utilisant essentiellement les idées du théorème de Cook (qui montre que SAT est NP-complet). Par conséquent, si vous voulez prouver qu'un certain problème ne peut pas être résolu en temps polynomial, il suffit de montrer qu'il ne peut pas être résolu par des circuits de taille polynomiale.

Yuval Filmus
la source
Je pense que je comprends l'essentiel de cette réponse. Corrigez-moi si je me trompe: la complexité temporelle d'une machine de Turing limite la complexité spatiale d'une machine de circuit analogue. Mais je ne comprends pas cette affirmation: "Le modèle de calcul [du circuit], comme indiqué, est trop fort: il peut calculer des fonctions non calculables, en fait toutes les fonctions." Le modèle lui-même est trop solide? Ou votre déclaration initiale du modèle est plus forte que le modèle n'est réellement?
kdbanman
Les circuits sans restriction sont un modèle de calcul trop puissant. Vous devez les restreindre d'une manière ou d'une autre - soit restreindre leur taille ou leur structure, soit exiger qu'ils soient uniformes, ou les deux.
Yuval Filmus
Mais pourquoi restreindre le modèle? À quelle contrainte doivent-ils se conformer? S'ils sont une construction théorique, ne peuvent-ils pas faire ce que nous voulons?
kdbanman
Ils le peuvent, mais ils ne sont pas utiles pour la théorie de la complexité, car ils peuvent calculer toutes les fonctions possibles.
Yuval Filmus