Czy funkcje logiczne Turinga są kompletne?

Funkcja boolowska jest funkcją .$f:\{0,1\}^n\rightarrow\{0,1\}$

Podstawa logiczna jest znana jako Turing complete, ponieważ pozwala na odwrócenie dowolnej sekwencji lub pozostawienie jej bez zmian. To samo można powiedzieć o bramkach .$(\vee,\wedge)$$s\in\{0,1\}$$\mathrm{XOR}$

W tym sensie możemy zacząć od początkowej konfiguracji komputera tak że i to kolejne wartości :$\textbf{b}=(b_1,\ldots,b_n)$$b_i\in\{0,1\}$$\mathrm{XOR}$$\textbf{v}_i$

$\textbf{b}\oplus\textbf{v}_1\oplus\textbf{v}_2\oplus\textbf{v}_3\ldots$

Każdy stan reprezentowałby permutację jakiegoś elementu w . Ten proces skutecznie naśladuje maszynę Turinga i zakłada, że ​​istnieje jakiś generator wartości .$\textbf{v}_i$$\textbf{b}$$\textbf{v}_i$

Czy możemy więc powiedzieć, że funkcje logiczne Turinga są kompletne?

Nieformalnie język (programistyczny) jest Turing kompletny, jeśli każda funkcja obliczeniowa ma swoją reprezentację. Ogólna funkcja obliczeniowa akceptuje dane wejściowe o dowolnym rozmiarze. Z drugiej strony funkcje boolowskie akceptują dane wejściowe o stałym rozmiarze. Dlatego funkcje boolowskie nawet nie kwalifikują się jako potencjalnie pełne Turinga.

Odpowiednie pojęcie kompletności tutaj jest kompletną podstawą połączeń. Zestaw połączeń ( funkcje -ary na wartościach logicznych dla dowolnego ) jest kompletny, jeśli każdą funkcję logiczną na (dla dowolnego ) można przedstawić za pomocą połączeń. Następujące zestawy są kompletne: podstawa de Morgan i podstawa . Natomiast nie jest kompletny: może wyrażać tylko funkcje liniowe.$k$$k$$x_1,\ldots,x_n$$n \geq 1$$\{\lnot,\lor,\land\}$$\{\lnot,\Rightarrow\}$$\{\lnot,\oplus\}$

Ściśle mówiąc, jak odpowiedział YF, skończone obwody nie mogą być Turinga kompletne.

warto jednak wspomnieć o tropie w odpowiedzi na to pytanie (i być może tego, czego szukasz) blisko spokrewnionej koncepcji stosowanej dość powszechnie w teorii, w której obwody są wykorzystywane do obliczania funkcji w sposób silniejszy niż Turinga.

mianowicie rodziny obwodów. rodzina obwodów może obliczać nieskończone języki. każde wejście o rozmiarze ma powiązany obwód / funkcję zbudowaną za pomocą jakiejś metody, niekoniecznie zbudowaną za pomocą TM! języki obwodów obliczalne przez rozstrzygalne bazy TM są znane jako obwody jednorodne, a obwody niemożliwe do zbudowania w tej klasie są znane jako niejednorodne .$n$$C_n$