Este proyecto presenta una implementación de la técnica de ordenamiento 'Bubble Sort' (ordenamiento de burbuja) en una Máquina de Turing (MT), un modelo computacional teórico fundamental en la informática. La MT está definida mediante una tabla de transiciones en formato YAML, lo que la hace compatible con la plataforma online turingmachine.io, permitiendo visualizar el proceso de ordenamiento paso a paso. Se proporcionan dos variantes: una para números decimales (donde cada dígito ocupa una celda) y otra para números representados en notación unaria (donde cada dígito se representa con una secuencia de '1's separados por '0's).
¿Cómo funciona? En la versión decimal, la MT realiza recorridos secuenciales de izquierda a derecha comparando pares de dígitos adyacentes. Si están en el orden incorrecto, se intercambian. El proceso se repite hasta que un recorrido completo no realiza ningún intercambio, indicando que la lista está ordenada. La versión unaria, debido a la representación de los números, utiliza un enfoque de 'marcado' para la comparación, alternando la marca de unidades en los números derecho e izquierdo para determinar cuál es mayor. La MT decimal utiliza 25 estados para controlar el proceso, mientras que la unaria requiere aproximadamente 31 estados debido a la complejidad de la comparación unaria.
¿Para qué sirve? Aunque el Bubble Sort es un algoritmo de ordenamiento ineficiente en la práctica, esta implementación sirve como una herramienta didáctica para comprender el funcionamiento de las Máquinas de Turing y cómo se pueden utilizar para resolver problemas computacionales. Es útil para estudiantes de informática, entusiastas de la computación teórica y cualquier persona interesada en explorar los fundamentos de la computación.
Consideraciones: La implementación está escrita en Python 3.10+ y requiere la librería PyYAML. El código incluye un emulador de Máquina de Turing que permite ejecutar y verificar el ordenamiento localmente. La versión decimal es más fácil de visualizar en turingmachine.io debido a su simplicidad. La versión unaria, aunque más compleja, demuestra cómo se pueden adaptar las Máquinas de Turing para manejar diferentes representaciones de datos. El proyecto también incluye un generador de archivos YAML que permite crear Máquinas de Turing para diferentes secuencias de números decimales, facilitando la experimentación.