1. No category

Una máquina de Turing para el algoritmo “Quicksort”
Edgar Fuentes Figueroa
Resumen
En base al algoritmo de ordenamiento Quicksort se elabora una máquina de Turing que utiliza este
algoritmo para ordenar una lista de n números naturales. Después de explicar el concepto de
complejidad del tiempo para una máquina de Turing, se calcula la complejidad del tiempo para la
máquina de Quicksort. Por último, se da una descripción de la prueba de Turing y las primeras
ideas acerca de la misma; se discute el problema de hacer el Test de Turing para el algoritmo
Quicksort y para el problema de armar el cubo Rubik.
Palabras clave: Alan Turing, Turing Test, Turing Machine, Quicksort, Time complexity.
Metodología –.Revisión bibliográfica de los conceptos de máquina de Turing, complejidad del
tiempo para una máquina de Turing y Test de Turing. A partir de los conocimientos obtenidos se
desarrolla el algoritmo Quicksort en una máquina de Turing. La complejidad del tiempo se obtiene
al correr la máquina con una entrada que genera el peor caso de ejecución.
Resultados – El tiempo de ejecución es de orden cuadrático lo cual coincide con resultados
analíticos.
Originalidad – Desarrollo de una máquina de Turing propia para el algoritmo Quicksort.
2
INTRODUCTION: M ÁQUINA DE TURING
Se presenta un modelo abstracto de cómputo diseñado en la década de 1930 por el matemático inglés
Alan Turing [1]; este modelo es llamado Máquina de Turing. El objetivo de Turing era demostrar las
limitaciones inherentes de los métodos algorítmicos. Mediante la formulación de un modelo capaz de
ejecutar un algoritmo cualquiera, Turing pudo afirmar que cualquier deficiencia en el modelo era de
hecho una deficiencia en el método algorítmico. A pesar de ser un modelo teórico, la Máquina de
Turing anticipó muchas de las características de las computadoras modernas.
Turing consideró una “computadora humana” trabajando con lápiz y papel. Decidió que sin pérdida de
generalidad, se podía suponer que la computadora humana operaba bajo reglas simples: Primero, las
únicas cosas escritas en el papel son símbolos de un alfabeto fijo; segundo, cada decisión tomada por
la computadora depende solo del símbolo que examina en su estado actual; tercero, aunque el estado
de la computadora cambie como resultado de examinar diferentes símbolos, solo es posible tener un
número finito de estados distintos.
Así, Turing definió los pasos primitivos que toma una computadora humana durante el proceso de
cómputo:
1. Examinar un símbolo en el papel;
2. Borra un símbolo o reemplazarlo por otro;
3. Quitar atención a algún símbolo y prestar atención a otro símbolo cercano.
Una Máquina de Turing tiene un alfabeto finito de símbolos, y un conjunto finito de estados, que
corresponden a los estados mentales de la computadora humana. El papel es una cinta lineal, que
tiene un extremo izquierdo y es potencialmente infinita hacia la derecha. La cinta esta marcada por
cuadrados, cada uno de estos contiene un símbolo; si un cuadrado no contiene símbolo, decimos que
contiene el símbolo blanco. Consideramos que la lectura y escritura en la cinta se realiza por medio de
un cabezal centrado en algún cuadrado de la cinta.
Un movimiento simple está determinado por el estado actual y el símbolo actual en la cinta, y consiste
de tres partes:
1. Cambiar de un estado actual a otro estado que puede ser distinto o no;
2. Reemplazar un símbolo en el cuadrado actual por otro símbolo que puede ser distinto al
original;
3. Dejar el cabezal en el cuadrado actual, o moverlo a un cuadrado que este a la derecha o a la
izquierda (este último movimiento solo es posible si el cabezal no se encuentra ya en el
extremo izquierdo de la cinta).
La cinta sirve como dispositivo de entrada (la entrada es una cadena finita de símbolos no blancos
que están en la cinta antes de comenzar el cómputo), la memoria disponible para el cómputo, y el
dispositivo de salida. La salida, si esta es relevante, es la cadena de símbolos que quedan en la cinta
al terminar el cómputo.
En general, una Máquina de Turing tiene dos estados de alto: uno para denotar aceptación y otro para
denotar rechazo, por ejemplo cuando ocurre algún tipo de error durante la ejecución.
Los conceptos anteriores permiten hacer la siguienteDefinición:Una Máquina de Turing es una 5-tupla
𝑇 = (𝑄, Σ, Γ, 𝑞! , 𝛿),
donde
𝑄 es un conjunto finito de estados. Los dos estados de alto ℎ! y ℎ! no son elementosde 𝑄.
Σ, el alfabeto de entrada, y Γ el alfabeto de la cinta, son ambos conjuntos finitos con Σ ⊆ Γ .
El símbolo blanco Δ no es un elemento de Γ.
𝑞! , el estado inicial, es un elemento de 𝑄.
𝛿 es la función de transición:
𝛿: 𝑄× Γ ∪ Δ ⟶ 𝑄 ∪ ℎ! , ℎ! × Γ ∪ {Δ} ×{𝐷, 𝐼, 𝐸}
Para un estado 𝑝 ∈ 𝑄, un estado 𝑞 ∈ 𝑄 ∪ {ℎ! , ℎ! }, dos símbolos 𝑋, 𝑌 ∈ Γ ∪ {∆}, y una dirección
𝑅 ∈ {𝐷, 𝐼, 𝐸}, la fórmula
𝛿 𝑝, 𝑋 = (𝑞, 𝑌, 𝑅)
3
indica que si 𝑇 está en el estado 𝑝 y el símbolo actual en el cabezal es 𝑋, la Máquina de Turing
reemplaza 𝑋 por 𝑌 en el cuadrado actual, cambia al estado 𝑞, y mueve el cabezal un cuadrado hacia
la derecha, la izquierda o lo deja estacionario, dependiendo de si 𝑅 es 𝐷, 𝐼 o 𝐸, respectivamente. Si el
estado 𝑞 es ℎ! o ℎ! , se dice que este movimiento provoca que 𝑇 se detenga. En este estado de alto, 𝑇
no puede moverse, ya que 𝛿 esta definida en (𝑞, 𝑌) solo si 𝑞 ∈ 𝑄. La transición
𝛿 𝑝, 𝑋 = (𝑞, 𝑌, 𝑅)
se representa por el diagrama
ALGORITM O DE ORDENAM IENTO “QUICKSORT”
Quicksort ha sido históricamente el algoritmo genérico de ordenamiento más rápido conocido en la
práctica. Es un algoritmo recursivo del tipo “divide y vencerás” y es fácil de implementar.La idea básica
es ordenar una lista siguiendo los pasos siguientes: se escoge un elemento arbitrario de la lista y se
forman tres grupos; el primer grupo, tiene los elementos menores a aquel que se escogió; el segundo,
los elementos iguales que el escogido; y el tercero, tiene los elementos más grandes. De forma
recursiva, se ordenan el primer y el tercer grupo; luego, se concatenan todos los grupos. Comúnmente
se evita crear el segundo grupo (de elementos iguales) cuando se codifica el algoritmo.
El algoritmo clásico de Quicksort, para ordenar un arreglo 𝑆, es como sigue
1.
2.
3.
4.
Si el número de elementos en 𝑆 es 0 o 1 entonces se ha terminado.
Escoger cualquier elemento 𝛾 en 𝑆 (𝛾 es llamado pivote).
Se parte 𝑆 − {𝛾} en dos grupos disjuntos: 𝑆! = {𝑥 ∈ 𝑆 − {𝛾}|𝑥 ≤ 𝛾} y 𝑆! = {𝑥 ∈ 𝑆 − {𝛾}|𝑥 ≥ 𝛾}
Se regresa quicksort(𝑆! ) seguido de 𝛾, seguido de quicksort(𝑆! ).
La ambigüedad dada en el paso 3, respecto a los elementos iguales que el pivote, se debe al diseño
del algoritmo. Lo más deseable para mejorar el desempeño es que la mitad de estos elementos vaya
a 𝑆! y la mitad a 𝑆! .
MÁQUINA DE TURING PA RA EL ALGORITMO QUICKSORT
Es posible diseñar una máquina de Turing para el algoritmo Quicksort; de hecho, pueden existir
diferentes máquinas para un mismo algoritmo. En esta sección, se describe una máquina de Turing
para ordenar una lista de𝑛 números enteros positivos {1,2,3, … , 𝑛} y que no tiene elementos repetidos.
Como se verá en la siguiente sección, con esta máquina es posible encontrar la complejidad del
tiempo del algoritmo analizando el número de movimientos simples realizados.
Notación
Con el fin de presentar un diagrama más limpio y claro de leer, no se utilizó completamente la
notación común para máquinas de Turing. Normalmente, cuando hay varios estados posibles después
de cambiar el estado actual se dibuja una línea para cada uno de esos posibles estados; como la lista
a ordenar puede tener 𝑛 elementos y cada uno de ellos representa un cambio de estado, no es
posible hacer un dibujo con todos los estados posibles. Lo anterior se observa en el diagrama de la
máquina de Turing propuesta donde los puntos suspensivos indican que hay estados intermedios.
Como se observa en la figura 1, la ejecución de la máquina comienza con la búsqueda del pivote. Se
inicia en el extremo izquierdo de la cinta, en el estado 𝑞! y leyendo el símbolo blanco. La función de
transición indica que el cabezal se mueve a la derecha para leer el primer número de la lista; la
entrada consiste del elemento blanco seguido de la lista y termina con el elemento blanco; como el
pivote será el último elemento de la lista, el cabezal debe recorrer toda la lista hasta encontrar el
elemento blanco y regresar un espacio para leer el pivote. En este trabajo, 𝑥 es un número cualquiera
y por lo tanto, la instrucción 𝑥/𝑥, 𝐷 indica que mientras se vea un número, este no se modifica y se
avanza a la derecha. En este punto, es importante aclarar que esta instrucción debe darse como una
4
lista en la notación original; por lo tanto, no es correcto interpretar que la computadora es capaz de
decidir cual elemento es un número y cual no. Se debe de pensar que en realidad la notación usada
es una forma de abreviar esa lista sin perder de vista que se deben de especificar todos los elementos
que aparecen en ella. Una vez que se ha leído el pivote, este se fija y el cabezal regresa al primer
número de la lista. Si el pivote es 𝑛 se ejecuta la máquina 𝑇! , la cual esta definida por la figura 1.
Figura 1.- Esquema del algoritmo QuickSort
Nuevamente, en la figura 2 aparecen notaciones que se deben interpretar cuidadosamente. En la
primera instrucción de la esquina superior izquierda debe darse una lista con todos los elementos
menores que el pivote. Y en la instrucción que está debajo de la anterior lo correcto es que haya una
flecha para cada elemento mayor que el pivote, sin embargo esto haría que el dibujo fuera muy
grande y difícil de interpretar; aquí 𝑚 es un elemento cualquiera mayor que el pivote pero queda fijo.
Figura 2.- Maquina de Turing para el algoritmo QuickSort
5
De las explicaciones anteriores, se puede ver que los modelos presentados son solo ilustrativos en el
funcionamiento de una máquina de Turing y que para utilizarse en un proceso real tendrían que
reescribirse dada una lista particular. Para 𝑇! los elementos 𝑚, 𝑛, 𝑝, 𝑥 y 𝑥 son elementos fijos pero son
cualquier número en la lista, es decir, para las instrucciones donde se presentan estos elementos
también debería aparecer una flecha para cada valor posible.
El funcionamiento de la máquina en un caso particular se esclarece con el siguiente ejemplo.
Ejem plo
Se utiliza el diagrama presentado para ordenar la lista {3,1,2}. Entonces la entrada debe ser ∆ 3 1|2|∆,
donde el color rojo indica la posición del cabezal. Y en el estado inicial, el cabezal pasa de leer el
primer símbolo blanco a leer el número 3. Mientras se lean los elementos 1, 2 o 3 el cabezal se mueve
a la derecha; cuando se llega al símbolo blanco se regresa a la izquierda y lee el pivote que en este
caso es el número 2. Ahora, con el pivote fijo, regresa al primer número de la lista y se ejecuta 𝑇! .
Dentro de la máquina 𝑇! las opciones son: leer un número menor que el pivote y moverse a la
derecha, ver el pivote y moverse a la izquierda; o leer un número 𝑚 mayor que el pivote, reescribir el
símbolo blanco y moverse a la derecha. En este caso, el cabezal lee el número 𝑚 = 3 y lo cambia por
el símbolo blanco para después avanzar a la derecha. La lista al momento es ∆ ∆ 1|2|∆.
Ahora, el cabezal debe buscar el pivote moviéndose a la derecha por lo que cada vez que se lee un
elemento de la lista de elementos diferentes que el pivote se sigue avanzando a la derecha. Aquí, el
cabezal pasa por el número 1, luego el número 2 y se regresa a la izquierda. El cabezal está leyendo
el número 𝑥 = 1, que es menor que el pivote, lo cambia por 𝑚 = 3 y se mueve a la izquierda. Se tiene
∆ ∆ 3|2|∆.
Mientras se lea un número se mueve a la izquierda buscando el símbolo blanco. Cuando se encuentra
el símbolo blanco se reemplaza por 𝑥 = 1 y se mueve a la derecha, de modo que ∆ 1 3|2|∆.
Se regresa al estado inicial de 𝑇! . En este momento se lee un número mayor que el pivote, 𝑚 = 3, por
lo que se reescribe el símbolo blanco moviéndose a la derecha. En seguida se observa el pivote y se
mueve a la izquierda, ∆ 1 ∆|2|∆. Como el cabezal está en el símbolo blanco, se mueve a la derecha y
se cambia el pivote por el número 3: ∆ 1 ∆|3|∆. Después de recorrer a la izquierda hasta encontrar el
símbolo blanco y luego un lugar a la derecha, se inicia 𝑇! dentro de 𝑇! .
Como el cabezal está leyendo el número 3 en el primer estado de 𝑇! , se mueve a la izquierda sin
modificar el símbolo actual. Se tiene ∆ 1 ∆|3|∆ y esto indica a la máquina que el cabezal queda
estacionario y se alcanza el estado ℎ! para 𝑇! .
Así, continua la ejecución de 𝑇! en el estado que se encuentra justo debajo del recuadro de 𝑇! . El
símbolo blanco indica que el cabezal se mueve hacia la izquierda para leer el número 1; este número,
que es menor que el pivote, se fija y se llama 𝑝. Se recorre a la izquierda hasta encontrar el símbolo
blanco; el primer elemento de la sublista a ordenar se encuentra haciendo un movimiento a la
derecha. Entonces se inicia 𝑇! y con la cinta ∆ 1 ∆|3|∆.
Nuevamente, se alcanza el estado ℎ! de 𝑇! después de dos movimientos. Ahora, el estado actual es
el que se encuentra a la derecha del recuadro de 𝑇! y se tiene ∆ 1 ∆|3|∆. Solo resta encontrar el
símbolo blanco mediante movimientos a la derecha. De este modo ∆ 1 ∆|3|∆ se cambia por ∆ 1 2|3|∆
y se detiene 𝑇! dejando una lista ordenada.
COM PLEJIDAD DEL TIEM PO DE UNA M ÁQUINA DE TURING
La complejidad el tiempo de un algoritmo es el número de operaciones que se realizan cuando la
entrada tiene un tamaño fijo 𝑛. La importancia de conocer la complejidad del tiempo es saber de
antemano si un algoritmo es adecuado para resolver un problema dado.
Si se tiene una máquina de Turing que ejecuta algún algoritmo es posible encontrar la complejidad del
tiempo de dicho algoritmo mediante el conteo de número de movimientos realizados por la máquina
cuando la entrada tiene tamaño fijo 𝑛.
Definición. Sea 𝑇 una máquina de Turing que eventualmente se detiene para cualquier entrada válida.
La complejidad del tiempo de 𝑇 es la función 𝜏 ! : ℕ ⟶ ℕ, donde 𝜏 ! (𝑛) se define al considerar, para
cada entrada de tamaño 𝑛, el número de movimientos que hace 𝑇 en esa entrada antes de parar, y
tomando 𝜏 ! (𝑛) como el máximo de esos números.
6
Com plejidad del tiem po para el algoritm o Quicksort
En el algoritmo Quicksort el peor caso, donde se hacen más operaciones, es cuando el pivote es el
menor elemento [2]. Considerando esto, se analiza el número de movimientos que realiza la máquina
propuesta cuando la entrada tiene tamaño 𝑛.
En la etapa inicial se recorre la lista desde el símbolo blanco a la izquierda hasta el símbolo blanco a
la derecha y de regreso; se hace un movimiento a la derecha antes de iniciar 𝑇! . Entonces la primera
etapa lleva 2 𝑛 + 1 + 1 = 2𝑛 + 3 movimientos.
Es importante notar que, en este caso, se requiere ejecutar las máquinas 𝑇! , 𝑇! , … , 𝑇! inevitablemente
y en ese orden. Para 𝑇! , se inicia con el cabezal en el primer elemento de la lista y se mueve hasta el
último, que es el pivote, en 𝑛 − 1 movimientos. Como no se encuentra ningún elemento más pequeño
que el pivote, el cabezal regresa hasta la posición en la que inició y que ahora está marcada con el
símbolo blanco; el cabezal realizó 𝑛 − 1 movimientos más. Ahora, se requiere la misma cantidad de
movimientos para ir hasta el pivote y cambiarlo por el número 2. Finalmente, antes de iniciar 𝑇! , se
realiza la misma cantidad de movimientos y uno más para dejar el cabezal en el primer elemento de la
nueva sublista. En resumen, hasta el momento 𝑇! lleva 4 𝑛 − 1 + 1 movimientos.
Notando que la siguiente sublista tiene 𝑛 − 1 elementos se deduce que, antes de iniciar 𝑇! , la máquina
𝑇! realiza 4 𝑛 − 2 + 1 movimientos.
Así, los movimientos realizados por las máquinas antes de terminar son
𝑇! : 4 𝑛 − 1 + 1
𝑇! : 4 𝑛 − 2 + 1
⋮
𝑇!!! : 4 1 + 1
𝑇! : 1
Una vez que 𝑇! termina, las demás máquinas requieren dos movimientos para terminar, es decir, se
suman 2(𝑛 − 1) movimientos a la cantidad ya calculada.
En total, se tiene que
!!!
𝑖 + 𝑛 − 1 + 2 𝑛 − 1 = 2𝑛! + 3𝑛
𝜏 ! 𝑛 = 2𝑛 + 3 + 4
!!!
Por lo tanto, la complejidad del tiempo para el algoritmo Quicksort es de orden cuadrático. Cabe
mencionar que el análisis presentado por Weiss [2] también reporta un orden cuadrático en el peor
caso.
EL TEST DE TURING
¿Pueden las máquinas pensar? Esta controversial pregunta surgió en la mente del matemático inglés
Alan Turing. Al menos desde 1941, Turing ya se cuestionaba acerca de la inteligencia de las
máquinas [3]. Se sabe que durante el tiempo de la Segunda Guerra mundial, Turing circuló un artículo
sobre la inteligencia de las máquinas entre sus colegas en Betchley Park; sin duda este artículo fue el
primero en tratar estos temas.
Aún no se conoce una interpretación correcta de las ideas de Turing. Mientras que algunos opinan
que Turing da una definición de lo que es inteligencia, otros opinan que, sin necesidad de definir la
integencia, Turing quería saber si era posible que una máquina emulara los procesos del cerebro
humano.
El siguiente es un extracto de una transcripción de una emisión radiofónica efectuada en Enero de
1952; en ella Alan Turing responde a la pregunta “¿se puede decir propiamente que las máquinas
piensan?”:
7
No quiero dar una definición de pensar, y si tuviera que hacerlo probablemente no podría decir
nada más que es un tipo de zumbido que entró en mi cabeza. Pero realmente no veo la
necesidad de acordar una definición. Lo importante es trazar una línea que divida las
propiedades de un cerebro, o de un hombre, que queremos discutir y aquellas que no. Me
gustaría sugerir un tipo de prueba que uno podría aplicarle a una máquina. Podría decirse que
es una prueba para ver si una máquina piensa, pero es mejor evitar esa cuestión, y decir que
las máquinas que aprueben son, digamos, máquinas de “Grado A”. La idea de esta prueba es
que una máquina tiene que intentar y pretender que es un hombre, respondiendo las
preguntas que le son dadas, y aprobará solo si la pretensión es razonablemente convincente.
Una considerable proporción de un jurado, que no deben ser expertos en máquinas, deben
ser convencidos por la pretensión. No se le permite al jurado ver la máquina –eso haría la
prueba muy fácil. Así que la máquina esta apartada en una habitación lejana y el jurado puede
hacerle preguntas, las cuales se le transmiten a la máquina y ella manda una respuesta
mecanografiada. Las preguntas pueden tratar cualquier tema. Y las preguntas no necesitan
realmente ser preguntas. Por ejemplo “Yo afirmo que tu eres una máquina”. De la misma
forma, a la máquina se le permite todo tipo de trucos para aparentar ser humano, como
esperar un poco antes de dar una respuesta, o cometer errores de ortografía, pero no puede
hacer manchas en el papel. Sería mejor suponer que cada jurado tiene que juzgar varias
veces, y algunas de esas veces realmente están tratando con un hombre y no con una
máquina. Esto evitaría que dijeran “debe ser una máquina” cada vez sin la consideración
apropiada.
Bueno, esta es mi prueba. Obviamente no estoy diciendo que en el presente las máquinas
puedan pasar la prueba, o que no podrían. Mi sugerencia es simplemente que este asunto es
lo que deberíamos discutir. No es lo mismo que preguntarse “¿Pueden las máquinas
pensar?”, pero es bastante cercano para nuestro propósito, y tiene las mismas dificultades.
Aunque Turing comprende que las máquinas de su tiempo están lejos de poder imitar a un humano,
se muestra optimista al predecir que para el fin de siglo sería posible programar una máquina que
responda preguntas de tal forma que sea en extremo difícil adivinar si se trata de un hombre o una
máquina.
La motivación para esta primera versión de la prueba de Turing, llamada el Juego de la Imitación, se
explica a continuación. El juego se lleva a cabo entre un hombre (A), una mujer (B) y el interrogador
(C) cuyo sexo es irrelevante. El interrogador permanece en una habitación separada de A y de B. El
objetivo del interrogador es determinar cuál de los otros dos jugadores es la mujer, mientras que el
objetivo del hombre y la mujer es convencer al interrogador de que él/ella es la mujer.
Turing afirmó que, en el esquema del Juego de la Imitación, la pregunta “¿pueden las máquinas
pensar?” puede remplazarse por la pregunta “¿Qué pasará cuando una máquina toma la parte del
jugador A en este juego? ¿El interrogador cometerá la misma cantidad de errores que cometía cuando
jugaba con un hombre y una mujer?”. Así, la prueba de Turing trata de evaluar la habilidad de una
máquina para imitar a un ser humano; en consecuencia, se genera una nueva versión del juego en
donde (A) es una máquina, (B) un humano, y (C) es el interrogador que trata de determinar cuál de
estas entidades con las que se comunica es el humano.
A lo largo de los años, se han presentado muchas objeciones contra el test de Turing; quizás las
malas interpretaciones abundan porque no existen todas las especificaciones necesarias sobre la
prueba. Turing nunca habló sobre un tiempo específico para la duración de la prueba. Ni siquiera
acerca del número de jueces o el número mínimo de identificaciones correctas necesarias para
aprobar.
Así mismo, al paso del tiempo se han diseñado máquinas con el simple propósito de aprobar el Test
de Turing. En la versión moderna de la prueba se han registrado máquinas que logran engañar a una
cierta cantidad de jueces pero no la suficiente. Fue hasta el año 2014 que una máquina obtuvo el
“Grado A” al convencer a todos los jueces de que era un humano.
Consideremos el algoritmo de Quicksort y la máquina de Turing que se ha elaborado para dicho
algoritmo. Supongamos que en el esquema de la prueba de Turing tomamos el papel de interrogador;
8
asumamos que podemos entregar una lista de elementos a ordenar a una entidad que se encuentra
en otra habitación y en base a su respuesta debemos determinar si se trata de una máquina o un
humano. ¿Cómo lograríamos hacer una identificación correcta? Por un lado, sabemos que si la lista
es pequeña el humano no necesita hacer todos los movimientos que haría la máquina (que no puede
funcionar correctamente si no ejecuta todos los pasos) y probablemente sea más veloz al responder.
Pero por otro lado, para una lista suficientemente grande, tanto el humano como la máquina deben
seguir el algoritmo para ser competentes. Esta discusión tiene el propósito de observar que cuando se
utiliza la prueba de Turing para ver si una máquina es capaz de imitar a un humano en un problema
específico (y no parecer humano en todo sentido) se presentan nuevas interrogantes y probablemente
sea necesario hacer una versión muy particular de la prueba.
Otro problema interesante para aplicar el Test de Turing es la solución del cubo Rubik. Actualmente
existe una variedad de robots capaces de armar el cubo Rubik en segundos; de igual forma, se tiene
registro de humanos que resuelven el cubo Rubik en menos de 6 segundos. Si se tuviera que hacer el
Test de Turing en este caso probablemente el tiempo de solución no sería un buen punto de
referencia para tomar una decisión. En este momento, lo que interesa remarcar es el hecho de que,
como lo predijo Turing, cada vez es más complejo diferenciar entre las acciones ejecutadas por una
máquina y las acciones de un humano. La capacidad de las máquinas ha avanzado hasta un punto en
el que para algunas labores en específico es imposible distinguir la ejecución de un hombre y la de
una máquina. Planteando la interrogante de “¿cómo saber si este cubo Rubik fue armado por un robot
o una persona?” se presenta las siguientes imágenes donde el cubo es armado por un hombre o una
máquina.
CONCLUSIONES
Aunque el esquema de la máquina de Turing, que se elaboró para el algoritmo Quicksort, tendría que
rescribirse para un problema en específico se logró proponer una forma en la que una “computadora
humana” podría resolver el problema de ordenar una lista de números.
De cualquier modo, se alcanzó el objetivo principal que era obtener la complejidad del tiempo para el
algoritmo de Quicksort. Cabe mencionar que dado un problema, se pueden construir diversas
máquinas de Turing para resolver el mismo problema. En este sentido, no se afirma que la máquina
de Turing que se elaboró en este trabajo sea la más eficiente o la menos eficiente; tan solo se señala
que en este caso coincide la complejidad obtenida con los resultados analíticos que existen en la
bibliografía.
Por último, las menciones a la Prueba de Turing son una forma de poner en perspectiva el esfuerzo
que se hace por minimizar la diferencia entre hombre y máquina y algunos de los avances que se han
tenido en este campo.
BIBLIOGRAPHY
[1] MARTIN, John C. “Introduction to languages and the theory of computation”, McGraw Hill (2010).
[2] WEISS, M. A. “Data structures and algorithm analysis”, Pearson (2014).
[3] COPELAND, B. J. “The Turing Test: The elusive standard of artificial intelligence”, Springer (2003).