Interesuje mnie koncepcja „kompletności r-Turinga”, zdefiniowana przez Axelsena i Glück (2011) . System jest gotowy do r-Turinga, jeśli może obliczyć ten sam zestaw funkcji, co odwracalna maszyna Turinga, bez generowania żadnych „śmieciowych” danych. Jest to to samo, co możliwość obliczenia każdej funkcji, która jest (a) obliczalna i (b) iniekcyjna.
Chciałbym obliczeniowo zbadać przestrzeń obliczalnych funkcji iniekcyjnych. W tym celu szukam „najbardziej minimalnego” odwracalnego języka programowania --- czegoś, co może odgrywać równoważną rolę dla obliczalności r-Turinga, którą rachunek lambda odgrywa dla obliczalności Turinga.
Wiem, że istnieje wiele języków odwracalnych, które ludzie opracowali i udowodnili, że są kompletne. Są one jednak opracowywane z myślą o praktycznych zastosowaniach, dlatego ich autorzy koncentrują się na nadaniu im wyrazistych cech, a nie na minimalizacji.
Czy ktoś wie, czy tak minimalny odwracalny język został opisany, czy też prowadzone są badania w tym kierunku? Jestem dość nowy w literaturze na ten temat, więc łatwo mogłem to przegapić. Alternatywnie, czy ktoś ma wgląd w to, jak można stworzyć taki język?
Poniżej znajduje się podsumowanie tego, czego szukam. Nie wiem, czy można go stworzyć, modyfikując sam rachunek lambda, czy też należałoby użyć zupełnie innego rodzaju języka.
- Pełny język r-Turinga - oblicza wszystkie obliczalne funkcje odwracalne i może tylko obliczać funkcje odwracalne
- Składnia i semantyka są jak najmniejsze. (Np. Rachunek Lambda ma tylko definicje funkcji i aplikacje, i nic więcej.) Nie jest konieczne, aby składnia lub semantyka była powiązana z tymi z rachunku lambda, chociaż mogą być.
- Program = dane. Oznacza to, że programy działają na wyrażeniach, a nie na jakichkolwiek innych danych. Gwarantuje to, że dane wyjściowe programu można zawsze interpretować jako program. To prawdopodobnie oznacza, że musi to być funkcjonalny, a nie imperatywny styl języka.
- Istnieje jakiś systematyczny sposób przekonwertowania programu na jego odwrotność, który nie wymaga znacznie więcej obliczeń niż ten, który jest wykonywany w obliczeniach odwrotnych. (Nie wszystkie języki odwracalne mają tę właściwość, ale niektóre mają.)
Powinienem podkreślić, że podejście Axelsen i Glück do obliczeń odwracalnych różni się od dobrze znanego podejścia ze względu na Bennetta, w którym program (na ogół nieodwracalny) jest odwracalny poprzez zwrócenie pewnych informacji o historii obliczeń wraz z danymi wyjściowymi. Kompletność r-Turinga polega na możliwości obliczenia funkcji iniekcyjnych bez żadnych dodatkowych danych wyjściowych. Istnieje kilka rzeczy zwanych odmianami „odwracalnego rachunku lambda”, które są odwracalne w sensie Benneta - nie tego szukam.