Si el comportamiento de una TM con alguna cinta extraña se puede simular con una TM con una sola cinta normal, entonces la cinta extraña no ha agregado potencia al cálculo. Esto demostraría que estudiar la estructura de la cinta no es particularmente interesante.
Primero, considere una cinta 2d simple en forma de plano (llámela cinta 2). ¿Podemos simular el comportamiento de una 2-TM con una 1-TM (nuestra TM normal con una sola cinta)? Seguro que podemos. Primero, numere cada celda en el plano, saliendo en espiral desde el centro:
. . .
. . .
… 543 …
… 612 …
… 789 …
. . .
. . .
. . .
Ahora, podemos ‘desenrollar’ este plano 2D en la cinta única, de modo que cada celda en el plano corresponda a una celda en la cinta 1:
- ¿Cuánta potencia informática tiene Amazon Web Services?
- ¿Cuál es la diferencia entre las arquitecturas i386 y x86?
- ¿Por qué se invierten los controles y habilitaciones de algunos de los registros de microprocesadores (SAP-1)?
- Dada solo una lista de todas las notas tocadas en una pieza, junto con sus duraciones y tiempos de inicio, ¿se puede determinar algorítmicamente la clave?
- ¿Cuál es la diferencia entre multiprogramación, multitarea, multiprocesamiento y ejecución múltiple?
123456789 …
Dado que el diseño de la cuadrícula es obviamente computable, cuando el 2-TM se movería hacia la izquierda / derecha / arriba / abajo, el 1-TM puede calcular cuántos pasos hacia la izquierda / derecha necesita moverse para terminar en la celda correcta Por lo tanto, podemos simular el 2-TM en el 1-TM, y no ha obtenido ninguna potencia adicional.
Desde la forma de la solución, con suerte, puedes adivinar la generalización. Por ejemplo, podría encontrar un patrón similar para desenrollar una cinta 3 en la cinta 1 (piense en numerar los bloques en un cubo de rubix). De forma similar, esto muestra que [math] \ mathbb {N} ^ m [/ math] puede simularse para todas [math] m [/ math] (estructuras en forma de cuadrícula de dimensión arbitraria finita). También puede simular [math] \ mathbb {N} ^ \ infty [/ math], una cinta de cuadrícula de dimensiones infinitas.
También es posible que pueda obtener algunas topologías extrañas poniendo propiedades de conexión extrañas en la cinta. Digamos, todas las celdas pares están conectadas entre sí (puede pasar de la celda 4 a la celda 8 en 1 paso). Pero, siempre que las reglas que dictan estos movimientos se puedan describir de una manera algorítmica simple, son computables y, por lo tanto, se pueden simular mediante una TM de variedad de jardín. Y si las reglas de transición no son algorítmicas de esta manera, entonces la no computabilidad parece surgir de las reglas de transición, y no de la topología de la cinta.
