Czy funkcje logiczne Turinga są kompletne?

9

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?

turing-machines turing-completeness boolean-algebra

— użytkownik13675
źródło

1

Jak ta maszyna mogła utknąć w nieskończonej pętli?

— Guildenstern

Wydaje mi się, że chodzi o to, że chociaż formalizm logiczny obwodu logicznego jest izomorficzny w stosunku do formalizmu Turinga, nie mówi ci on, jak zbudować lub wygenerować taki program ... Musisz po prostu „poznać” wartości ...

v_{i}

$\textbf{v}_i$

— user13675

8

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\}$

— Yuval Filmus
źródło

Czy ich odpowiednik, obwody boolowskie, byłby kompletny w Turingu? Sądzę, że tak, odkąd Cook (w swoim dowodzie kompletności NP 3SAT) pokazał, w jaki sposób maszyny Turinga i obwody boolowskie są równoważne?

— user13675

@ user13675 Nie, to dokładnie ten sam problem. Każdą zatrzymującą się maszynę Turinga można przekształcić w równoważny obwód logiczny lub formułę dla każdego rozmiaru wejściowego, ale dla każdego rozmiaru potrzebny będzie inny.

— Yuval Filmus

5

Ś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$

— vzn
źródło