Lonas reversibles de Turing?

Esta pregunta es acerca de si hay alguna lona de Turing reversible conocida, donde "reversible" significa en el sentido de Axelsen y Glück , y "tarpit" es un concepto mucho más informal (y podría no ser una muy buena elección de palabra), pero haré todo lo posible para explicar lo que quiero decir con eso.

Lo que quiero decir con "tarpit"

Algunos modelos de computación están diseñados para ser útiles de alguna manera. Otros resultan ser Turing completos y realmente no tienen propiedades particularmente útiles; estos se conocen como "lonas de Turing". Los ejemplos incluyen el lenguaje Brainfuck , el autómata celular Rule 110 y el lenguaje Bitwise Cyclic Tag (que me gusta porque es muy fácil de implementar y cualquier cadena binaria es un programa válido).

No existe una definición formal de "tarpit de Turing", pero para esta pregunta la estoy usando para referirme a un sistema bastante simple (en términos de tener un pequeño número de "reglas") que "simplemente sucede" que es Turing completo, sin su estado interno tiene algún significado semántico obvio. El aspecto más importante para mis propósitos es la simplicidad de las reglas, más que la falta de una semántica obvia. Básicamente estamos hablando del tipo de cosas sobre las que Stephen Wolfram escribió una vez un libro muy grande , aunque no usó la palabra "tarpit".

Lo que quiero decir con "reversible"

Estoy interesado en el cálculo reversible. En particular, me interesan los lenguajes que están completos en T-ruring , en el sentido de Axelsen y Glück , lo que significa que pueden calcular todas las funciones inyectables computables y solo pueden calcular funciones inyectivas. Ahora, hay muchos modelos de cálculo que son reversibles en este sentido, como la máquina universal de Turing reversible de Axelsen o el lenguaje reversible de alto nivel Janus . (Hay muchos otros ejemplos en la literatura; es un área activa de investigación).

Cabe señalar que la definición de Axelsen y Glück de la integridad de r-Turing es un enfoque diferente a la computación reversible que el enfoque habitual debido a Bennett. En el enfoque de Bennett, se permite que un sistema produzca "datos basura" que se desechan al final del cálculo; En tales condiciones, se puede completar un sistema reversible. Sin embargo, en el enfoque de Axelsen y Glück, el sistema no puede producir tales "datos basura", lo que restringe la clase de problemas que puede calcular. (Por lo tanto, "r-Turing completo" en lugar de "Turing completo").

_{Nota: el papel de Axelsen y Glück está detrás de un muro de pago. Esto es desafortunado: que yo sepa, actualmente no hay ningún recurso que no sea de pago sobre el tema de la integridad de r-Turing. Intentaré comenzar una página de Wikipedia si tengo tiempo, pero no prometo nada.}

Lo que estoy buscando

Los ejemplos de computación reversible mencionados anteriormente están más bien "semánticamente cargados". Esto es algo bueno en la mayoría de los contextos, pero significa que las reglas requeridas para actualizar su estado en cada paso de tiempo son bastante complejas. Estoy buscando los "lonas" de la informática reversible. Es decir, sistemas más o menos arbitrarios con reglas bastante simples que "resultan" ser lenguajes completos. Reitero que no hay una definición formal de lo que estoy buscando, pero lo sabré cuando lo vea, y creo que es algo razonable preguntar.

Hay varias cosas que sé que casi se ajustan a la factura, pero no del todo. Hay varios autómatas celulares reversibles que han demostrado ser completos de Turing. La hormiga de Langton (una especie de máquina de Turing bidimensional con una función de transición de estado reversible bastante arbitraria y bastante simple) también está completa, siempre y cuando se permita que sus condiciones iniciales contengan patrones repetitivos infinitos. Sin embargo, con estos sistemas no es trivial definir una asignación de su estado a una "salida" de tal manera que no se descarten datos basura. Me interesan específicamente los sistemas que pueden considerarse como tomar una entrada, realizar alguna secuencia de transformaciones (reversibles) y luego (si terminan) devolver algo de salida.

(Espero que esta pregunta sea más fácil de responder que la anterior relacionada con un equivalente reversible al cálculo lambda).

"r-complete" parece ser un concepto relativamente nuevo inventado por Axelsen y Glück ~ 2011, posiblemente no considerado mucho por otros autores, y me pregunto si hay una prueba diferente a la de Turing complete.

Estoy tomando esta pregunta detallada y tortuosa para hacer básicamente:

• un sistema completo simple de Turing
• reversible

pruebe los autómatas celulares reversibles completos de Turing, por ejemplo:

• Autómatas celulares universales, reversibles, de dos estados en tres dimensiones Miller / Fredkin

  Se describe un nuevo autómata celular reversible de dos estados (RCA). Se muestra que este RCA tridimensional es capaz de computación universal. Además, se ofrece evidencia de que este RCA es capaz de construcción universal.

• K. Imai y K. Morita, Un autómata celular triangular reversible bidimensional de 8 estados computacional universal, Theoretical Computer Science 231 (2000), no. 2, 181-191.

  Resumen: Un autómata celular reversible (RCA) es un autómata celular (CA) cuya función global es inyectiva y cada configuración tiene como máximo un predecesor. Margolus demostró que existe un RCA bidimensional bidimensional de computación universal. Pero su RCA tiene un vecino no uniforme, por lo que Morita y Ueno propusieron un RCA universal de cómputo de 16 estados utilizando autómatas celulares particionados (PCA). Debido a que PCA puede considerarse como una subclase de CA estándar, sus modelos tienen un vecino estándar. En este artículo, mostramos que se puede reducir el número de estados de los modelos de Morita y Ueno. Para disminuir el número de estados de sus modelos con propiedades isotrópicas de preservación de bits, utilizamos un vecino triangular de 3 vecinos y, por lo tanto, puede ser posible un RCA de 8 estados. Este es el RCA bidimensional de estado más pequeño bajo la condición de propiedad isotrópica en el marco de PCA. Mostramos que nuestro modelo puede simular elementos básicos del circuito, como cables unitarios, elementos de retardo, cables cruzados, puertas de conmutación y puertas de conmutación inversas, y es posible construir una puerta de Fredkin combinando estos elementos. Como se sabe que la puerta de Fredkin es una puerta lógica universal, nuestro modelo tiene universalidad de cómputo.

se encontró como referencia en esta encuesta de AC que podría tener otras pistas útiles en la investigación (por ejemplo, ver sección 7, Reversibilidad y universalidad). (con 17 pgs y 86 referencias, el título está al borde de la ironía).

UNIVERSALIDADES EN LA ENCUESTA DE AUTOMATA CELULAR A (CORTA) Ollinger