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

31

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.

AlexC
źródło
3
BTW, nie mogę powiedzieć, czy pytania dotyczące maszyny Turinga lepiej opublikować tutaj, czy na MathOverflow. Próbuję tutaj pierwszy, ponieważ cs ma tag „maszyny Turinga”, a MO nie. Nie stosuję symulacji krzyżowej zgodnie z zasadami, ale cieszę się z migracji tego pytania, jeśli byłoby to lepsze miejsce.
AlexC
12
Myślę, że to rozsądne miejsce na to pytanie.
Suresh Venkat
4
Dodano tytuł „uniwersalny”. (Najprostsza
dwustanowa
1
ps lat temu szukał ankiety na temat uniwersalności automatów komórkowych bezskutecznie. wydaje się, że nie został zbytnio włączony do literatury. koncepcja jest dość szeroko rozpowszechniona w „folklorze” w tym punkcie, ale nie ma zbytniego uzasadnienia w formalnych defns / proofs / teorii. wolfram zrobił wiele w tej dziedzinie, ale jak wielu zauważyło, jego styl jest bardziej eksperymentalny.
vzn
2
Heh Współpracownik kładzie gazetę ( arxiv.org/abs/1904.09828 ) na Slacku i nerd-snipes mnie, szukam w Google „2.1 uniwersalnej tokarki” i oto jesteśmy. Gratulacje!
Cyan

Odpowiedzi:

12

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.rl

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.MwtMwt

Neary, Woods SOFSEM 2012, Najmniejsze znane uniwersalne maszyny Turinga

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 .

Niall Murphy
źródło
13

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

zdjęcie z papieru

(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. ...

Marzio De Biasi
źródło
1
Link prowadzi do pracy Alexa Smitha, a nie do pracy, o której myślę, że zamierzałeś.
Jeffε
Bardzo przydatny link. Dzięki. Wygląda na to, że najlepiej wybrać maszynę (2, 18).
AlexC
Czytając ten artykuł, napisano, że maszyny Turinga z symbolem 2 stanu 3 mają poważny problem z zatrzymaniem, więc maszyna Turinga z symbolem 3 stanu Wolfram 2 nie może być uniwersalna.
Craig Feinstein
1
@CraigFeinstein: Wolfram (2,3) TM nieco różni się od zwykłych TM: nie ma stanu zatrzymania i wymaga i nieskończonej obsługi powtarzającej się taśmy. Nie można go nawet uznać za słabo uniwersalny (słabo uniwersalna TM wymaga nieskończonego powtarzającego się wzoru w obu kierunkach)
Marzio De Biasi
11

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.

David Eppstein
źródło
Ograniczenie 2 stanów będzie o wiele łatwiejsze do symulacji niż TM z większą liczbą stanów. W tej chwili myślę, że łatwiej będzie mi stworzyć 2-stanową, 18-kolorową bazę TM niż ta z 3 stanami, a nawet niewielką liczbą kolorów.
AlexC
(2, 5) jest interesujące i może być dla mnie użytecznym krokiem pośrednim. Ale z tych linków wygląda to tak, jakbym musiał przejść do (2, 18), aby znaleźć taki, który pozwala mi zacząć od tylko skończonej liczby nieblackich komórek na początkowej taśmie. Dzięki!
AlexC
5

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.S0s<SC0c<C2LRC+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)LR(cnew,snew,emit)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ęcLc(c,0,L,receive)R

cc(c,s,emit)(c,0,L,receive)cc
ss0), ale trudniejsze do wykrycia w odpowiedniej komórce. Do tego służy etykieta : tak długo, jak odpowiada temu stan, kontynuuj pętlę dekrementacji / inkrementacji, ale jeśli nie, to skończymy i posprzątamy.L

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(c,0,dir,receive) gdzie to bieżący stan; przesuń, odwróć stan.dir

  2. (c,s)(cnew,snew,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,emit)(c,s1,emit) dla ; przesuń, odwróć stan.s>0

  4. (c,0,emit)c ; ruszaj się, nie zmieniaj stanu.

  5. (c,s,dir,receive)(c,s+1,dir,receive) jeśli stan to ; przesuń, odwróć stan.dir

  6. d i r (c,s,dir,receive)(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ć.dir

Łą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

Bruno Le Floch
źródło
0

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]

vzn
źródło
-3

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,

użytkownik2230103
źródło
Próbując przeanalizować ten długi argument, dochodzę do wniosku, że Smith (2,3) -TM jest wyraźnie uniwersalny tylko w słabym znaczeniu. Jednak kilka innych odpowiedzi już szczegółowo to omówiło, z odniesieniami do artykułów z klasyfikacjami, które starają się uczynić tę narrację matematycznie precyzyjną. Należy również pamiętać, że nie wszystkie modele TM zakładają na początku nieskończoną pustą taśmę.
András Salamon,
Twój komentarz pokazuje tylko, że ignorujesz ten obszar. Nie zastosowałem żadnych trudnych koncepcji dla kogoś, kto zna podstawy maszyn Turinga (np. Konfiguracja początkowa, pusty symbol itp.). Znowu jedyną różnicą, którą już zaakceptowaliśmy w przypadku innych rodzajów automatów, jest to, że maszyna Smitha-Wolframa Turinga nie zaczyna się od czystej taśmy. Ta poprawna odpowiedź ma -3 wyraźnie pokazuje, jak demokracja i popularność nie oznaczają prawdy, bardziej istotna realizacja niż cokolwiek innego, biorąc pod uwagę tego rodzaju klaunów, którzy teraz rządzą światem pod parasolem demokracji.
user2230103,