Jakim automatem jest Google Turing Doodle?

Z okazji urodzin Alana Turinga Google opublikował doodle przedstawiające maszynę. Jaką maszyną jest doodle? Czy może wyrażać język Turing Complete?

Istnieją oczywiste różnice w stosunku do klasycznej maszyny Turinga: skończona taśma, ograniczenia w sposobie łączenia stanu, ...

Doodle jest nadal dostępne tutaj

(Wyświetlacz w prawym górnym rogu pokazuje oczekiwane wyjście.)

Taśma pośrodku jest podzielona na kwadraty, które mogą pomieścić puste miejsce, zero lub jeden. Głowa jest umieszczona nad jednym z kwadratów i służy do czytania i pisania.

Pod taśmą widać zieloną strzałkę, którą można kliknąć, aby uruchomić maszynę. Obok niego znajdują się dwie linie kół, z których niektóre są połączone. Nazywam je „stanami”.

Po uruchomieniu komputera zaświeci się pierwszy stan z prawej strony zielonego przycisku, następnie następny z prawej strony i tak dalej ... Każdy stan zawiera jedno z następujących poleceń:

• puste = nic nie rób (po prostu przejdź do następnego stanu)
• 1 = napisz jeden na taśmie w bieżącej pozycji głowy
• 0 = zapisz zero na taśmie w bieżącej pozycji głowy
• strzałka w lewo = przesuń głowę o jeden krok w lewo
• strzałka w prawo = przesuń głowę o jeden krok w prawo
• warunek: jeśli wartość pod głową jest równa wartości pokazanej w kwadracie, przejdź do drugiej linii stanów. jeśli nie, przejdź do następnego stanu po prawej
• lewy skok: powrót do (naprawionego) poprzedniego stanu, ale tylko w górnym rzędzie [Pierwotnie zapomniałem tego, dzięki @Marzio!]

Nie ma możliwości „nałożenia” dwóch skoków (jeden na drugi). Maszyna zatrzymuje się, gdy opuści stan i nie ma następnego stanu po prawej stronie.

(Po zatrzymaniu urządzenia zawartość taśmy jest porównywana z zawartością wyświetlacza, ale nie uważam tego za część zamierzonej funkcjonalności urządzenia).

Przy założeniu, że:

• możemy dodać dowolnie dużą liczbę wierszy („wiersze stanu”)
• rzędy mogą być dowolnie długie
• taśma jest nieskończona

$M_4$

... więc nawet gdy co za Doodle jest być może nie Turinga kompletne (ze względu na zakaz kumulacji lewej tylko operatora skoku dostępnej tylko w pierwszym rzędzie), jest wystarczająco silny, aby chodzić linię grzywnie (ONZ) rozstrzygalności: - re

EDYCJA: TURING DOODLE TO TURING KOMPLETNY

(Pozostawiam poprzednią odpowiedź powyżej, ponieważ nie jestem pewien, czy ta część jest poprawna :-)

Wydaje mi się, że nawet przy jednym skoku w lewo, bez nakładania się, Turing Doodle jest już gotowy! . (Prostym) pomysłem jest użycie samej taśmy do przechowywania bieżącego stanu i użycie wielu komórek do przedstawienia większego alfabetu.

Na przykład 2 symbole 8 stanów TM mogą być symulowane przy użyciu następującej reprezentacji taśmy:

    HEAD POSITION
    v
...[s][b2 b1 b0] [_][b2 b1 b0] [_][b2 b1 b0] ....
   ^^^^^^^^^^^^^
    "macro cell"

Doodle Turinga może:

1. $s$
2. $b2, b1, b0$
3. napisz następny symbol, przenieś głowę do „komórki makro” po lewej lub prawej stronie i zapisz na niej następny stan; na poniższym rysunku te operacje (które można wykonać na sekwencji komórek za pomocą akcji przesuń w lewo / prawo i napisz) są nazywane „MW”;
4. na koniec przenieś sterowanie do górnego rzędu, który jednym lewym skokiem przywróci sterowanie do kroku 1.

Pełny obraz jest dostępny tutaj .

$TM$$DM$

