Jakim automatem jest Google Turing Doodle?


10

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 Zrzut ekranu z doodle

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


9
Oczywiście maszyna Turinga! en.wikipedia.org/wiki/Turing_machine Być może byłeś zdezorientowany, ponieważ system przejścia jest funky.
Huck Bennett

W silniku sterującym znajduje się również „operator skoku w lewo”, który umożliwia powrót do poprzedniej pozycji, ale tylko w górnym rzędzie; ponadto nie ma możliwości „nałożenia” dwóch skoków (jeden na drugi). Bez operatora skoku maszyna jest równoważna z DFA (akcje w silniku sterującym są „wykonywane” od lewej do prawej), ale również przy ograniczonym operatorze skoku w lewo maszyna wydaje się nie dość mocna, aby symulować LBA (ale ja tego nie zrobiłem za dużo o tym myśleć). W każdym przypadku Turing nie może być ukończony, ponieważ taśma jest skończona.
Marzio De Biasi

1
@Marzio De Biasi: Masz rację, że ta łamigłówka zawiera instrukcje skoku, a bez nich model jest oczywiście bardzo słaby, ponieważ maszyna może działać tylko przez stały czas. (Nie jestem pewien, co rozumiesz przez „odpowiednik DFA”). Jakie ograniczenia nałożone na instrukcje skoku mogą zmienić odpowiedź. „Taśma jest skończona” jest prawdopodobnie błędnym założeniem.
Tsuyoshi Ito

Google utrzymuje ich Doodles dostępny (choć najwyraźniej nie zawsze interaktywnych wersji).
Raphael

@TsuyoshiIto: Mam na myśli (ale być może się mylę), że mając maszynę bez pętli, możesz zbudować DFA, który ją symuluje. Jeśli zezwolisz na dowolne skoki w obu kierunkach, które mogą się nakładać, maszyna natychmiast „dobiera końca” (zakładając nieskończoną taśmę) nawet z dwoma tylko rzędami (stany można „spłaszczyć” poziomo). Nie wiem, co się stanie, jeśli zezwolisz na skoki w lewo, które mogą się nakładać (ale tylko w pierwszym rzędzie) i dowolną liczbę rzędów (ale kontrola w niższych rzędach może być tylko w górę lub w dół). Być może to miłe pytanie dla cs.stackexchange.com
Marzio De Biasi,

Odpowiedzi:


10

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

M4

atdoodle

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

TdoodleTC

TMDM


nieeee! pobiłeś mnie do tego! Właśnie pisałem, jak zrobić dowolną TM w przestrzeni stanu zamiast taśmy. Jednak twoje podejście jest ładniejsze, ponieważ wykorzystuje tylko jeden skok. Dobra robota! Czekaj, w jaki sposób twoje urządzenie odbiera dane wejściowe?
Artem Kaznatcheev

@ marzio-de-biasi Dobra robota!
pepper_chico

1
@ArtemKaznatcheev: odbiera dane na taśmie; oczywiście musisz go zakodować zgodnie z oryginalnymi symbolami alfabetu emulacji TM i pozostawić puste miejsca na reprezentację stanu.
Marzio De Biasi

Znak młodości alen turing. Podobało mi się czytanie
iDroid

nie w pełni przekonana o kompletności TM. nie sądzę, że zajmowałeś się przypadkiem, w którym TM zapisuje nowe puste kwadraty, które nie zostały wcześniej zdefiniowane na taśmie wejściowej. który jest wymagany dla kompletności TM, w przeciwnym razie jest to tylko skończone obliczenie.
vzn

5

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 .


ale czy ostro wdrożyli maszynę Turinga? ta ma skończoną taśmę, więc jest to zauważalna różnica. czy to różnica robi różnicę? czy faktycznie wprowadzili słabszą maszynę?
bjelli

2
@bjelli Cóż, nie mogę tego zapewnić, ponieważ ponieważ nie zaprojektowałem go, nie znam wszystkich zasad dotyczących ich maszyny. Ale jeśli dojdziesz do finału gry, możesz kliknąć ikonę Króliczka, która prowadzi do dłuższej taśmy, sprawdź analizę tutaj: sbf5.com/~cduan/technical/turing . Tak więc może nie być ograniczenia liczby linii, które może uzyskać maszyna, co doprowadziłoby cię do taśmy dowolnego rozmiaru.
pepper_chico

plz narysuj dowód, że jego Turing się zakończył
dniu

4

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. 01ϵ
  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. ϵ01

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

01ϵ01n

3(n1)+15n+1

Maszyna Google Doodle

ϵ01ϵ0101

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

  1. 1
  2. j
  3. ϵ01
  4. ϵ
  5. 01
  6. 01

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

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.