Tarpits reversíveis de Turing?

Esta pergunta é sobre se existem tarpits reversíveis conhecidos de Turing, onde "reversível" significa no sentido de Axelsen e Glück , e "tarpit" é um conceito muito mais informal (e pode não ser uma escolha muito boa de palavra), mas farei o possível para explicar o que quero dizer com isso.

O que quero dizer com "tarpit"

Alguns modelos de computação são projetados para serem úteis de alguma forma. Outros, por acaso, são completos de Turing e realmente não têm propriedades particularmente úteis; estes são conhecidos como "tarpits de Turing". Os exemplos incluem a linguagem Brainfuck , o autômato celular Rule 110 e a linguagem Bitwise Cyclic Tag (que eu gosto porque é muito fácil de implementar e qualquer string binária é um programa válido).

Não existe uma definição formal de "taruring de Turing", mas, para esta pergunta, estou usando-o para significar um sistema bastante simples (em termos de ter um pequeno número de "regras") que "simplesmente acontece" como Turing completo, sem seu estado interno tendo qualquer significado semântico óbvio. O aspecto mais importante para meus propósitos é a simplicidade das regras, e não a falta de semântica óbvia. Basicamente, estamos falando sobre o tipo de coisa sobre a qual Stephen Wolfram escreveu um livro muito grande , embora ele não tenha usado a palavra "tarpit".

O que quero dizer com "reversível"

Estou interessado em computação reversível. Em particular, estou interessado em idiomas que são r-Turing completos, no sentido de Axelsen e Glück , o que significa que eles podem calcular todas as funções injetáveis ​​computáveis ​​e só podem calcular funções injetáveis. Agora, existem muitos modelos de computação que são reversíveis nesse sentido, como a máquina de Turing universal reversível da Axelsen ou a linguagem reversível de alto nível Janus . (Existem muitos outros exemplos na literatura; é uma área ativa de pesquisa.)

Deve-se notar que a definição de Axelsen e Glück de completude r-Turing é uma abordagem diferente para computação reversível do que a abordagem usual de Bennett. Na abordagem de Bennett, é permitido que um sistema produza "dados de lixo" que são jogados fora no final do cálculo; sob tais condições, um sistema reversível pode ser Turing completo. No entanto, na abordagem de Axelsen e Glück, o sistema não tem permissão para produzir esses "dados indesejados", o que restringe a classe de problemas que ele pode calcular. (Portanto, "r-Turing complete" em vez de "Turing complete".)

_{Nota: o papel Axelsen e Glück está atrás de uma parede de pagamento. Isso é lamentável - até onde eu sei, não há atualmente nenhum recurso que não seja de pagamento pago sobre a completude de r-Turing. Vou tentar iniciar uma página da Wikipedia se tiver tempo, mas não promessas.}

O que estou olhando

Os exemplos de computação reversível mencionados acima são todos "semanticamente carregados". Isso é bom na maioria dos contextos, mas significa que as regras necessárias para atualizar seu estado a cada etapa do tempo são bastante complexas. Estou procurando os "tarpits" da computação reversível. Ou seja, sistemas mais ou menos arbitrários com regras bastante simples que "simplesmente acontecem" como linguagens completas de r-Turing. Reitero que não há uma definição formal do que estou procurando, mas saberei quando a vir e acho uma coisa razoável a se perguntar.

Sei que há várias coisas que quase se encaixam na conta, mas não exatamente. Existem vários autômatos celulares reversíveis que foram mostrados como Turing completos. A formiga de Langton (um tipo de máquina de Turing bidimensional com uma função de transição de estado reversível bastante arbitrária e bastante simples) também é Turing completa, desde que suas condições iniciais permitam conter infinitos padrões de repetição. No entanto, com esses sistemas, não é trivial definir um mapeamento de seu estado para uma "saída" de forma que nenhum dado indesejado seja descartado. Estou interessado especificamente em sistemas que podem ser considerados como tendo uma entrada, realizando alguma sequência de transformações (reversíveis) nela e depois (se terminarem) retornando alguma saída.

(Espero que esta pergunta seja mais fácil de responder do que a anterior, sobre um equivalente reversível ao cálculo lambda.)

"r-complete" parece ser um conceito relativamente novo inventado por Axelsen e Glück ~ 2011, possivelmente não considerado muito por outros autores, e se pergunta se há uma prova diferente do que Turing completo.

Estou tomando esta pergunta detalhada e tortuosa para pedir basicamente:

• um sistema completo simples de Turing
• reversível

tente autômatos celulares reversíveis completos de Turing, por exemplo:

• Autômatos celulares universais reversíveis e de dois estados em três dimensões Miller / Fredkin

  Um novo autômato celular reversível (RCA) de dois estados é descrito. Este RCA tridimensional mostra-se capaz de computação universal. Além disso, são oferecidas evidências de que esse RCA é capaz de construção universal.

• K. Imai e K. Morita, Um autômato celular reversível triangular bidimensional e bidimensional com 8 estados de computação , Teórica Computer Science 231 (2000), n. 2, 181-191.

  Resumo: Um autômato celular reversível (RCA) é um autômato celular (CA) cuja função global é injetiva e cada configuração possui no máximo um predecessor. Margolus mostrou que existe uma RCA bidimensional bidimensional universal de computação. Mas sua RCA tem um vizinho não uniforme, então Morita e Ueno propuseram a RCA universal de computação de 16 estados usando autômatos celulares particionados (PCA). Como o PCA pode ser considerado como uma subclasse da CA padrão, seus modelos têm um vizinho padrão. Neste artigo, mostramos que o número de estados dos modelos de Morita e Ueno pode ser reduzido. Para diminuir o número de estados de seus modelos com propriedades de preservação isotrópica e de preservação de bits, usamos um 3 vizinho triangular e, portanto, uma RCA de 8 estados pode ser possível. Este é o RCA bidimensional de menor estado sob a condição de propriedade isotrópica na estrutura do PCA. Mostramos que nosso modelo pode simular elementos básicos do circuito, como fios unitários, elementos de retardo, fios cruzados, interruptores e inversores, e é possível construir uma porta de Fredkin combinando esses elementos. Como o portão de Fredkin é conhecido por ser um portão lógico universal, nosso modelo tem universalidade de computação.

foi encontrado como referência nesta pesquisa de autoridades de certificação que pode ter outras pistas úteis na investigação (por exemplo, ver seção 7, Reversibilidade e Universalidade). (às 17 páginas e 86 refs, o título está quase irônico.)

UNIVERSALIDADES NA PESQUISA CELULAR DE AUTOMATA A (CURTA) Ollinger