Recordemos que los retóricos sólo hacen preguntas cuya respuesta correcta conoce (o, con más precisión, sólo hacen preguntas de las que tiene la suficiente información como para determinar cuál es la respuesta correcta). Un sofista sólo hace preguntas de las que no tiene la suficiente información como para determinar cuál es la respuesta correcta.
Tanto los retóricos como los sofistas se dividen a su vez en veraces y mentirosos. Un veraz sólo hace afirmaciones verdaderas (con más precisión, sólo hace afirmaciones de las que posee la suficiente información como para saber que son verdaderas). Un mentiroso sólo hace afirmaciones de las que posee la suficiente información como para saber que son falsas. Nadie hace afirmaciones de las que carezca de información suficiente como para
determinar si son verdaderas o falsas
Una institución muy importante en el planeta de los retóricos y los sofistas son los Clubes. Un Club es un lugar en el que los nativos se reúnen para conversar y realizar otras actividades sociales. En todo Club, y ésta es su característica distintiva, hay dos tableros. Un tablero indica cuántos sofistas y cuántos retóricos hay presentes y el otro indica cuántos veraces y cuántos mentirosos hay. Por ejemplo, en cierto momento uno de los tableros puede estar indicando "8 retóricos y 5 sofistas" y el otro "10 veraces y 3 mentirosos" (los tableros no indican, por ejemplo, cuántos de los retóricos son veraces y cuántos son mentirosos).
No está claro cómo obtienen los tableros su información, aunque se supone que el mecanismo involucra cierta capacidad telepática. Lo cierto es que la información que brindan es siempre correcta y está todo el tiempo a la vista de los presentes.
Cierta vez había presentes en un Club tres nativos, llamados A, B y C. Ninguno de ellos conocía previamente a los otros. Aparte del hecho de que todos son nativos del planeta, la única información adicional que poseen inicialmente es la que brindan los tableros.
A le pregunta a B: ¿Eres retórico?
B le pregunta a C: ¿Eres retórico?
C le pregunta a A: ¿Eres veraz?
B le dice a C: Eres sofista.
A le dice a C: Eres mentiroso.
B le dice a A: Eres mentiroso.
¿A cuál de los cuatro grupos (sofistas veraces, sofistas mentirosos, retóricos veraces o retóricos mentirosos) pertenece cada uno?
7.1.06
Gödel y Turing (Parte 5)
(A la parte 4 - A la parte 6)
Más sobre la tesis de Turing
“El trabajo de Turing en la construcción de tablas de comportamiento parece inmerso en la cuestión de la programación de computadoras, tanto más cuanto Turing utilizó una notación abreviada equivalente a la definición de subrutinas. Aunque no puede decirse que la idea de la programación tenga su origen en el trabajo de Turing, la verdad es que en éste la idea es formalizada de tal modo que es difícil creer que las computadoras todavía no existieran. Sin embargo, un asunto tiene que enfatizarse: en su trabajo Turing no estaba considerando las máquinas de computación (que llegarían sólo diez años más tarde), lo que Turing hacia era modelar la acción de la mente humana.”
(HODGES, Andrew – Turing – Editorial Norma, Bogotá, 1998. )
Un algoritmo es, informalmente hablando, un procedimiento mecánico (o una receta) para resolver un problema determinado. Específicamente serán de nuestro interés los problemas matemáticos que involucran números enteros positivos.
Normalmente un algoritmo se expresa como una serie de instrucciones que deben seguirse paso a paso al pie de la letra (de la misma manera en que una computadora ejecuta los pasos de un programa). Supongamos, por ejemplo, que nuestro problema consiste en calcular la parte entera de la raíz cuadrada de un número dado. Como primer intento podríamos plantear sencillamente el “algoritmo” siguiente:
Propuesta I:
Entrada: n.
Paso 1: Calcule la parte entera de la raíz cuadrada de n y llámela k.
Salida: k.
Sin embargo, como es fácil imaginar, las instrucciones que acabamos de escribir no constituyen genuinamente un algoritmo. La instrucción principal dice sencillamente “resuelva el problema”, sin indicarnos realmente el modo de hacerlo.
Para que un conjunto de instrucciones constituya verdaderamente un algoritmo deberíamos estar seguros de que cada uno de sus pasos puede ser ejecutado mecánicamente, mientras que en la Propuesta I no tenemos ninguna garantía de que el Paso 1 cumpla esa condición. El siguiente conjunto de instrucciones nos da una respuesta mejor para nuestro problema:
Propuesta II:
Entrada: n.
Paso 1: Asigne a la variable k el valor 1.
Paso 2: Eleve k al cuadrado.
Paso 3: Si el cuadrado de k es menor o igual que n, sume 1 al valor de k y vaya al paso 2.
Paso 4: Si el cuadrado de k es mayor que n, vaya al paso 5.
Paso 5: Reste 1 al valor de k.
Salida: k.
Por ejemplo, si n = 22, las instrucciones nos llevan a calcular los cuadrados de 1, 2, 3,... Estos cálculos llegarán hasta el cuadrado de 5, que es el primer número que es excede a 22. La salida es k = 4, la respuesta correcta del problema.
La Propuesta II es un refinamiento de la Propuesta I, pues está construida subdividiendo cada instrucción de ésta en pasos más sencillos. Pero ¿es cierto que cada paso del segundo algoritmo puede realizarse mecánicamente? Analicemos: cada instrucción de la Propuesta II nos pide, o bien elevar un número al cuadrado, o bien sumarle o restarle una unidad, o bien comparar dos números enteros. Nuestra familiaridad con calculadoras y computadoras nos indica que, en efecto, todas estas operaciones pueden efectuarse mecánicamente.
Pero, si no contásemos con esa familiaridad ¿cómo podríamos tener la absoluta certeza de que existe un procedimiento mecánico para, por ejemplo, elevar un número al cuadrado? El modo de lograr esta certeza sería refinar una y otra vez la Propuesta II hasta lograr un conjunto de instrucciones tan sencillas que no quepa ninguna duda de que pueden ser ejecutadas mecánicamente. La idea central de la Tesis de Turing es que el último refinamiento de cualquier algoritmo será, a la larga, una máquina de Turing (o máquina T, para abreviar).
En el artículo donde presenta por primera vez su tesis (1), Turing ofrece el siguiente argumento como justificación de la misma (2):
Turing analiza los pasos que sigue una persona al realizar un cálculo matemático. Dice que en esa tarea, los humanos revisamos cifra por cifra los números involucrados en el cálculo y que en cada paso elemental (o irreducible) del mismo escribimos o borramos un símbolo. Finalmente argumenta que nuestro modo de proceder está siempre regido por nuestro “estado mental” en cada instante (análogo al “estado interno” de una máquina T). Por lo tanto, dice Turing, los pasos elementales de cualquier cómputo son equivalentes a los que realiza una máquina T.
Es interesante observar que en su razonamiento Turing analiza los pasos que sigue una persona (no un artefacto) al realizar un cálculo. Por lo tanto, al definir su máquina, Turing estaba intentando dar un modelo matemático del funcionamiento del cerebro humano. En otras palabras, al momento de escribir su artículo, Turing consideraba que el cerebro humano funciona esencialmente igual que computadora. La complejidad del cerebro es, desde luego, mucho mayor que el de cualquier computadora actual, pero la diferencia entre ambos residiría sólo en una cuestión de complejidad, no en una cuestión de naturaleza esencial.
En escritos posteriores Turing modificó esta primera convicción y pasó a creer que el cerebro humano tiene en realidad capacidades que son imposibles de alcanzar por una computadora, ni siquiera en teoría (3). Concretamente, en esta segunda etapa de su pensamiento, Turing creía que los presentimientos o la intuición marcaban una diferencia real entre mente humana y la computadora mecánica.
¿Es el cerebro humano una computadora (extraordinariamente compleja, pero computadora al fin) o, por el contrario, existe una diferencia esencial entre “computadora” y “cerebro”? No existe por el momento (y tal vez nunca exista) un acuerdo unánime acerca del cuál es la respuesta a esta pregunta. En la actualidad, sólo por citar algunos ejemplos, el físico-matemático Roger Penrose es defensor de la convicción según la cual el cerebro es esencialmente superior a una computadora y que no pueden equipararse, ni siquiera en teoría. Por el contrario, el filósofo Daniel Dennett y el matemático Douglas Hofstadter sostienen la idea opuesta, es decir, que el cerebro es fundamentalmente una computadora muy compleja y que es posible, al menos en teoría, que en el futuro lejano las computadoras artificiales lleguen a equipararse al cerebro humano en sus capacidades. El autor de estas notas debe decir que simpatiza con esta última postura. [...]
Notas:
(1) On computable numbers with an aplication to the Entscheidungsproblem, publicado en el Proceedings of London Mathematical Society, vol. 42 (1937), pp. 230 – 265.
(2) Decíamos en la nota anterior que la Tesis de Turing no puede ser demostrada matemáticamente. Por lo tanto, cualquier argumento que intente justificarla debe ser necesariamente de carácter extra-matemático.
(3) La pregunta de si las máquinas pueden pensar preocupó a Turing durante décadas. En 1950, por ejemplo, presentó la idea de un test (hoy conocido como Test de Turing) que permitiría en teoría determinar si una computadora piensa o no. La idea del test es que si ante preguntas de carácter general una computadora puede dar respuestas que no se distingan de las que daría una persona, entonces puede decirse que la máquina efectivamente piensa. Desde su misma formulación el test ha sido motivo de mucha controversia.
(A la parte 4 - A la parte 6)
Más sobre la tesis de Turing
“El trabajo de Turing en la construcción de tablas de comportamiento parece inmerso en la cuestión de la programación de computadoras, tanto más cuanto Turing utilizó una notación abreviada equivalente a la definición de subrutinas. Aunque no puede decirse que la idea de la programación tenga su origen en el trabajo de Turing, la verdad es que en éste la idea es formalizada de tal modo que es difícil creer que las computadoras todavía no existieran. Sin embargo, un asunto tiene que enfatizarse: en su trabajo Turing no estaba considerando las máquinas de computación (que llegarían sólo diez años más tarde), lo que Turing hacia era modelar la acción de la mente humana.”
(HODGES, Andrew – Turing – Editorial Norma, Bogotá, 1998. )
Un algoritmo es, informalmente hablando, un procedimiento mecánico (o una receta) para resolver un problema determinado. Específicamente serán de nuestro interés los problemas matemáticos que involucran números enteros positivos.
Normalmente un algoritmo se expresa como una serie de instrucciones que deben seguirse paso a paso al pie de la letra (de la misma manera en que una computadora ejecuta los pasos de un programa). Supongamos, por ejemplo, que nuestro problema consiste en calcular la parte entera de la raíz cuadrada de un número dado. Como primer intento podríamos plantear sencillamente el “algoritmo” siguiente:
Propuesta I:
Entrada: n.
Paso 1: Calcule la parte entera de la raíz cuadrada de n y llámela k.
Salida: k.
Sin embargo, como es fácil imaginar, las instrucciones que acabamos de escribir no constituyen genuinamente un algoritmo. La instrucción principal dice sencillamente “resuelva el problema”, sin indicarnos realmente el modo de hacerlo.
Para que un conjunto de instrucciones constituya verdaderamente un algoritmo deberíamos estar seguros de que cada uno de sus pasos puede ser ejecutado mecánicamente, mientras que en la Propuesta I no tenemos ninguna garantía de que el Paso 1 cumpla esa condición. El siguiente conjunto de instrucciones nos da una respuesta mejor para nuestro problema:
Propuesta II:
Entrada: n.
Paso 1: Asigne a la variable k el valor 1.
Paso 2: Eleve k al cuadrado.
Paso 3: Si el cuadrado de k es menor o igual que n, sume 1 al valor de k y vaya al paso 2.
Paso 4: Si el cuadrado de k es mayor que n, vaya al paso 5.
Paso 5: Reste 1 al valor de k.
Salida: k.
Por ejemplo, si n = 22, las instrucciones nos llevan a calcular los cuadrados de 1, 2, 3,... Estos cálculos llegarán hasta el cuadrado de 5, que es el primer número que es excede a 22. La salida es k = 4, la respuesta correcta del problema.
La Propuesta II es un refinamiento de la Propuesta I, pues está construida subdividiendo cada instrucción de ésta en pasos más sencillos. Pero ¿es cierto que cada paso del segundo algoritmo puede realizarse mecánicamente? Analicemos: cada instrucción de la Propuesta II nos pide, o bien elevar un número al cuadrado, o bien sumarle o restarle una unidad, o bien comparar dos números enteros. Nuestra familiaridad con calculadoras y computadoras nos indica que, en efecto, todas estas operaciones pueden efectuarse mecánicamente.
Pero, si no contásemos con esa familiaridad ¿cómo podríamos tener la absoluta certeza de que existe un procedimiento mecánico para, por ejemplo, elevar un número al cuadrado? El modo de lograr esta certeza sería refinar una y otra vez la Propuesta II hasta lograr un conjunto de instrucciones tan sencillas que no quepa ninguna duda de que pueden ser ejecutadas mecánicamente. La idea central de la Tesis de Turing es que el último refinamiento de cualquier algoritmo será, a la larga, una máquina de Turing (o máquina T, para abreviar).
En el artículo donde presenta por primera vez su tesis (1), Turing ofrece el siguiente argumento como justificación de la misma (2):
Turing analiza los pasos que sigue una persona al realizar un cálculo matemático. Dice que en esa tarea, los humanos revisamos cifra por cifra los números involucrados en el cálculo y que en cada paso elemental (o irreducible) del mismo escribimos o borramos un símbolo. Finalmente argumenta que nuestro modo de proceder está siempre regido por nuestro “estado mental” en cada instante (análogo al “estado interno” de una máquina T). Por lo tanto, dice Turing, los pasos elementales de cualquier cómputo son equivalentes a los que realiza una máquina T.
Es interesante observar que en su razonamiento Turing analiza los pasos que sigue una persona (no un artefacto) al realizar un cálculo. Por lo tanto, al definir su máquina, Turing estaba intentando dar un modelo matemático del funcionamiento del cerebro humano. En otras palabras, al momento de escribir su artículo, Turing consideraba que el cerebro humano funciona esencialmente igual que computadora. La complejidad del cerebro es, desde luego, mucho mayor que el de cualquier computadora actual, pero la diferencia entre ambos residiría sólo en una cuestión de complejidad, no en una cuestión de naturaleza esencial.
En escritos posteriores Turing modificó esta primera convicción y pasó a creer que el cerebro humano tiene en realidad capacidades que son imposibles de alcanzar por una computadora, ni siquiera en teoría (3). Concretamente, en esta segunda etapa de su pensamiento, Turing creía que los presentimientos o la intuición marcaban una diferencia real entre mente humana y la computadora mecánica.
¿Es el cerebro humano una computadora (extraordinariamente compleja, pero computadora al fin) o, por el contrario, existe una diferencia esencial entre “computadora” y “cerebro”? No existe por el momento (y tal vez nunca exista) un acuerdo unánime acerca del cuál es la respuesta a esta pregunta. En la actualidad, sólo por citar algunos ejemplos, el físico-matemático Roger Penrose es defensor de la convicción según la cual el cerebro es esencialmente superior a una computadora y que no pueden equipararse, ni siquiera en teoría. Por el contrario, el filósofo Daniel Dennett y el matemático Douglas Hofstadter sostienen la idea opuesta, es decir, que el cerebro es fundamentalmente una computadora muy compleja y que es posible, al menos en teoría, que en el futuro lejano las computadoras artificiales lleguen a equipararse al cerebro humano en sus capacidades. El autor de estas notas debe decir que simpatiza con esta última postura. [...]
Notas:
(1) On computable numbers with an aplication to the Entscheidungsproblem, publicado en el Proceedings of London Mathematical Society, vol. 42 (1937), pp. 230 – 265.
(2) Decíamos en la nota anterior que la Tesis de Turing no puede ser demostrada matemáticamente. Por lo tanto, cualquier argumento que intente justificarla debe ser necesariamente de carácter extra-matemático.
(3) La pregunta de si las máquinas pueden pensar preocupó a Turing durante décadas. En 1950, por ejemplo, presentó la idea de un test (hoy conocido como Test de Turing) que permitiría en teoría determinar si una computadora piensa o no. La idea del test es que si ante preguntas de carácter general una computadora puede dar respuestas que no se distingan de las que daría una persona, entonces puede decirse que la máquina efectivamente piensa. Desde su misma formulación el test ha sido motivo de mucha controversia.
(A la parte 4 - A la parte 6)
5.1.06
Gödel y Turing (Parte 4)
(A la parte 3 - A la parte 5)
La Tesis de Turing
Tomemos la máquina de Turing que hemos descripto en la parte 3 y apliquemos las instrucciones de su programa a la entrada formada por cinco símbolos # consecutivos. Al cabo de unos pocos pasos llegaremos al estado q0 (que marca el final del cómputo), veremos entonces que la salida de la máquina correspondiente a esa entrada está formada por cuatro símbolos # consecutivos. Por otra parte, si tomamos como entrada un único símbolo #, entonces la máquina nunca llegará al estado q0. Es decir, la máquina se colgará entrando en un estado de cómputo perpetuo.
Definición: Dada una máquina de Turing, diremos que una entrada es válida para ella si al cabo de una cantidad finita de pasos la máquina llega al estado q0 y la salida así obtenida está formada por cierto número de símbolos # consecutivos.
Por ejemplo, para la máquina descrita en la parte 3, la entrada ##### (que indicaremos como #5) es válida, mientras que la entrada # (o #1) no lo es.
Démosle un significado concreto a estas entradas y salidas. Convengamos en que una sucesión de n símbolos # consecutivos (es decir #n) representa el número n. Otras entradas no tendrán significado para nosotros. Entonces, en el ejemplo anterior podemos interpretar que la entrada es el número 5 y que la salida es el 4.
Interpretando de esta forma las entradas y las salidas, es fácil comprobar que si la entrada de la máquina descripta en la parte 3 es un número n > 1 entonces la salida será el número n – 1; para n = 1, ya dijimos, la máquina no da salida alguna. En otras palabras, la máquina de la parte 3 representa un algoritmo que calcula la función f(n) = n – 1, cuyo dominio (1) es el conjunto de los enteros mayores que 1. (2)
La Tesis de Turing dice que, codificadas adecuadamente las entradas y las salidas, todo algoritmo puede representarse mediante una máquina de Turing (3). Es decir, para todo algoritmo A existe una máquina de Turing T tal que para cada entrada para la que A dé una salida, T también da una salida y además exactamente la misma. Si A no da una salida, T tampoco.
Observemos que no es posible demostrar esta tesis, ya que para obtener una tal demostración deberíamos tener una definición previa del concepto de algoritmo, pero justamente esta definición es lo que se pretende dar con el concepto de máquina de Turing. Sí podemos decir a favor de la tesis que todas las demás definiciones que se han dado del concepto de algoritmo (incluida la concepción de Alonzo Church) han resultado ser equivalentes a la dada por Turing, es decir los procesos representados por cualquiera de esas otras definiciones son exactamente aquellos que pueden representarse mediante máquinas de Turing.
Aceptada la Tesis de Turing como un axioma, concluimos que si pudiéramos demostrar que cierto problema matemático es irresoluble por cualquier máquina de Turing, entonces habremos demostrado que es irresoluble por cualquier programa informático, presente o futuro.
Notas:
(1) El dominio de f(n) es el conjunto de los valores de n para los cuáles el cálculo tiene sentido (es decir, para los cuales el cálculo puede realizarse y da como resultado un número entero mayor o igual que 1).
(2) Sólo trabajaremos con algoritmos cuyas entradas y salidas sean números, o conjuntos finitos de números enteros mayores o iguales que 1. Para representar conjuntos (o n-uplas) se pueden anotar en la cinta de la máquina varias series de símbolos # separadas por casillas vacías.
(3) Es posible definir máquinas que trabajen con más símbolos, que utilicen más cintas ó cuyos cursores puedan moverse dos ó más casillas a la vez. Sin embargo, tales cambios no representan ninguna diferencia esencial. Todo cálculo que pueda ser hecho por estas máquinas con más recursos puede también ser realizado, aunque en general más lentamente, por alguna máquina con una única cinta como la que hemos descrito en la parte 3.
(A la parte 3 - A la parte 5)
La Tesis de Turing
Tomemos la máquina de Turing que hemos descripto en la parte 3 y apliquemos las instrucciones de su programa a la entrada formada por cinco símbolos # consecutivos. Al cabo de unos pocos pasos llegaremos al estado q0 (que marca el final del cómputo), veremos entonces que la salida de la máquina correspondiente a esa entrada está formada por cuatro símbolos # consecutivos. Por otra parte, si tomamos como entrada un único símbolo #, entonces la máquina nunca llegará al estado q0. Es decir, la máquina se colgará entrando en un estado de cómputo perpetuo.
Definición: Dada una máquina de Turing, diremos que una entrada es válida para ella si al cabo de una cantidad finita de pasos la máquina llega al estado q0 y la salida así obtenida está formada por cierto número de símbolos # consecutivos.
Por ejemplo, para la máquina descrita en la parte 3, la entrada ##### (que indicaremos como #5) es válida, mientras que la entrada # (o #1) no lo es.
Démosle un significado concreto a estas entradas y salidas. Convengamos en que una sucesión de n símbolos # consecutivos (es decir #n) representa el número n. Otras entradas no tendrán significado para nosotros. Entonces, en el ejemplo anterior podemos interpretar que la entrada es el número 5 y que la salida es el 4.
Interpretando de esta forma las entradas y las salidas, es fácil comprobar que si la entrada de la máquina descripta en la parte 3 es un número n > 1 entonces la salida será el número n – 1; para n = 1, ya dijimos, la máquina no da salida alguna. En otras palabras, la máquina de la parte 3 representa un algoritmo que calcula la función f(n) = n – 1, cuyo dominio (1) es el conjunto de los enteros mayores que 1. (2)
La Tesis de Turing dice que, codificadas adecuadamente las entradas y las salidas, todo algoritmo puede representarse mediante una máquina de Turing (3). Es decir, para todo algoritmo A existe una máquina de Turing T tal que para cada entrada para la que A dé una salida, T también da una salida y además exactamente la misma. Si A no da una salida, T tampoco.
Observemos que no es posible demostrar esta tesis, ya que para obtener una tal demostración deberíamos tener una definición previa del concepto de algoritmo, pero justamente esta definición es lo que se pretende dar con el concepto de máquina de Turing. Sí podemos decir a favor de la tesis que todas las demás definiciones que se han dado del concepto de algoritmo (incluida la concepción de Alonzo Church) han resultado ser equivalentes a la dada por Turing, es decir los procesos representados por cualquiera de esas otras definiciones son exactamente aquellos que pueden representarse mediante máquinas de Turing.
Aceptada la Tesis de Turing como un axioma, concluimos que si pudiéramos demostrar que cierto problema matemático es irresoluble por cualquier máquina de Turing, entonces habremos demostrado que es irresoluble por cualquier programa informático, presente o futuro.
Notas:
(1) El dominio de f(n) es el conjunto de los valores de n para los cuáles el cálculo tiene sentido (es decir, para los cuales el cálculo puede realizarse y da como resultado un número entero mayor o igual que 1).
(2) Sólo trabajaremos con algoritmos cuyas entradas y salidas sean números, o conjuntos finitos de números enteros mayores o iguales que 1. Para representar conjuntos (o n-uplas) se pueden anotar en la cinta de la máquina varias series de símbolos # separadas por casillas vacías.
(3) Es posible definir máquinas que trabajen con más símbolos, que utilicen más cintas ó cuyos cursores puedan moverse dos ó más casillas a la vez. Sin embargo, tales cambios no representan ninguna diferencia esencial. Todo cálculo que pueda ser hecho por estas máquinas con más recursos puede también ser realizado, aunque en general más lentamente, por alguna máquina con una única cinta como la que hemos descrito en la parte 3.
(A la parte 3 - A la parte 5)
2.1.06
Gödel y Turing (Parte 3)
(A la parte 2 - A la parte 4)
La máquina de Turing
En 1936, independientemente y con pocos meses de diferencia, se crearon dos definiciones matemáticas del concepto de algoritmo. La primera fue concebida por el lógico norteamericano Alonzo Church y la segunda, por el lógico inglés Alan Turing (1). Aunque ambas concepciones son equivalentes, la idea de Turing resulta intuitivamente más clara, por lo que en toda la exposición sólo nos referiremos a ella (2).
Para Turing el concepto de algoritmo puede asimilarse al de una máquina abstracta, una computadora teórica hoy conocida como máquina de Turing. Esta máquina consta en primer lugar de una cinta, en la cual se anotará la entrada y la salida del algoritmo y que servirá a la vez de memoria de trabajo del dispositivo.
La cinta está dividida en celdas o casillas, cada una de las cuales puede contener un único símbolo (que indicaremos como #) o bien puede estar vacía. La cinta, además, es potencialmente infinita, esto significa que tanto hacia la derecha como hacia la izquierda podemos agregar todas las celdas que sean necesarias. La cantidad inicial de símbolos # es siempre finita.
La máquina consta también de un cursor que puede ver el contenido de una casilla a la vez. Cuando la casilla observada está vacía el cursor puede, si sus instrucciones así lo indican, anotar en ella un símbolo #. Si la casilla tiene ya un símbolo #, el cursor puede borrarlo, dejando la casilla vacía. Por otra parte, el cursor puede moverse a razón de una casilla por vez, tanto hacia la derecha como hacia la izquierda. Debido a la infinitud de la cinta, el cursor nunca encontrará límites para su movimiento.
Las acciones del cursor están dirigidas por un programa o conjunto de instrucciones. En un momento dado, la máquina puede estar en uno de una cantidad finita de estados posibles (que indicaremos como q0, q1, q2,..., qn). El programa le indica a la máquina qué debe hacer dependiendo del estado en que ésta se encuentre y de qué contenido tenga la casilla que el cursor está viendo.
Consideremos por ejemplo el siguiente programa:
q1 + # -> 0 D q2
q1 + 0 -> 0 I q1
q2 + # -> # S q0
q2 + 0 -> 0 D q2
A la izquierda aparecen todos los estados en que la máquina puede hallarse, excepto q0, y el contenido de la casilla que observa el cursor (0 es vacío). A la derecha se indica qué debe hacer el cursor en cada circunstancia. La primera instrucción (la máquina está en el estado q1 y el cursor está viendo un #) dice que el cursor debe borrar el símbolo de la casilla (ésta queda vacía) y luego debe moverse un lugar a la derecha, luego la máquina finalmente pasa al estado q2. La segunda instrucción dice que (si la máquina está en el estado q1 y el cursor está viendo una casilla vacía) entonces la celda debe quedar vacía, el cursor se mueve un lugar a la izquierda y la máquina queda en el estado q1. La S de la tercera instrucción significa que el cursor queda en su posición inicial. El estado q0 es el estado final, cuando la máquina pasa a él se detiene de inmediato. Es decir, el estado q0 indica que el cómputo ha terminado.
Convenimos en que inicialmente cualquier máquina se encontrará en el estado q1 y que el cursor observará el primer símbolo # de la izquierda.
Notas:
(1) Turing había nacido en 1912, por lo que, como Gödel, tenía menos de 25 años al publicar su trabajo fundamental. Tristemente, la vida de ambos fue difícil y terminó trágicamente. Turing se suicidó en 1954, abrumado por las presiones sociales causadas por su homosexualidad. Gödel, por su parte, sufrió a lo largo de toda su vida de periódicos y cada vez más profundos ataques de paranoia. Finalmente, en 1978, convencido de que existía una conspiración para envenenarlo, dejó de comer y murió de inanición.
(2) El artículo original de Turing lleva por título: On computable numbers with an aplication to the Entscheidungsproblem, y fue publicado en el Proceedings of London Mathematical Society, vol. 42 (1937), pp. 230 – 265.
(A la parte 2 - A la parte 4)
La máquina de Turing
En 1936, independientemente y con pocos meses de diferencia, se crearon dos definiciones matemáticas del concepto de algoritmo. La primera fue concebida por el lógico norteamericano Alonzo Church y la segunda, por el lógico inglés Alan Turing (1). Aunque ambas concepciones son equivalentes, la idea de Turing resulta intuitivamente más clara, por lo que en toda la exposición sólo nos referiremos a ella (2).
Para Turing el concepto de algoritmo puede asimilarse al de una máquina abstracta, una computadora teórica hoy conocida como máquina de Turing. Esta máquina consta en primer lugar de una cinta, en la cual se anotará la entrada y la salida del algoritmo y que servirá a la vez de memoria de trabajo del dispositivo.
La cinta está dividida en celdas o casillas, cada una de las cuales puede contener un único símbolo (que indicaremos como #) o bien puede estar vacía. La cinta, además, es potencialmente infinita, esto significa que tanto hacia la derecha como hacia la izquierda podemos agregar todas las celdas que sean necesarias. La cantidad inicial de símbolos # es siempre finita.
La máquina consta también de un cursor que puede ver el contenido de una casilla a la vez. Cuando la casilla observada está vacía el cursor puede, si sus instrucciones así lo indican, anotar en ella un símbolo #. Si la casilla tiene ya un símbolo #, el cursor puede borrarlo, dejando la casilla vacía. Por otra parte, el cursor puede moverse a razón de una casilla por vez, tanto hacia la derecha como hacia la izquierda. Debido a la infinitud de la cinta, el cursor nunca encontrará límites para su movimiento.
Las acciones del cursor están dirigidas por un programa o conjunto de instrucciones. En un momento dado, la máquina puede estar en uno de una cantidad finita de estados posibles (que indicaremos como q0, q1, q2,..., qn). El programa le indica a la máquina qué debe hacer dependiendo del estado en que ésta se encuentre y de qué contenido tenga la casilla que el cursor está viendo.Consideremos por ejemplo el siguiente programa:
q1 + # -> 0 D q2
q1 + 0 -> 0 I q1
q2 + # -> # S q0
q2 + 0 -> 0 D q2
A la izquierda aparecen todos los estados en que la máquina puede hallarse, excepto q0, y el contenido de la casilla que observa el cursor (0 es vacío). A la derecha se indica qué debe hacer el cursor en cada circunstancia. La primera instrucción (la máquina está en el estado q1 y el cursor está viendo un #) dice que el cursor debe borrar el símbolo de la casilla (ésta queda vacía) y luego debe moverse un lugar a la derecha, luego la máquina finalmente pasa al estado q2. La segunda instrucción dice que (si la máquina está en el estado q1 y el cursor está viendo una casilla vacía) entonces la celda debe quedar vacía, el cursor se mueve un lugar a la izquierda y la máquina queda en el estado q1. La S de la tercera instrucción significa que el cursor queda en su posición inicial. El estado q0 es el estado final, cuando la máquina pasa a él se detiene de inmediato. Es decir, el estado q0 indica que el cómputo ha terminado.
Convenimos en que inicialmente cualquier máquina se encontrará en el estado q1 y que el cursor observará el primer símbolo # de la izquierda.
Notas:
(1) Turing había nacido en 1912, por lo que, como Gödel, tenía menos de 25 años al publicar su trabajo fundamental. Tristemente, la vida de ambos fue difícil y terminó trágicamente. Turing se suicidó en 1954, abrumado por las presiones sociales causadas por su homosexualidad. Gödel, por su parte, sufrió a lo largo de toda su vida de periódicos y cada vez más profundos ataques de paranoia. Finalmente, en 1978, convencido de que existía una conspiración para envenenarlo, dejó de comer y murió de inanición.
(2) El artículo original de Turing lleva por título: On computable numbers with an aplication to the Entscheidungsproblem, y fue publicado en el Proceedings of London Mathematical Society, vol. 42 (1937), pp. 230 – 265.
(A la parte 2 - A la parte 4)
Suscribirse a:
Entradas (Atom)