Sé que las compuertas NAND se pueden usar para crear circuitos que implementen todas las tablas de verdad, y las computadoras modernas se componen de compuertas NAND. ¿Cuál es el vínculo teórico entre las puertas NAND y la integridad de Turing? Me parece que los circuitos de compuerta NAND están más cerca de autómatas finitos que las máquinas Turing. Mi intuición es que puedo construir chanclas, y por lo tanto registros y memoria, fuera de las puertas NAND, y la memoria sin límites es una propiedad crucial de los sistemas completos de Turing. Estoy buscando una explicación más teórica o matemática, o indicadores sobre qué leer.
14
Respuestas:
De hecho, hay poca conexión. Para una comprensión profunda, permítanme explicar la conexión entre programas y circuitos .
Un programa (o algoritmo , o máquina ) es un mecanismo para calcular una función. Para mayor claridad, supongamos que la entrada es una cadena binaria , y la salida es una salida booleana b . El tamaño de la entrada es potencialmente ilimitado. Un ejemplo es un programa que determina si la entrada es la codificación binaria de un número primo.x b
Un circuito (booleano) es una colección de instrucciones para calcular alguna función finita . Podemos imaginar el circuito como un circuito eléctrico, o pensarlo como una secuencia de instrucciones (esta vista se llama confusamente un programa en línea recta ). Concretamente, podemos suponer que la entrada es una cadena binaria de longitud n , y la salida es booleana. Un ejemplo es un circuito que determina si la entrada codifica un número primo (como antes, solo que ahora la entrada debe ser de longitud n ).x n n
Podemos convertir un programa en un circuito P n que simula P en entradas de longitud n . La secuencia correspondiente de circuitos P 0 , P 1 , P 2 , ... no es arbitraria: todos pueden ser construidos por un programa que da n salidas P n . Llamamos a tal secuencia de circuitos unP Pn P n P0,P1,P2,… n Pn uniforme (confusamente, a menudo pensamos en la secuencia como un circuito "único" para un n indefinido ).Pn n
No todas las secuencias de circuitos son uniformes. De hecho, ¡una secuencia de circuitos puede calcular todas las funciones, desde cadenas hasta booleanas, computables o no computables! Sin embargo, en la teoría de la complejidad nos interesan esos modelos no uniformes en los que los circuitos están restringidos. Por ejemplo, la pregunta P = NP establece que los problemas de NP completo no pueden resolverse mediante algoritmos de tiempo polinomiales. Esto implica que los problemas de NP completo no pueden resolverse mediante circuitos uniformes de tamaño polinómico. Además, se conjetura que los problemas de NP completo no pueden resolverse mediante circuitos de tamaño polinómico sin el requisito de uniformidad .
Los modelos de computación completos de Turing son modelos que realizan todas las funciones computables (y no más). En contraste, los sistemas completos de compuertas (como AND, OR, NOT o NAND) permiten calcular funciones arbitrarias finitas utilizando circuitos hechos de estas compuertas. Tales sistemas completos pueden calcular funciones completamente arbitrarias utilizando secuencias (sin restricciones) de circuitos.
fuente
De hecho, tienes razón. Un circuito lógico combinacional es equivalente a un autómata finito. Las puertas NAND no los hacen más poderosos; se usan porque es simplemente más barato construir un circuito lógico digital con un solo tipo de puerta que construirlo con todas las puertas diferentes. De hecho, una puerta NAND se puede construir a partir de una puerta AND y una puerta NOT. Las chanclas completan el circuito de Turing. Aquí hay una clave útil:
Circuitos combinacionales ~ Autómatas finitos ~ Lenguajes regulares ~ Expresiones regulares ~ Cálculo proposicional ~ Programas de línea recta
Si desea obtener más información, hay un muy buen libro que puede descargar en formato PDF de forma gratuita que explica todo esto:
https://cs.brown.edu/people/jes/book/pdfs/ModelsOfComputation.pdf
fuente