Para comenzar la teoría de la computación Necesitamos una noción de qué significa que algo es computable y, aparte de la existencia de lo que en su día se llamó computadoras mecánicas, y al final electrónicas, como las que usamos hoy, computadora, de hecho era una persona, normalmente una mujer, que hacía cálculos necesarios, frecuentemente para militares, y hay que cuestionarse, si queremos razonar sobre la computación, si necesitamos una definición de qué significa que algo sea computable. En los años 1930, Godel, Church, Turing y otros hicieron varias propuestas sobre qué significa que algo sea coputable y probaron varios teoremas sobre ello. Y fue realmente Turing, en 1936, quien, no solo propuso de qué significa ser computable sino que dio una razón de por qué ésta era la definición correcta. En este segmento vamos a revisar el argumento de Turing y el modelo de computación de Turing. Debo decir desde el principio que este modelo de computación influenció a Von Newmann, que al final llevó a la creación de la computadora moderna, pero, esencialmente, la base del argumento es que, cualquier cosa que imaginemos que es computable en algún sentido, es realmente capturado por esta definición. Y previo a esta definición... ahora, computar significa computar en tu portátil ¿verdad? Pero queremos una definición más abstracta porque, cuando se hizo esta definición no tenían portátil ni computador de sobremesa No tenían nada. Es ciertamente una definición abstracta sobre el proceso de computación. Así que el argumento de Turing es algo así: Digamos que tratas de computar un número o quizá una función ¿verdad? Te doy un número y se aplica una función a ese número ¿Qué haces? Bueno, típicamente trabajas en papel, aunque no importa que sea papel, puede ser una pizarra, puede ser un computador moderno, pero hay un lugar donde registrar datos. Y Turing lo idealizó como una cinta -de hecho, en la construcción original de los ordenadores, era un tipo de cinta- una cita unidimensional, por simplicidad, porque si quieres el modelo más simple para captar lo que estás hablando es más sencillo de razonar. Los ordenadores modernos no tienen una cinta unidimensional, pero realmente eso no afecta la noción de computación. Así que, tienes una cinta unidimensional dividida en cuadrados, o celdas, y en cada celda puedes poner un símbolo. Puede ser un dígito, como 0 o 1, o una letra, como a o b. Pero lo importante es que las celdas individuales en la cinta son reconocibles ¿verdad? y puedes decir dónde comienza y acaba una celda, y solo hay un número limitado de símbolos. Y hay una gran discusión acerca de por qué debe haber un número limitado de símbolos ¿sabes? parece muy restrictivo. Bueno, sí y no. ¿verdad? Por una parte, solo hay que buscar los que hay Por otra parte, solo podemos usar un número finito de símbolos, ¿verdad? Usamos quizá un puñado de alfabetos de lenguas diferentes y algunos dígitos, pero es una lista finita de símbolos. Y si necesitas más, construyes símbolos compuestos. ¿Verdad? Quizá digas algo como ¡oh! ésto, aunque está hecho con 2 símbolos, voy a tratarlo como como un único símbolo. Así que, de nuestra lista finita de símbolos puedes obtener realmente una lista tan extensa como quieras. OK Así, escribes en el papel o en el computador, o donde sea, que hemos idealizado como una cinta, escribes un número finito de símbolos y entonces tratas de hacer este argumento acerca de qué es lo que estás haciendo. ¿Estás haciendo un proceso automático? O sea, ¿tienes una secuencia de pasos en mente? ¿Sólo hay un número finito de pasos? y puedes repetirlos sucesivamente De hecho, podrías incluso construir un proceso que lleve a repetirlo infinitas veces. Pero solo hay un número finito de tipos de pasos que puedes realizar. ¿Verdad? No puedes mantener en mente una secuencia de instrucciones que tiene un número infinito de instrucciones que cambia todo el tiempo. ¿Verdad? Tienes que estar leyéndolo de algún sitio. Y estas instrucciones pueden estar escritas en una cinta, pero... volveremos sobre ello. Así que, tienes una cinta que imaginamos tan larga como quieras, ¿Ok? La abstracción matemática es infinita, pero no es tan crucial, es simplemente tan larga como quieras. Si necesitas más espacio de disco duro conectas un disco duro externo, ¿verdad? Tienes un número finito de símbolos y tú, el computador, en este caso, tienes una lista finita de instrucciones que vas a seguir. Y la forma de modelar ésto es que hay un controlador que, por sí mismo, tiene un número limitado de estados en los que puede encontrarse, estados que, aproximadamente, corresponden a la lista de instrucciones a seguir. Y, ¿qué hacen estos estados? Los estados dicen qué hacer a continuación Así que, ¿qué va a hacer? Bien Mira a un cuadrado particular en la cinta y, basándose en lo que hay en ese cuadrado y en el estado en que se encuentra, decide qué hacer a continuación. Quizá es reescribir el cuadrado, o sea, quizá la instrucción actual es si hay una a, convertirla en una c -esta sería una parte de la computación- o quizá decide, según lo que hay en ese cuadrado, tengo que mirar en el siguiente cuadrado Así que, en vez de estar aquí ahora voy a mirar en este cuadrado. O quizá voy a hacer una de estas 2 cosas, pero además voy a mover a la siguiente instrucción Y eso cambia mi estado mental interno. Y ésto es esencialmente. Éste es el modelo de Turing del computador que ahora llamamos máquina de Turing, y el argumento que Turing hizo captura esencialmente todo lo que naturalmente llamarías computable por medios finitos. ¿Ok? Y aunque ha habido propuestas para modelar computadores que va potencialmente más allá de ésto, usualmente implican algún tipo de infinito tomando infinitos pasos, en un tiempo infinito, y cosas de este tipo, pero no son consideradas prácticas en términos generales. Hay algunas propuestas basadas en agujeros negros, en mecánica cuántica, y cosas de este tipo, pero, de nuevo, no práctico. Incluso las propuestas para computadores cuánticos que, de hecho, queremos construir, cuando hablamos de computar una función que toma una lista finita de símbolos y produce una lista finita de símbolos, incluso en éstos no son más potentes en términos de qué son capaces de computar que las máquinas de Turing. Y este argumento de que cualquier cosa que puedas imaginar puede ser simulado por máquinas de Turing es el tipo de argumento es el tipo de argumento que Godel y Church e incluso Turing, pero en particular Godel y Church usaban antes de que apareciera Turing. Turing llegó y dijo, no solo tengo este modelo que puede simular cualquier modelo de computación que puedas imaginar, cualquier modelo computacional de tipo razonable o práctico que puedas imaginar, sino que este es un argumento del porqué ¿verdad? Y explícitamente dice que este argumento apela a la intuición, ¿verdad? lo que intuitivamente queremos decir de algo que es computable con estados finitos, y, por tanto, es necesariamente, matemáticamente, insatisfactorio. Lo que se conoce como tesis de Church-Turing, que, en cierto sentido fue mucho más fuertemente argumentado por Turing, es que cualquier modelo de computación puede ser simulado por máquinas de Turing. Y, por tanto, cualquier cosa considerada computable es computable por máquinas de Turing. Y también está lo que conocemos como la tesis física de Church-Turing en la que cambias el sentido, no de algo que es computable de forma abstracta, sino computable por máquinas de estado finito en el mundo físico, y, de nuevo, todas estas cosas, aunque suenan elegantes y oficiales, significa que realmente apelan a la intuición de lo que queremos decir de algo que es computable. Ahora bien, debo decir que este modelo de computación específicamente por la configuración en la que tienes un conjunto discreto de inputs, como nombres, o cadenas de símbolos y una función específica que les quieres aplicar, entonces, si tienes ésto, ¿verdad? digamos una función computable - no sé- f(a) = x^2 y te doy un número como como x = 123, esto encaja en este marco. Y puedes imaginar ¡oh! quizá puedo conseguir algo más potente que ésto usando aleatorización, de alguna manera.