Mientras era estudiante de EE asistí a algunas conferencias que presentaban una buena caracterización de los circuitos booleanos en términos de cuántos bucles anidados tienen. En complejidad, los circuitos booleanos a menudo se consideran dags, pero en los ciclos reales de hardware son comunes. Ahora, modulo algunos tecnicismos con respecto a qué es un bucle y qué constituye un bucle anidado, la afirmación era básicamente que para implementar en hardware un autómata se necesitan dos bucles anidados, y para implementar un procesador se necesitan tres bucles anidados. (Podría estar fuera de uno con estos recuentos).
Dos cosas me molestan:
- No había nada como una prueba formal.
- No vi esto en ningún otro lado.
¿Alguien investigó declaraciones precisas de este tipo?
Al buscar el nombre del profesor, encontré una pequeña página web y un libro (Capítulo 4) que analizan esta taxonomía.
Tipo de antecedentes : en caso de que se pregunte por qué los ciclos son útiles en el hardware real, aquí hay un ejemplo simple. Conecte dos inversores en un ciclo. (Un inversor es una puerta que calcula la función booleana NO). Este circuito tiene dos equilibrios estables (y uno inestable). En ausencia de cualquier intervención externa, el circuito simplemente permanecerá en uno de los dos estados. Sin embargo, es posible forzar el circuito a un estado particular aplicando una señal externa. La situación puede verse así: mientras el ciclo está conectado a la señal externa "leemos la entrada", y de lo contrario simplemente "recordamos el último valor que vimos". Entonces, un bucle nos ayuda a recordar cosas.
Respuestas:
Debería echar un vistazo a la tesis doctoral (más tarde publicada como una monografía) de Tomás Feder: Redes estables y gráficos de productos , donde estudió la complejidad de encontrar configuraciones estables de redes , que son exactamente circuitos con "bucles" como usted mencionó.
fuente