Какие логические ворота необходимы для полноты Тьюринга?

В последнее время мой сын играет Маленькую Большую Планету 2, и я заметил, что редактор игр разрешает И ворота, ИЛИ ворота и НЕ ворота... Является ли это Тьюрингом полным? Если да, может ли кто-нибудь порекомендовать источник для обучения превратить эти примитивы в нечто вроде более высокого уровня условного, если?

Ответ 1

Вам НЕ нужно, и один из AND или OR может выполнять всю двоичную логику. Это Закон DeMorgan, в основном.

Однако этого недостаточно для полноты Тьюринга. Для этого вам также нужен случайный (или уменьшающийся эквивалент) доступ (теоретически) бесконечной памяти.

Скорее всего, вы сможете построить флип-флоп (a D flip flop построен с использованием NAND, поэтому его легко использовать) доступные логические ворота. Из этого вы можете построить зарегистрируйтесь, и с достаточным количеством из них вы будете оснащены для создания простых программ.

Ответ 2

Во всех случаях требуется все, что требуется, все это можно построить, поэтому у вас три. Здесь курс, который выводит вас из логических ворот, вплоть до создания компьютера, вплоть до написания операционной системы: Элементы вычислительных систем: Создание современного компьютера из первых принципов

Ответ 3

Идея: вы должны иметь возможность построить NAND gate, чтобы затем вы могли построить XOR gate. С помощью XOR и AND вы можете создать half-adder. Комбинируйте полукомпенсаторы для создания полного полного сумматора. По крайней мере, это будет начало.

NAND и NOR являются базовыми строительными блоками для других ворот, поэтому шансы Полнота Turing не за горами.

Ответ 4

И, OR и NOT функционально завершено, то есть могут быть выражены все возможные таблицы истинности. Который, я считаю, также делает его полным, поскольку вы можете построить процессор общего назначения с любым функционально полным набором ворот

Ответ 5

Я знаю, что я опаздываю к игре здесь, но да. Я играю LBP2, и у него есть AND, OR, NOT, XOR, NAND, NOR. Вы также можете добавлять и вычитать сигналы, есть также способы делать двоичные файлы в игре.

Ответ 6

Единственными воротами, которые вам нужны, являются NOT и OR. С этими двумя вы можете построить все другие логические ворота. Например, NOT (OR (NOT | NOT)) является логическим элементом AND, OR (NOT | NOT) является NAND, NOT (OR()) является NOR и т.д. Трудный для создания (а также наиболее функционально полезный) XOR, который может быть выполнен с деревом NAND-ворот, который, в свою очередь, может быть сделан с NOT и OR, как показано выше.