[c&p] A través de su "máquina", Turing demostró que existen problemas que un ordenador no puede resolver, existen funciones que no es posible calcular mediante la "máquina de Turing", ya que no admiten una solución algorítmica. El más conocido de ellos es el "problema de la parada".
Más en la wikipedia:
En inglés: http://en.wikipedia.org/wiki/Halting_problem
En español: http://es.wikipedia.org/wiki/Problema_de_la_parada
Un problema relacionado matemáticamente es el de la compresión de datos.
En principio un número irracional necesita un número infinito de cifras para ser representado. Pensemos en un número como pi: 3.1415926535....
Pero existen algoritmos finitos* (en definitiva, programas informáticos*) que son capaces de calcular pi con cualquier precisión decidida de antemano. En ese sentido podemos decir que el número pi es "comprimible" (o "compresible", como gusten).
Sin embargo, hay números que podemos definir, pero que no podemos calcular de manera eficiente, y se puede demostrar que no se pueden calcular usando el problema de la parada.
Por ejemplo, en teoría de la computación, podemos diseñar un método que asigne a cada algoritmo (o programa en un lenguaje de computación, ya sea en la máquina de Turing o en lenguaje GOTO u otro sistema equivalente) un número natural.
Podemos, más aún, definir la probabilidad de que un programa aleatoriamente elegido pare, y con ciertas restricciones de naturaleza matemática, demostrar que es un número** bien definido entre 0 y 1 (en Matemáticas, las probabilidades se suelen tomar entre 0 y 1, no en términos porcentuales).
No es posible, sin embargo, calcular ese número (que se llama omega), en el sentido de que no existe ningún algoritmo que lo calcule, como consecuencia del problema de la parada: http://en.wikipedia.org/wiki/Halting_probability o http://es.wikipedia.org/wiki/Constante_de_Chaitin
*Sí, ya sé que la mayoría de definiciones de algoritmo que circulan incluyen la finitud en la definición, y que no es necesariamente lo mismo un algoritmo que un programa informático, no me saltéis a la yugular. Lo pongo como explicación para los que estén menos puestos en el tema.
**Ese número depende de la codificación usada para los programas, pero una vez decidida dicha codificación, el número está bien definido.
la existencia de algoritmos infinitos como lo dice #1, es a veces necesaria para poder comprender ciertos numeros como pi epero es verdad que debe existir algo o alguien que para una maquina de manera automatica si el proceso se convierte en una serie de bucles infinitos
Comentarios
Más en la wikipedia:
En inglés: http://en.wikipedia.org/wiki/Halting_problem
En español: http://es.wikipedia.org/wiki/Problema_de_la_parada
Un problema relacionado matemáticamente es el de la compresión de datos.
En principio un número irracional necesita un número infinito de cifras para ser representado. Pensemos en un número como pi: 3.1415926535....
Pero existen algoritmos finitos* (en definitiva, programas informáticos*) que son capaces de calcular pi con cualquier precisión decidida de antemano. En ese sentido podemos decir que el número pi es "comprimible" (o "compresible", como gusten).
Sin embargo, hay números que podemos definir, pero que no podemos calcular de manera eficiente, y se puede demostrar que no se pueden calcular usando el problema de la parada.
Por ejemplo, en teoría de la computación, podemos diseñar un método que asigne a cada algoritmo (o programa en un lenguaje de computación, ya sea en la máquina de Turing o en lenguaje GOTO u otro sistema equivalente) un número natural.
Podemos, más aún, definir la probabilidad de que un programa aleatoriamente elegido pare, y con ciertas restricciones de naturaleza matemática, demostrar que es un número** bien definido entre 0 y 1 (en Matemáticas, las probabilidades se suelen tomar entre 0 y 1, no en términos porcentuales).
No es posible, sin embargo, calcular ese número (que se llama omega), en el sentido de que no existe ningún algoritmo que lo calcule, como consecuencia del problema de la parada: http://en.wikipedia.org/wiki/Halting_probability o http://es.wikipedia.org/wiki/Constante_de_Chaitin
*Sí, ya sé que la mayoría de definiciones de algoritmo que circulan incluyen la finitud en la definición, y que no es necesariamente lo mismo un algoritmo que un programa informático, no me saltéis a la yugular. Lo pongo como explicación para los que estén menos puestos en el tema.
**Ese número depende de la codificación usada para los programas, pero una vez decidida dicha codificación, el número está bien definido.
la existencia de algoritmos infinitos como lo dice #1, es a veces necesaria para poder comprender ciertos numeros como pi epero es verdad que debe existir algo o alguien que para una maquina de manera automatica si el proceso se convierte en una serie de bucles infinitos