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