turing complete - máquina - ¿Qué puertas lógicas se requieren para la integridad de Turing?

maquina electromecanica de turing

Question

Mi hijo ha estado jugando Little Big Planet 2 últimamente, y noté que el editor del juego permite AND gates, OR gates y NOT gates ... ¿Está Turing completo? Si es así, ¿puede alguien recomendar una fuente para aprender a convertir esos primitivos en algo así como un nivel superior condicional si?

Answer 1

AND, OR y NOT está funcionalmente completo , es decir, se pueden expresar todas las tablas de verdad posibles. Creo que también lo hace completamente completo, ya que puede construir un procesador de propósito general con cualquier conjunto de puertas funcionalmente completo.

Answer 2

Las únicas puertas que necesitas no son ni OR. Con esos dos puedes construir todas las demás puertas lógicas. Por ejemplo, NO (O (NO | NO)) es una puerta AND, O (NO | NO) es NAND, NO (O ()) es NOR, etc. La difícil de hacer (y también la más funcionalmente útil) es XOR, que se puede hacer con un árbol de compuertas NAND, que a su vez se puede hacer con NOT y OR como se muestra arriba.

Answer 3

No necesita y uno de AND o OR para poder hacer toda la lógica binaria. Esta es la ley de DeMorgan , básicamente.

Sin embargo, esto no es suficiente para la integridad de Turing. Para eso, también necesita acceso aleatorio (o reduciblemente equivalente) (en teoría) memoria infinita.

Lo más probable es que usted pueda construir un flip flop (un flip flop D está construido usando NAND, por lo que es fácil) usando las puertas lógicas disponibles. A partir de ellos, puede crear un registro, y con suficientes de ellos estará equipado para crear algunos programas simples.

Answer 4

Sé que llego tarde al juego aquí, pero sí. Juego LBP2, y tiene un AND, OR, NOT, XOR, NAND, NOR. También puedes sumar y restar señales, también hay formas de hacer binarios en el juego.

Answer 5

Una idea: deberías poder construir una compuerta NAND , entonces puedes construir una compuerta XOR . Con XOR y AND puedes construir un half-adder . Combina las medias sumas para construir un half-adder . Eso sería un comienzo por lo menos.

NAND y NOR son bloques de construcción básicos para otras puertas, por lo que es probable que la integridad de Turing esté a la vuelta de la esquina .

Answer 6

Una puerta nand es todo lo que se requiere, todo se puede construir a partir de eso, por lo que los tres que tienes son suficientes. Aquí hay un curso que lo lleva desde puertas lógicas, hasta la construcción de una computadora, hasta la escritura de un sistema operativo: Los elementos de los sistemas de computación: la construcción de una computadora moderna a partir de los Primeros Principios