Desafío de programación Java: la creación de una máquina de Turing sencilla

En 1936, el matemático Alan Turing concibió un tipo aparentemente simple de la máquina computacional llamado Máquina de Turing. Turing en realidad nunca construyó una máquina de Turing. En cambio, fue un dispositivo hipotético que él inventó para ayudar en el estudio de la computabilidad - es decir, si los problemas complejos pueden ser resueltos por pasos de cálculo y si una máquina puede ser concebido que puede resolver cualquier problema computable. (Si usted está interesado en saber más sobre la historia o la aplicación de las máquinas de Turing, puede encontrar muchos artículos sobre ellos en Internet. Sólo tiene que utilizar cualquier proveedor de búsqueda para buscar "máquina de Turing".)

El funcionamiento de una máquina de Turing es simple. Encarna a pocos conceptos básicos:

1. El corazón de una máquina de Turing es una cinta infinitamente largo que se divide en células en el que la información se puede escribir.

   En la práctica real, por supuesto, no hay ningún dispositivo físico puede tener un número infinito de células. Pero en la teoría de una Máquina de Turing, la cinta es infinito.

2. La información que se puede escribir en cada celda se limita a un solo símbolo, tal como un 0 o un 1. Sin embargo, la información puede ser representado por los valores combinados de células sucesivas.

   Por ejemplo, es posible representar valores numéricos por las ocurrencias sucesivas del símbolo 1 seguido de un 0. Así, 1110 representan el valor 3 porque hay tres 1's- 111111011110 podría representar los valores de 6 y 4 (seis de 1 seguido de un cero, seguido a las cuatro de 1 seguido de otro cero).

3. La máquina de Turing contiene una la cabeza de lectura y escritura siempre que se coloca sobre uno (y sólo uno) de las células de la cinta.

   Esta cabeza de lectura-escritura puede leer el símbolo que está contenido en la célula. También puede borrar el símbolo y, si se desea, escribir un nuevo símbolo en su lugar. La célula sobre la que la cabeza de lectura-escritura está posicionado se conoce como el celda actual o el celular cabeza.

4. La cinta está motorizado de manera que se puede mover hacia la izquierda o la derecha debajo de la lectura y escritura cabeza de una célula a la vez.

5. La máquina tiene una estado, el cual está representado por un símbolo como una letra del alfabeto.

Al igual que cualquier computadora, una máquina de Turing se puede programar. Sin embargo, un programa para una máquina de Turing no se parece remotamente un programa Java.

En su lugar, un programa de la máquina de Turing es simplemente un conjunto de reglas que se evalúan para determinar qué acciones debe tomar la máquina. Cada regla identifica una acción a ser tomada cuando la celda actual contiene un símbolo dado y el equipo está en un estado determinado. Por ejemplo, una regla podría dictar lo que debe hacer si la celda actual contiene un 1 y el estado de la máquina es "a".

Cada regla puede especificar cualquiera de tres acciones:

• Borre la celda actual o escribir un nuevo valor a la celda.

• Mover la cinta una celda hacia la izquierda o una celda a la derecha.

• Cambie el estado de la máquina a un nuevo estado.

Por ejemplo, una regla puede especificar que si la celda actual contiene un 1 y el estado de la máquina es "una," la Máquina de Turing debe escribir un 0 en la celda actual, avanzar en la cinta una celda a la derecha, y cambiar el estado de la máquina a "b".

Además de un programa, la cinta de la máquina de Turing puede tener un valor inicial.

Eso es todo, eso es toda la definición de una máquina de Turing. A pesar de su simplicidad, una Máquina de Turing puede calcular cualquier cosa de 2 + 2 a la trayectoria de un cohete a Marte.

Para este desafío, es necesario crear un muy simple máquina de Turing. Para simplificar el problema, aceptar las siguientes limitaciones en esta versión de la máquina de Turing:

• La cinta no tiene que ser infinita. Se puede utilizar cualquier función de Java - una matriz, una cadena, o una colección - para representar la cinta.

  (Tenga en cuenta que, aunque la cinta no tiene que ser infinito, debe ser capaz de moverse fácilmente hacia la izquierda o derecha de la celda actual. Si decide utilizar una matriz, no comience con la celda actual en el elemento 0, ya que no será capaz de moverse izquierda desde allí).

• Una célula puede estar vacío o puede contener cualquier letra o número. Una celda vacía se representa con un carácter de subrayado.

• El estado puede ser cualquier carácter alfanumérico único.

• El programa para la Máquina de Turing se lee de un archivo de texto. Este archivo de texto contiene una regla por línea. Cada regla contiene cinco caracteres, separados por espacios, que proporcionan los detalles para cada regla, de la siguiente manera:

• Celular actual: El valor que se ajustará a la celda actual.

• Estado actual: El valor que se ajustará para el estado actual de la máquina.

• Nuevo celular: El valor para escribir en la nueva celda. _ Para borrar la celda, * para salir de la celda sin cambios.

• Movimiento: L o R para mover la cinta hacia la izquierda o la derecha; H para detener la programación de cualquier otro carácter para no mover la cinta.

• Nuevo estado: El nuevo valor para el estado de la máquina.

1 a 0 L b

La siguiente figura muestra la interfaz de usuario para la solución de la muestra, pero usted es libre de usar cualquier diseño de la interfaz de usuario que te gustaría para este proyecto.

Estas son algunas de las consideraciones para la creación de la interfaz:

• Valor y celda actual: Como mínimo, usted debe mostrar el valor de la cinta y resaltar la celda actual.

• Herramientas y pantalla: También debe proporcionar la capacidad de iniciar, detener o reiniciar la ejecución del programa, y ​​usted debe mostrar los resultados de cada paso del programa.

• La ejecución del programa: Puede proporcionar una manera para que el usuario ejecute el programa cargado de principio a fin, así como una forma para que el usuario de un solo paso a través del programa haciendo clic en un botón para ejecutar cada paso del programa.

• Cargando el programa: Usted debe proporcionar botones que permiten al usuario cargar un programa de la máquina de Turing de un archivo de texto y que permite al usuario reiniciar la máquina para ejecutar el programa de nuevo.

He aquí un consejo para la aplicación de la cinta infinita: Utilice tres variables de cadena para mantener los valores de la cinta, uno para el carácter único almacenado en la celda actual, una segunda para los personajes a la izquierda de la celda actual, y un tercero para los personajes la derecha de la celda actual. A continuación, puede mover fácilmente la celda actual izquierda o derecha utilizando la combinación correcta de concatenación y las operaciones de subcadena.

Usted puede encontrar la solución a este reto en el Descargas pestaña de El Java All-in-One For Dummies, Página cuarto producto Edition.

¡Buena suerte!