Circuitos lógicos combinacionales y teoría de la computación

8

Estoy tratando de vincular circuitos lógicos combinacionales (computadoras basadas solo en puertas lógicas) con todo lo que aprendí recientemente en Teoría de la Computación.

Me preguntaba si los circuitos lógicos combinacionales pueden implementar cálculos de la misma manera que las máquinas de estados finitos. Parecen radicalmente diferentes:

Las máquinas de estado finito, sin embargo, tienen una memoria bien definida en la forma de los estados en los que puede estar. Sin embargo, los circuitos lógicos combinacionales no tienen una memoria bien definida, por lo que para implementar algoritmos que necesitan memoria, utilizan un poco método extraño de conexión en serie (vea cómo del sumador anterior está conectado a del sumador actual en la imagen a continuación). CotutCyonorte

Por muy radicalmente diferente que parezca, ambos parecen estar haciendo cálculos. Por ejemplo, ambos pueden implementar un algoritmo para la suma binaria (e incluso la multiplicación binaria) por diferentes que sean esas implementaciones:

FSM:
ingrese la descripción de la imagen aquí

Circuito lógico combinacional (C, como en y , significa Carry):CyonorteCotut
ingrese la descripción de la imagen aquí

Incluso estoy pensando (aunque todavía es muy incierto) que podemos convertir cada FSM en un circuito lógico combinacional correspondiente.

Entonces, me pregunto:

¿Pueden los circuitos lógicos combinacionales también considerarse un tipo instantáneo de modelo de cómputo? ¿Podemos aplicar a él todos los conceptos que aprendemos en la Teoría de la computabilidad y la Teoría de la complejidad computacional, como la complejidad del espacio y la computabilidad?

Por un lado, parece que no encajan como modelo de cómputo porque no tienen operaciones elementales (como lectura / escritura de una cinta, reducción de funciones, pasos en la búsqueda de pruebas del paradigma de programación lógica), implementan sus cálculos instantáneamente
Pero, por otro lado, parecen encajar como un modelo de cómputo porque podemos modelar todo tipo de cómputo con ellos (la adición binaria es un ejemplo), y se pueden ver de manera abstracta (al centrarse solo en las tablas de verdad y las puertas lógicas y olvidarse del circuito físico que podría implementarlo).
Entonces, ¿qué piensan ustedes?

Además, si realmente puede considerarse como un modelo de computación (tipo instantáneo), ¿tienen algún ejemplo de otro modelo de computación similar (también un tipo instantáneo)?

Muchas gracias por adelantado

nerd
fuente
Es posible que desee ver esto: stackoverflow.com/questions/4908893/…
Usuario

Respuestas:

9

Los circuitos lógicos son comunes en la teoría de la complejidad, donde van por los nombres de circuitos . Hay una gran diferencia entre los circuitos y los modelos de cómputo, como la máquina de Turing: cada circuito solo puede manejar entradas de tamaño fijo. Para solucionar esto, bajo el modelo de cálculo de circuito, para cada longitud de entradanorte hay un circuito Cnorte, y juntos calculan una función en cadenas de longitud arbitraria. Este modelo de cálculo, como se indicó, es demasiado fuerte: puede calcular funciones no computables, de hecho todas las funciones. El problema es que una secuencia infinita de circuitos no necesariamente tiene una descripción finita. Para solucionar este problema, generalmente exigimos que los circuitos sean uniformes , es decir, que sean generados por alguna máquina de Turing, que en la entradanorte genera Cnorte.

El modelo de circuito es especialmente popular en la teoría de la complejidad, incluso sin la restricción de uniformidad. La razón es la siguiente observación: una máquina de Turing que funciona en tiempo polinómico se puede convertir en una secuencia (uniforme) de circuitos de tamaño polinómico, utilizando esencialmente las ideas del teorema de Cook (que muestra que SAT es NP-completo). Por lo tanto, si desea demostrar que un cierto problema no puede resolverse en tiempo polinómico, es suficiente para demostrar que no puede resolverse mediante circuitos de tamaño polinómico.

Yuval Filmus
fuente
Creo que entiendo la esencia de esta respuesta. Corríjame si me equivoco: la complejidad temporal de una máquina de Turing limita la complejidad espacial de una máquina de circuito análogo. Pero no entiendo esta afirmación: "El modelo de cálculo [del circuito], como se dijo, es demasiado fuerte: puede calcular funciones no computables, de hecho todas las funciones". ¿El modelo en sí es demasiado fuerte? ¿O su declaración inicial del modelo es más fuerte de lo que es realmente el modelo?
kdbanman
Los circuitos no restringidos son un modelo computacional demasiado fuerte. Debe restringirlos de alguna manera, ya sea restringir su tamaño o estructura, o exigir que sean uniformes, o ambos.
Yuval Filmus
¿Por qué restringir el modelo, sin embargo? ¿A qué restricción deben conformarse? Si son una construcción teórica, ¿no pueden hacer lo que queramos?
kdbanman
Pueden, pero no son útiles para la teoría de la complejidad, ya que pueden calcular todas las funciones posibles.
Yuval Filmus