Máquina de Turing en el sistema de tipos

propuesto por josejuan

Animado por la elegante solución de @jmgomez al desafío Cálculo número primo con expresiones lambda, propongo realizar algún tipo de computación usando únicamente el sistema de tipos. Lógicamente, la computación debe resolverse en tiempo de compilación, nunca en tiempo de ejecución.

Enunciado
Animado por la elegante solución de @jmgomez al desafío Cálculo número primo con expresiones lambda, propongo realizar algún tipo de computación usando únicamente el sistema de tipos. Lógicamente, la computación debe resolverse en tiempo de compilación, nunca en tiempo de ejecución.

Es importante notar que el desafío consiste en que la computación se realice en tiempo de compilación y una única vez; por ejemplo, @jmgomez definió una computación para validar la primalidad de las instancias válidas para el tipo prime, dicha validación se realiza una vez cuando se compila (so pena que F* no tenga algún compilador...).

La computación a realizar es libre, pero debería ser algún tipo de computación (aunque sencilla) que se haga típicamente con el propio lenguaje y no con el sistema de tipos.

Por ejemplo, sumar, restar, exigir paridad, etc...
Preguntas sobre el desafío

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

Plantea tu pregunta

3 Soluciones

Dar mi solución

0votos
Máquina de Turing en el sistema de tipos en F#
por

jmgomez

hace 5 años

Computación bastante rudimentaria, sólo es capaz de sumar dígitos del 0 al 9 aunque cuantos se quiera. Como se ve en el código debería ser simple ampliarlo para más operaciones aritméticas y para aumentar el número de dígitos (e.g. tratando la computación como una calculadora).

Dar mi solución