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.