Sistemas de Post

propuesto por AverageUser

Crear un simulador de sistemas de Post.

Enunciado
Los sistemas de post son un modelo matemático de computación equivalentes a maquinas de turing.

Un sistema (de post) en especifico se representa como una secuencia finita de pares. Estos pares a la ves están compuestos por dos palabras (secuencias de símbolos finita).

Dado un sistema de post como es descrito, y una palabra inicial P, el algoritmo que se realiza puede ser descrito de la siguiente forma:


1- Se escoge el primer par (U,V) de el sistema; si no existe se termina el computo y se entrega la palabra final.

2- Si U es prefijo de P, se le corta el comienzo U a P y se le pega V al final, para despues comenzar del paso 1 (usando el sistema completo, y el nuevo P). Ejemplo; P = AABB , (U,V) = (AA,CC) resultaría en BBCC

3- Si en cambio U no es prefijo de P, entonces se prueba el siguiente par del sistema. Si ninguno de estos produce un cambio se termina el computo (ya dicho en paso 1).

Aquí hay un ejemplo de una simulación de la conjetura de collatz  en notación unaria.

Dominio Palabra Inicial = {0}*.
Intencion: Si la Conjetura de Collatz es cierta, se detiene con 0; en caso contrario, podria no detenerse.
Ejemplo: si Palabra Inical = 00000000000000000000, entonces Palabra Final = 0.

(00, 1011)
(010, 1011)
(1011, 0)
(110, 000)
(1110, 000)

Ver todo el enunciado

Preguntas sobre el desafío

¿Tienes dudas sobre el desafío? plantéala aquí

Plantea tu pregunta

5 Soluciones

Dar mi solución

0votos
Sistemas de Post en Haskell
por

josejuan

hace 3 meses

Ésta es la más eficiente, tiene coste lineal (en la palabra total generada). Monta un árbol con las bifurcaciones del programa de entrada. De todos modos insisto que ésto es reinventar la rueda, compilándolo a código máquina, tenemos incluso predicción de salto (el pattern matching compila a condiciones de código máquina).

0votos
Sistemas de Post en Haskell
por

josejuan

hace 3 meses

Si no es por no implementar explícitamente los pasos de la máquina, es que usando pattern matching podemos usar Haskell directamente y además no será interpretado, sino que se compilará a código máquina. Pero ahí va.

Dar mi solución