Связь между воротами NAND и полнотой по Тьюрингу

Я знаю, что шлюзы NAND можно использовать для создания схем, реализующих каждую таблицу истинности, а современные компьютеры состоят из вентилей NAND. Какова теоретическая связь между воротами NAND и полнотой Тьюринга? Мне кажется, что схемы затворов NAND ближе к конечным автоматам, чем машины Тьюринга. Моя интуиция заключается в том, что я могу создавать триггеры, и, следовательно, регистры и память из шлюзов NAND, а неограниченная память является ключевым свойством полных систем Тьюринга. Я ищу более теоретическое или математическое объяснение или указатели на то, что читать.

turing-machines turing-completeness digital-circuits BSM
источник

«Современные компьютеры построены из ворот NAND» Я уверен, что это неверно. Типичные библиотеки ячеек для цифровых дизайнов содержат десятки, а не сотни вентилей, и они различаются по функциям (ищите вентили AOI), а также по разветвлению и разветвлению.

AProgrammer

Вы правы, я имел в виду в теоретическом смысле, что вся цифровая логика может быть построена из NANDS, которые считаются функционально завершенными

bsm

Ответы:

Там действительно мало связи. Для более глубокого понимания позвольте мне объяснить связь между программами и схемами .

Программа (или алгоритм , или машина ) представляет собой механизм для вычисления функции. Для определенности предположим, что вход является двоичной строкой , а выход - логическим выходом $x$ $b$ . Размер входа потенциально неограничен. Одним из примеров является программа, которая определяет, является ли ввод двоичной кодировкой простого числа.

(Булева) схема представляет собой набор инструкций для вычисления некоторой конечной функции. Мы можем изобразить схему как электрическую схему или представить ее как последовательность инструкций (эта точка зрения называется смущающей прямой программой ). Конкретно, мы можем предположить, что входные данные являются двоичной строкой длины , а выходные данные являются логическими. Одним из примеров является схема, которая определяет, кодирует ли вход простое число (как и раньше, только теперь вход должен иметь длину $x$ $n$ $n$ ).

Мы можем преобразовать программу в схему которая имитирует на входах длины . Соответствующая последовательность цепей не является произвольной - все они могут быть построены с помощью программы, которая дает выходов . Мы называем такую последовательность цепей однородной цепью (в замешательстве мы часто думаем о последовательности как о «единственной» схеме для неопределенного ). $P$ $P_n$ $P$ $n$ $P_0,P_1,P_2,\ldots$ $n$ $P_n$ $P_n$ $n$

Не каждая последовательность цепей одинакова. Действительно, последовательность схем может вычислять каждую функцию от строк до логического, вычислимого или не вычисляемого! Тем не менее, в теории сложности нас интересуют такие неоднородные модели, в которых схемы ограничены. Например, вопрос P = NP утверждает, что NP-полные задачи не могут быть решены алгоритмами полиномиального времени. Это означает, что NP-полные проблемы не могут быть решены с помощью однородных схем полиномиального размера. Более того, предполагается, что NP-полные задачи не могут быть решены с помощью схем полиномиального размера без требования однородности .

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

Юваль Фильмус
источник

Можете ли вы объяснить, «последовательность цепей может вычислять каждую функцию от строк до логического, вычислимого или не вычислимого»? Их способность вычислять невычислимые (с точки зрения полноты по Тьюрингу) функции обусловлены ограничением размера входных данных?

БСМ

n

$n$

n

$n$

Можете ли вы объяснить это, @YuvalFilmus? Кажется странным, что невычислимая функция, такая как колмогоровская сложность, внезапно стала бы «вычислимой» с использованием схем.

Корт Аммон

f

$f$ ее ограничение строками длины

n

$n$ вычислимо Это все.

Юваль Фильмус

Вы на самом деле правы. Комбинационная логическая схема эквивалентна конечному автомату. Ворота NAND не делают их более могущественными; они используются потому, что просто создать цифровую логическую схему с одним типом затвора дешевле, чем построить ее со всеми различными затворами. Фактически, логический элемент NAND может быть построен только из логического элемента AND и логического элемента NOT. Шлепанцы делают схему Тьюринга-полной. Вот удобный ключ:

Комбинационные схемы ~ Конечные автоматы ~ Регулярные языки ~ Регулярные выражения ~ Исчисление высказываний ~ Программы прямых

Последовательные схемы ~ машины Тьюринга ~ рекурсивно перечислимые языки ~ исчисление предикатов ~ $\mu$ -рекурсивные функции

Если вы хотите узнать больше, есть очень хорошая книга, которую вы можете бесплатно скачать в формате PDF, которая объясняет все это:

https://cs.brown.edu/people/jes/book/pdfs/ModelsOfComputation.pdf

user628544
источник