Maszyna jest dostarczana z „taśmą” (analogiem papieru) biegnącą przez nią i podzielona na sekcje (zwane „kwadratami”), z których każda może nosić „symbol”. W dowolnym momencie jest tylko jeden kwadrat, powiedzmy r-ty, opatrzony symbolem S (r), który jest „w maszynie”. Możemy nazwać ten kwadrat „zeskanowanym kwadratem”. Symbol na zeskanowanym kwadracie można nazwać „zeskanowanym symbolem”. „Zeskanowany symbol” jest jedynym, z którego maszyna jest, że tak powiem, „bezpośrednio świadoma”. Jednak zmieniając konfigurację m, maszyna może skutecznie zapamiętać niektóre symbole, które „widziała” (skanowała) wcześniej. Możliwe zachowanie maszyny w dowolnym momencie zależy od konfiguracji m qn i zeskanowanego symbolu S (r). Ta para qn, S (r) będzie nazywana „konfiguracją”: w ten sposób konfiguracja określa możliwe zachowanie maszyny. W niektórych konfiguracjach, w których zeskanowany kwadrat jest pusty (tj. Nie ma symbolu), maszyna zapisuje nowy symbol na zeskanowanym kwadracie: w innych konfiguracjach usuwa zeskanowany symbol. Urządzenie może również zmienić skanowany kwadrat, ale tylko przesuwając go o jedno miejsce w prawo lub w lewo. Oprócz dowolnej z tych operacji konfiguracja m może zostać zmieniona. Niektóre z zapisanych symboli {232} utworzą ciąg cyfr, który jest dziesiętnym obliczanej liczby rzeczywistej. Pozostałe są tylko szorstkimi notatkami „wspomagającymi pamięć”. Tylko szorstkie nuty będą mogły zostać usunięte. nie nosi żadnego symbolu) urządzenie zapisuje nowy symbol na zeskanowanym kwadracie: w innych konfiguracjach kasuje zeskanowany symbol. Urządzenie może również zmienić skanowany kwadrat, ale tylko przesuwając go o jedno miejsce w prawo lub w lewo. Oprócz dowolnej z tych operacji konfiguracja m może zostać zmieniona. Niektóre z zapisanych symboli {232} utworzą ciąg cyfr, który jest dziesiętnym obliczanej liczby rzeczywistej. Pozostałe są tylko szorstkimi notatkami „wspomagającymi pamięć”. Tylko szorstkie nuty będą mogły zostać usunięte. nie nosi żadnego symbolu) urządzenie zapisuje nowy symbol na zeskanowanym kwadracie: w innych konfiguracjach kasuje zeskanowany symbol. Urządzenie może również zmienić skanowany kwadrat, ale tylko przesuwając go o jedno miejsce w prawo lub w lewo. Oprócz dowolnej z tych operacji konfiguracja m może zostać zmieniona. Niektóre z zapisanych symboli {232} utworzą ciąg cyfr, który jest dziesiętnym obliczanej liczby rzeczywistej. Pozostałe są tylko szorstkimi notatkami „wspomagającymi pamięć”. Tylko szorstkie nuty będą mogły zostać usunięte. Niektóre z zapisanych symboli {232} utworzą ciąg cyfr, który jest dziesiętnym obliczanej liczby rzeczywistej. Pozostałe są tylko szorstkimi notatkami „wspomagającymi pamięć”. Tylko szorstkie nuty będą mogły zostać usunięte. Niektóre z zapisanych symboli {232} utworzą ciąg cyfr, który jest dziesiętnym obliczanej liczby rzeczywistej. Pozostałe są tylko szorstkimi notatkami „wspomagającymi pamięć”. Tylko szorstkie nuty będą mogły zostać usunięte.

Uważam, że operacje te obejmują wszystkie te, które są używane do obliczania liczby. Obrona tego sporu będzie łatwiejsza, gdy teoria maszyn będzie znana czytelnikowi. Dlatego w następnej części rozwijam teorię i zakładam, że rozumie się, co należy rozumieć przez „maszynę”, „taśmę”, „skanowane” itp.

Jest to fragment oryginalnego artykułu Turinga „O liczbach obliczalnych z zastosowaniem do Entscheidungsproblem”.

Współczesnym dobrym towarzyszem pracy, którą polecam, jest Annotated Turing Charlesa Petzolda.

Jak widać, Google po prostu próbowało przypominać maszynę, która jest bardzo podobna do opisu Turinga.

EDYCJA: Zakładając, że pełny alfabet Google'a to ten pokazany na końcu gry po kliknięciu ikony króliczka i biorąc pod uwagę fakt, że tworzy nieskończoną sekwencję, ma więcej wierszy i kolumn (więc możemy założyć, że możemy dodać dowolne ), ma lewe skoki (a także nakładające się na lewe skoki) w dowolnym rzędzie , ma warunkowy i bezwarunkowy skok między sąsiednimi rzędami, myślę, że Turing jest ukończony .

W łamigłówkach skoki są dozwolone na obu liniach, ale nie mogą się pokrywać. Na końcowym doodle sekwencji królików na końcu gry, pozwalają na skoki w każdej linii i mogą być zagnieżdżone w nawiasach, więc [()] jest dozwolone, ale ([)] wydaje się niedozwolone.

Wykorzystam następujące założenia:

1. $0$$1$$\epsilon$
2. Maszyna może korzystać z dowolnej stałej liczby linii
3. Skoki w lewo są dozwolone na dowolnej linii (użyję jednego skoku w lewo na linię)
4. $\epsilon$$0$$1$

Przy tych założeniach Google Doodle Machine jest Turing Complete .

$0$$1$$\epsilon$$0$$1$$n$

$3(n - 1) + 1$$5n + 1$

$\epsilon$$0$$1$$\epsilon$$0$$1$$0$$1$

GDM symuluje TM w następujący sposób:

1. $1$
2. $j$
3. $\epsilon$$0$$1$
4. $\epsilon$
5. $0$$1$
6. $0$$1$

Wybierz swoją ulubioną uniwersalną bazę TM i zastosuj ją w powyższej procedurze, aby uzyskać uniwersalną GDM.