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

Question

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

Answer 1

Вам нужно НЕ и один из И или ИЛИ, чтобы иметь возможность выполнять всю двоичную логику. Это закон Деморгана , в основном.

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

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

Answer 2

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

Answer 3

Идея: вы должны быть в состоянии построить NAND gate , чтобы вы могли затем построить XOR gate . С помощью XOR и AND вы можете создать половину сумматора . Объедините половину сумматоров, чтобы получить полных сумматоров . Это было бы началом по крайней мере.

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

Answer 4

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

Answer 5

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

Answer 6

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