Odwracalne plandeki Turinga?

To pytanie o to, czy istnieją jakieś znane tarpits odwracalny Turinga, gdzie „odwracalne” oznacza w sensie Axelsen i Glück , a „Tarpit” jest znacznie bardziej nieformalny pojęcie (i może nie być bardzo dobrym wyborem słowa), ale postaram się wyjaśnić, co mam na myśli.

Co rozumiem przez „tarpit”

Niektóre modele obliczeń zaprojektowano tak, aby były użyteczne. Inni akurat są kompletni w Turinga i tak naprawdę nie mają żadnych szczególnie użytecznych właściwości; są one znane jako „plandeki Turinga”. Przykłady obejmują język Brainfuck , automat komórkowy Rule 110 oraz język Bitwise Cyclic Tag (który podoba mi się, ponieważ jest bardzo łatwy do wdrożenia, a dowolny ciąg binarny jest prawidłowym programem).

Nie ma formalnej definicji „tarniny Turinga”, ale w tym pytaniu używam go w znaczeniu dość prostego systemu (pod względem posiadania małej liczby „reguł”), który „po prostu zdarza się” jest kompletnym Turingiem, bez jego stan wewnętrzny ma jakiekolwiek oczywiste znaczenie semantyczne. Najważniejszym aspektem dla moich celów jest prostota reguł, a nie brak oczywistej semantyki. Zasadniczo mówimy o rzeczach, o których Stephen Wolfram napisał kiedyś bardzo dużą książkę , chociaż nie użył słowa „tarpit”.

Co rozumiem przez „odwracalny”

Interesuje mnie obliczanie odwracalne. W szczególności interesują mnie języki, które są kompletne r-Turinga, w sensie Axelsena i Glück'a , co oznacza, że ​​mogą obliczyć każdą obliczalną funkcję iniekcyjną i mogą tylko obliczać funkcje iniekcyjne. Obecnie istnieje wiele modeli obliczeń odwracalnych w tym sensie, takich jak odwracalna uniwersalna maszyna Turinga Axelsena lub odwracalny język wysokiego poziomu Janus . (W literaturze istnieje wiele innych przykładów; jest to aktywny obszar badań).

Należy zauważyć, że definicja kompletności r-Turinga autorstwa Axelsena i Glück'a jest odmiennym podejściem do obliczeń odwracalnych niż podejście typowe ze względu na Bennetta. W podejściu Bennetta system może generować „śmieciowe dane”, które są wyrzucane na końcu obliczeń; w takich warunkach system odwracalny może być kompletny. Jednak w podejściu Axelsena i Glück'a system nie może wytwarzać takich „śmieciowych danych”, co ogranicza klasę problemów, które może on wyliczyć. (Dlatego „r-Turing zakończony” zamiast „Turing zakończony”).

_{Uwaga: papier Axelsen i Glück znajduje się za zaporą. To niefortunne - o ile mi wiadomo, nie ma obecnie żadnych niepłatnych zasobów na temat kompletności r-Turinga. Spróbuję założyć stronę Wikipedii, jeśli będę miał czas, ale żadnych obietnic.}

Czego szukam

Wszystkie wyżej wymienione przykłady obliczeń odwracalnych są raczej „obciążone semantycznie”. Jest to dobra rzecz w większości kontekstów, ale oznacza to, że reguły wymagane do aktualizacji ich stanu na każdym etapie są dość złożone. Szukam „tarpitów” obliczeń odwracalnych. To znaczy mniej lub bardziej arbitralne systemy z dość prostymi regułami, które „akurat” są kompletnymi językami. Powtarzam, że nie ma formalnej definicji tego, czego szukam, ale będę o tym wiedział, kiedy to zobaczę, i myślę, że rozsądne jest pytanie o to.

