Połączenie między bramkami NAND a kompletnością Turinga

Wiem, że bram NAND można używać do tworzenia obwodów, które implementują każdą tabelę prawdy, a nowoczesne komputery są zbudowane z bram NAND. Jaki jest teoretyczny związek między bramkami NAND a kompletnością Turinga? Wydaje mi się, że obwody bramki NAND są bliższe automatom skończonym niż maszyny Turinga. Moją intuicją jest to, że mogę budować przerzutniki, a zatem rejestry i pamięć, z bramek NAND, a pamięć nieograniczona jest kluczową właściwością kompletnych systemów Turinga. Szukam bardziej teoretycznych lub matematycznych wyjaśnień lub wskazówek na temat tego, co czytać.

turing-machines turing-completeness digital-circuits

— bsm
źródło

„nowoczesne komputery są zbudowane z bramek NAND” Jestem pewien, że to nieprawda. Typowe biblioteki komórkowe dla projektów cyfrowych zawierają dziesiątki, gdy nie setki bramek i różnią się pod względem funkcji (szukaj bramek AOI), a także pod względem wachlarza i wachlowania.

— AProgrammer

Masz rację, miałem na myśli teoretycznie, że cała cyfrowa logika może być zbudowana z NAND, które są uważane za funkcjonalnie kompletne

— bsm

Odpowiedzi:

Rzeczywiście istnieje niewiele powiązań. Dla dokładnego zrozumienia pozwól mi wyjaśnić związek między programami i obwodami .

Programu (lub algorytm lub maszyny ) jest mechanizmem do obliczania funkcji. Dla definitywności załóżmy, że wejście jest ciągiem binarnym , a wyjście jest wyjściem logicznym . Rozmiar danych wejściowych jest potencjalnie nieograniczony. Jednym z przykładów jest program, który określa, czy wejście jest kodowaniem binarnym liczby pierwszej. $x$ $b$

Obwód (boolowski) to zbiór instrukcji do obliczania niektórych funkcji skończonych . Możemy sobie wyobrazić obwód jako obwód elektryczny, lub myśleć o nim jako o sekwencji instrukcji (ten widok nazywa się myląco programem linii prostej ). Konkretnie możemy założyć, że wejście jest ciągiem binarnym długości , a wyjście jest logiczne. Jednym z przykładów jest obwód, który określa, czy wejście koduje liczbę pierwszą (tak jak poprzednio, tylko teraz wejście musi mieć długość ). $x$ $n$ $n$

Możemy przekonwertować program na obwód który symuluje na wejściach o długości . Odpowiednia sekwencja obwodów nie jest dowolna - wszystkie można zbudować za pomocą programu, który dał wyjść . Taką sekwencję obwodów nazywamy obwodem jednorodnym (myląco często myślimy o sekwencji jako o „pojedynczym” obwodzie dla nieokreślonego ). $P$ $P_n$ $P$ $n$ $P_0,P_1,P_2,\ldots$ $n$ $P_n$ $P_n$ $n$

Nie każda sekwencja obwodów jest jednorodna. Rzeczywiście, sekwencja obwodów może obliczyć każdą funkcję od ciągów znaków do wartości logicznej, obliczalnej lub nieobliczalnej! Niemniej jednak w teorii złożoności interesują nas takie niejednorodne modele, w których obwody są ograniczone. Na przykład pytanie P = NP stwierdza, że problemów z kompletnością NP nie można rozwiązać za pomocą algorytmów wielomianowych. Oznacza to, że problemów z kompletnością NP nie można rozwiązać za pomocą jednorodnych obwodów wielomianowych. Przypuszcza się ponadto, że problemów z kompletnością NP nie można rozwiązać za pomocą obwodów wielomianowych bez wymogu jednorodności .

Kompletne modele obliczeniowe Turinga to modele, które realizują wszystkie funkcje obliczeniowe (i nie więcej). Natomiast kompletne systemy bramek (takie jak AND, OR, NOT lub NAND) pozwalają na obliczenie dowolnych funkcji skończonych przy użyciu obwodów wykonanych z tych bramek. Takie kompletne systemy mogą obliczać całkowicie dowolne funkcje przy użyciu (nieograniczonych) sekwencji obwodów.

— Yuval Filmus
źródło

Czy potrafisz wyjaśnić, że „sekwencja obwodów może obliczyć każdą funkcję, od ciągów znaków do wartości logicznej, obliczalnej lub nieobliczalnej”? Czy ich zdolność do obliczania funkcji nieobliczalnych (z punktu widzenia kompletności Turinga) wynika z ograniczenia wielkości wejściowej?

— bsm

n

$n$

n

$n$

Czy możesz to wyjaśnić, @YuvalFilmus? Wydaje się dziwne, że nieobliczalna funkcja, taka jak złożoność Kołmogorowa, nagle stałaby się „obliczalna” za pomocą obwodów.

— Cort Ammon

f

$f$

n

$n$

W rzeczywistości masz rację. Kombinacyjny obwód logiczny jest równoważny skończonemu automatowi. Bramy NAND nie zwiększają ich siły; są one używane, ponieważ zbudowanie cyfrowego układu logicznego z tylko jednym rodzajem bramki jest po prostu tańsze niż zbudowanie go ze wszystkimi różnymi bramkami. W rzeczywistości bramę NAND można zbudować tylko z bramki AND i NOT. Japonki dopełniają obwód Turinga. Oto przydatny klucz:

Obwody kombinacyjne ~ Automaty skończone ~ Języki regularne ~ Wyrażenia regularne ~ Rachunek zdań ~ Programy prostej linii

$\mu$

Jeśli chcesz dowiedzieć się więcej, istnieje bardzo dobra książka do pobrania w formacie PDF za darmo, która wyjaśnia wszystko:

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

— użytkownik628544
źródło