Jaka jest najprostsza 2-stanowa uniwersalna maszyna Turinga bez kontrowersji?

Chcę zakodować prostą maszynę Turinga w zasadach gry w karty. Chciałbym uczynić ją uniwersalną maszyną Turinga, aby udowodnić jej kompletność.

Do tej pory stworzyłem stan gry, który koduje 2-stanową, 3-symbolową maszynę Turinga Alexa Smitha . Wydaje się jednak (co prawda na podstawie Wikipedii), że istnieją kontrowersje dotyczące tego, czy maszyna (2, 3) jest rzeczywiście uniwersalna.

Na wszelki wypadek chciałbym, aby mój dowód zawierał „niekontrowersyjny” UTM. Więc moje pytania to:

1. Czy maszyna (2,3) jest ogólnie uważana za uniwersalną, nie uniwersalną lub kontrowersyjną? Nie wiem, gdzie są renomowane miejsca, w których można znaleźć odpowiedź na to pytanie.

2. Jeśli maszyna (2,3) nie jest powszechnie akceptowana jako uniwersalna, to co jest najmniejszym N, tak że maszyna (2, N) jest niekontrowersyjnie akceptowana jako uniwersalna?

Zredagowano, aby dodać: Przydałoby się również znać wszelkie wymagania dotyczące nieskończonej taśmy dla wymienionych maszyn, jeśli je znasz. Wydaje się, że maszyna (2,3) wymaga początkowego stanu taśmy, który nie jest okresowy, co będzie nieco trudne do symulacji w ramach zasad gry w karty.

Pojawiły się nowe wyniki od czasu pracy cytowanej w poprzednich odpowiedziach. Ta ankieta opisuje aktualny stan techniki (patrz ryc. 1). Rozmiar najmniejszej znanej uniwersalnej maszyny Turinga zależy od szczegółów modelu, a oto dwa wyniki, które mają znaczenie dla tej dyskusji:

• Istnieje 2-stanowa, 18-symbolowa standardowa maszyna uniwersalna (Rogozhin 1996. TCS, 168 (2): 215–240). Mamy tutaj zwykłe pojęcie pustego symbolu w jednym lub obu kierunkach pojedynczej taśmy.
• Istnieje 2-stanowa, 4-symbolowa słabo uniwersalna maszyna (Neary, Woods 2009. FCT. Springer LNCS 5699: 262-273). Tutaj mamy pojedynczą taśmę zawierającą skończone wejście i stałe (niezależnie od wejścia) słowo powtarzane nieskończenie w prawo, a kolejne stałe słowo powtarzane nieskończenie w lewo. Poprawia to słabo uniwersalną maszynę wspomnianą przez Davida Eppsteina.$r$$l$

Wygląda na to, że (2.1) jest dla Ciebie najbardziej przydatny.

Zauważ, że obecnie wiadomo, że wszystkie najmniejsze uniwersalne maszyny Turinga działają w czasie wielomianowym. To implikuje, że ich problem przewidywania (biorąc pod uwagę maszynę , dane wejściowe czasowe unary, czy akceptuje ciągu czasu ?) Jest P-całkowity. Jeśli próbujesz stworzyć grę (1-osobową), może to być przydatne, na przykład, aby pokazać, że trudno jest znaleźć początkową konfigurację (układ kart), która prowadzi do zwycięstwa w ciągu t ruchów. W przypadku tych problemów ze złożonością dbamy tylko o skończoną część taśmy, co sprawia, że ​​(bardzo małe) słabo uniwersalne maszyny są bardzo przydatne.$M$$w$$t$$M$$w$$t$

Rysunek pokazuje najmniejsze znane uniwersalne maszyny dla różnych modeli maszyn Turinga (wzięte z Neary, Woods SOFSEM 2012), odnośniki można znaleźć tutaj .

To nie jest prawdziwa odpowiedź na twoje pytanie (niewiele wiem o (2,3) debacie maszynowej); ale proponuję artykuł „ Małe maszyny Turinga i uogólniona konkurencja dla bobrów ”. Szybko go przeczytałem jakiś czas temu i ma ładny wykres z granicami między 4 rodzajami małych baz TM:

• rozstrzygalny
• otwórz problem podobny do Collatza
• $3x + 1$ symulacja
• uniwersalny

(być może niektóre wyniki zostały poprawione).

Pojęcie TM zastosowane w papierze jest standardową definicją TM stosowaną w papierach na małych uniwersalnych maszynach Turinga:

... Mają unikalną jednowymiarową taśmę nieskończoną w obu kierunkach i unikalną głowicę do odczytu i zapisu. Jest pusty symbol oznaczony jako 0. Początkowo na taśmie zapisywane jest skończone słowo, wejście, inne komórki zawierają pusty symbol, głowa odczytuje lewy symbol wejścia, a stan jest stanem początkowym. Na każdym etapie, zgodnie z bieżącym stanem maszyny i symbolem odczytywanym przez głowę, symbol jest modyfikowany, głowa przesuwa się w lewo lub w prawo (i nie może dalej czytać tej samej komórki), a stan jest modyfikowany. Obliczenia zatrzymują się po osiągnięciu specjalnego stanu zatrzymania. ...

Możliwe jest również osiągnięcie uniwersalności z 7 stanami i 2 symbolami, chociaż stosuje się wiele takich samych zastrzeżeń (niejednolite warunki początkowe na nieskończonej taśmie i nietypowe warunki zakończenia). Zobacz http://11011110.livejournal.com/104656.html i http://www.complex-systems.com/abstracts/v15_i01_a01.html

Opierają się one na symulowaniu automatu komórkowego Reguły 110, który okazał się uniwersalny przez Matthew Cooka, a Cook znalazł również 2-stanową 5-symbolową symulację Reguły 110, jeśli jesteś zwolennikiem ograniczenia, że ​​istnieją tylko dwa stany.

Wybierz uniwersalną maszynę Turinga ze stanami ( ) i kolorami ( ) działającą na jednowymiarowej taśmie (nazywamy rzeczy związane z tą maszyną „prawdziwą”). Zbudujmy razem stanową maszynę Turinga (state i ) z kolorami : prawdziwe kolory i kolory „ulepszone”, które niosą informacje o stanach. Dodajemy ograniczenie, że stan początkowy powinien być identyczny ze stanem początkowym prawdziwej maszyny, z wyjątkiem ewentualnie komórki, w której zaczynamy.$S$$0\leq s < S$$C$$0\leq c< C$$2$$\text{L}$$\text{R}$$C+4SC$

Przez cały czas tylko bieżąca komórka lub dwie komórki uczestniczące w przejściu mogą mieć ulepszone kolory: wszystkie inne komórki mają swój prawdziwy kolor. Chcemy, aby nasza maszyna zachowywała się w następujący sposób: sprawdź, jakie prawdziwe przejście należy wykonać, przenieś informacje o „stanie prawdziwym” z komórki, którą chcemy pozostawić do komórki docelowej (wymaga to wiele tam i z powrotem), posprzątaj komórkę zostawiliśmy (nadając jej prawdziwy kolor), powtórz.

Przed przejściem bieżąca komórka ma wzmocniony kolor kodujący prawdziwy kolor i prawdziwy stan, a wszystkie inne mają swój prawdziwy kolor. Sprawdź, jakie przejście wykona prawdziwa maszyna --- możemy założyć, że zmierza w prawo (odwróć i wszędzie, aby przejść w lewo). Zmień ulepszony kolor na , przesuń w prawo i zmień bieżący stan na .$(c,s)$$\text{L}$$\text{R}$$(c_{\text{new}}, s_{\text{new}}, \text{emit})$$\text{L}$