Jest wiele rzeczy, które wiem o tym prawie pasują do rachunku, ale nie do końca. Istnieje kilka odwracalnych automatów komórkowych, które okazały się kompletne. Mrówka Langtona (rodzaj dwuwymiarowej maszyny Turinga z dość arbitralną i dość prostą funkcją odwracalnego przejścia stanu) również jest Turinga ukończona, o ile jej początkowe warunki mogą zawierać nieskończone powtarzające się wzory. Jednak w przypadku tych systemów zdefiniowanie odwzorowania ich stanu na „wynik” nie jest trywialne w taki sposób, że żadne niepotrzebne dane nie zostaną wyrzucone. Interesuje mnie w szczególności systemy, które można uznać za pobierające dane wejściowe, wykonujące na nim sekwencję (odwracalnych) transformacji, a następnie (jeśli zakończą) zwracające dane wyjściowe.

(Mam nadzieję, że na to pytanie będzie łatwiej odpowiedzieć niż na moje poprzednie pokrewne pytanie dotyczące odwracalnego odpowiednika rachunku lambda).

„r-complete” wydaje się być względnie nową koncepcją wymyśloną przez Axelsena i Glück ~ 2011, być może nie jest zbytnio rozważana przez innych autorów i zastanawiam się, czy istnieje dowód, że różni się ona od Turinga.

zadaję to pełne i okrężne pytanie, aby w zasadzie zadać:

• prosty kompletny system Turinga
• odwracalny

wypróbuj odwracalne automaty komórkowe firmy Turing, np .:

• Dwustanowe, dwustronne, uniwersalne automaty komórkowe w trzech wymiarach Miller / Fredkin

  Opisano nowatorski dwustanowy, odwracalny automat komórkowy (RCA). Ten trójwymiarowy RCA jest zdolny do uniwersalnego obliczenia. Dodatkowo oferowane są dowody na to, że RCA ma uniwersalną konstrukcję.

• K. Imai i K. Morita, Uniwersalny obliczeniowo dwuwymiarowy 8-stanowy trójkątny odwracalny automat komórkowy, Theoretical Computer Science 231 (2000), no. 2, 181–191.

  Streszczenie: Odwracalny automat komórkowy (RCA) to automat komórkowy (CA), którego funkcją globalną jest iniekcja, a każda konfiguracja ma co najwyżej jednego poprzednika. Margolus wykazał, że istnieje uniwersalny do obliczeń dwuwymiarowy dwustanowy RCA. Ale jego RCA ma niejednorodnego sąsiada, więc Morita i Ueno zaproponowali 16-stanowe uniwersalne obliczenia RCA z wykorzystaniem podzielonych automatów komórkowych (PCA). Ponieważ PCA można uznać za podklasę standardowego urzędu certyfikacji, ich modele mają standardowego sąsiada. W tym artykule pokazujemy, że można zmniejszyć liczbę stanów modeli Mority i Ueno. Aby zmniejszyć liczbę stanów z ich modeli z zachowaniem właściwości izotropowych i zachowujących bity, zastosowaliśmy trójkątny 3-sąsiad, dzięki czemu możliwe jest 8-stanowe RCA. Jest to dwuwymiarowy RCA o najmniejszym stanie pod warunkiem właściwości izotropowych w ramach PCA. Pokazujemy, że nasz model może symulować podstawowe elementy obwodu, takie jak druty jednostkowe, elementy opóźniające, druty krzyżujące, bramki przełączające i bramki zwrotne, i możliwe jest zbudowanie bramki Fredkin poprzez połączenie tych elementów. Ponieważ brama Fredkina jest znana jako uniwersalna brama logiczna, nasz model ma uniwersalność obliczeniową.

stwierdzono to jako odniesienie w tym badaniu urzędów certyfikacji, które mogą mieć inne pomocne wskazówki dotyczące dochodzenia (np. patrz ust. 7, Odwracalność i uniwersalność). (na 17 stronach i 86 pozycjach tytuł graniczy z ironią).

UNIWERSALNOŚĆ W AUTOMATY KOMÓRKOWEJ (KRÓTKA) ANKIETA Ollinger