Następnie maszyna widzi normalny kolor i jest w stanie . Zmienia na i wraca w lewo, w stanie . Mamy więc komórki gdzie różne prawdziwe kolory są oczywiście niezależne, ale nieistotne. Celem jest przeniesienie do komórki docelowej. Robimy to, zmniejszając lewy stan i zwiększając prawy stan, przechodząc między nimi. Koniec jest łatwy do wykrycia w lewej komórce ( stał się$c$$\text{L}$$c$$(c,0, \text{L},\text{receive})$$\text{R}$

Oto przejścia do implementacji tego. W prawie wszystkich przypadkach przesuń się w kierunku określonym przez bieżący stan, a następnie odwróć stan

1. $c \to (c,0,\langle dir\rangle,\text{receive})$ gdzie to bieżący stan; przesuń, odwróć stan.$\langle dir\rangle$

2. $(c,s) \to (c_{\text{new}},s_{\text{new}},\text{emit})$ zgodnie z przejściami prawdziwej maszyny; zignoruj ​​obecny stan, ustaw go w kierunku, w którym chcemy się poruszać; przesuń, odwróć stan.

3. $(c,s,\text{emit}) \to (c,s-1,\text{emit})$ dla ; przesuń, odwróć stan.$s>0$

4. $(c,0,\text{emit}) \to c$ ; ruszaj się, nie zmieniaj stanu.

5. $(c,s, \langle dir\rangle, \text{receive}) \to (c, s+1, \langle dir\rangle, \text{receive})$ jeśli stan to ; przesuń, odwróć stan.$\langle dir\rangle$

6. ⟨ d i r $(c,s, \langle dir\rangle, \text{receive}) \to (c,s)$ jeśli stan nie jest ; nie ruszaj się, rób co chcesz z państwem. Można to połączyć z 2., jeśli chcesz zawsze się poruszać.$\langle dir\rangle$

Łączenie 6 i 2 zmniejsza liczbę kolorów do . Uważam, że możliwe jest, aby początkowa konfiguracja nie miała w ogóle ulepszonego koloru, ale prawdopodobnie jest niechlujna.$C+3SC$

chyba że dokładnie zdefiniujesz „niekontrowersyjny” w jakiś techniczny sposób, nie ma dokładnej odpowiedzi. oto inna mała maszyna oparta na regule 110, która okazała się uniwersalna w pewnym sensie, ale rozumiem, że wymaga nieskończonych okresowych formulacji taśmy wejściowej (i podobnie ekstrakcji na końcu, gdy maszyna się zatrzymuje). nie widziałem opisanego w literaturze problemu „okresowych a nieokresowych”, chociaż omawiano go np. na listach matematycznych [Podstawy listy matematycznej]

Dowód Turinga na uniwersalność Alexa Smitha dla 2-stanowej, 3-symbolowej maszyny Turinga domysłowanej przez Wolframa zdecydowanie nie budzi kontrowersji. Podany dowód uniwersalności (nie maszyny) wymaga nieskończonego wzoru na taśmie Turinga, a pytanie brzmiało, czy należy zezwolić na takie konfiguracje (można pomyśleć o zwykle „pustej” taśmie jako o nieskończonym powtarzalnym wzorze pustych symboli). Wniosek był taki, że dopóki konfiguracja na taśmie maszynowej jest stała (tzn. Nie zmienia się po rozpoczęciu obliczeń i pozostaje taka sama dla każdego obliczenia), to obliczenia uniwersalne są wykonywane przez maszynę Turinga. Zauważ, że NIE jest to kontrowersyjne dla reguły 110 automatyki komórkowej Wolframa, którą Wolfram i Cook udowodnili, że jest uniwersalna. Potwierdzenie uniwersalności reguły 110 wymaga również nieskończonego wzoru w początkowej konfiguracji, który jest różny po obu stronach, a zatem ma ten sam charakter dla 2-stanowej, 3-symbolowej maszyny Turinga. Inną obawą było to, że być może takie złagodzenie wymogu warunku początkowego (pustego) uczyniłoby niektóre akceptowanymi automatami uniwersalnymi nie Turinga uniwersalnymi, takimi jak automaty o stanie skończonym, liniowo ograniczone lub popychające w dół, aby wymienić kilka przykładów, ale tak nie jest i nie szanuje hierarchię Chomsky'ego. Tak więc zdecydowanie nie jest kontrowersyjne, czy 2-stanowa, 3-symbolowa maszyna Turinga jest uniwersalna, ale jej dowód uniwersalności wymagał zmiany czegoś, co zwykle uważa się za cotenty zwykłej taśmy maszynowej Turinga. Nawiasem mówiąc, nie oznacza to bezpośrednio, że stan 2,