Autor Tema: ¿QUé algoritmo distingue números computables de no computabes?

0 Usuarios y 1 Visitante están viendo este tema.

01 Agosto, 2015, 05:35 pm
Leído 5191 veces

Raúl Aparicio Bustillo

  • Matemático
  • Mensajes: 3,105
  • Karma: +0/-3
  • Sexo: Masculino
¿Cómo puede reconocer un ordenador que un número que esté intentando calcular es no computable y que no va a llegar más allá de unas cuantas cifras en su aproximación?

01 Agosto, 2015, 06:05 pm
Respuesta #1

feriva

  • Matemático
  • Mensajes: 9,077
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
  • No soy matemático, eso es una etiqueta.
¿Cómo puede reconocer un ordenador que un número que esté intentando calcular es no computable y que no va a llegar más allá de unas cuantas cifras en su aproximación?

Con una instrucción condicional “if”, por ejemplo, que le diga que si llega a cierto número haga un break o regrese a la rutina principal. Si no se le dice nada, y no puede con el cálculo, lo normal es que en pantalla empiecen a aparecer ceros (si se quiere que aproxime un número, sin caer en una parda o un bucle infinito, también hay que programarlo)

01 Agosto, 2015, 06:21 pm
Respuesta #2

Raúl Aparicio Bustillo

  • Matemático
  • Mensajes: 3,105
  • Karma: +0/-3
  • Sexo: Masculino
¿y cómo se sabe que van a aparecer 0´s indefinidamente o en algún momento van a dejar de aparecer y    en vez de un número no computable es un número con muchos ceros? Además, necesitaríamos memoria infinita. Si nuestro cerebro funciona como un ordenador, evidentemente no podemos reconocer todos los números no computables, pero sí algunos de ellos. O si queréis ser un poco más explicitos, como sabe un ordenador que la constante  de Chaytin no es computable, por ejemplo?

01 Agosto, 2015, 08:46 pm
Respuesta #3

feriva

  • Matemático
  • Mensajes: 9,077
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
  • No soy matemático, eso es una etiqueta.
¿y cómo se sabe que van a aparecer 0´s indefinidamente o en algún momento van a dejar de aparecer y    en vez de un número no computable es un número con muchos ceros? Además, necesitaríamos memoria infinita. Si nuestro cerebro funciona como un ordenador, evidentemente no podemos reconocer todos los números no computables, pero sí algunos de ellos. O si queréis ser un poco más explicitos, como sabe un ordenador que la constante  de Chaytin no es computable, por ejemplo?

El ordenador no sabe más que lo que se le programa. Los lenguajes utilizados, como C, Python, etc.., son programas sobre los que a la vez se programa; por decirlo en lenguaje “moderno”, son una aplicación, lenguajes de alto nivel.
 El ordenador, por dentro, funciona en el lenguaje de nivel más bajo, a base de unas celdillas que se cargan o no se cargan eléctricamente dando lugar a números binarios. El centro de operaciones es la “pila de máquina” y es donde se almacenan los valores de los registros (en forma de número binario). El registro principal, que  se llama acumulador, va cargando y descargando bits para “contar”. Para los cálculos existen unos indicadores llamados “flags”; uno de estos “flags” es el indicador de arrastre, que hace algo así como llevar la cuenta de las “llevadas” al sumar y al hacer todo tipo de operaciones. Cuando hay un desbordamiento, el indicador de arrastre pasa de valer cero a 1 y el resultado de la operación se guarda en el acumulador mediante una orden “push” (“meter dato”); esta es la mecánica básica que usa el ordenador para calcular un número. Si no hay “sitio” para guardar nada, puede provocar o bien un bloqueo (en el que la pantalla se queda estática y del que sólo se puede salir desenchufando y volviendo a empezar) o unos “jumps” (saltos) encadenados de forma que los registros se cargan y descargan cíclicamente sin fin; salvo corte de fluido eléctrico, que es la única manera de recuperar el control. Y esto (según el programa que estemos haciendo y en qué dirección de memoria acabe) a veces se puede ver como una sucesión de filas de ceros pasando por la pantalla (en “scroll”); personalmente lo vi muchas veces cuando intenté programar alguna cosa en código máquina con el Spectrum.
  Un bucle infinito es eso, y nunca llega a ser infinito porque alguna vez alguien desconectará el ordenador, pero, si no, sí sería infinito. 

En cuanto a la constante de Chaitin, por lo leí hace mucho, es imposible que sea generada entera por un programa porque el programa tendría que ser prácticamente infinitamente largo, así que, supongo, llega un momento en el que el ordenador no puede sacar más decimales debido a que al programa no le “caben”, no ya al ordenador; pero no me acuerdo bien y no he vuelto a leer sobre el tema.  Lo que es seguro es que ante esa situación el programa no sabe nada; se puede quedar colgado o puede parar y devolver el control siempre y cuando se haya programado para eso.


01 Agosto, 2015, 08:59 pm
Respuesta #4

luis

  • Aprendiz
  • Mensajes: 304
  • Karma: +1/-0
  • Sexo: Masculino
¿Cómo puede reconocer un ordenador que un número que esté intentando calcular es no computable y que no va a llegar más allá de unas cuantas cifras en su aproximación?

si el ordenador está calculando, lo que calcula es computable. no entiendo qué significa "lo que intenta calcular".

saludos

luis

01 Agosto, 2015, 09:27 pm
Respuesta #5

Raúl Aparicio Bustillo

  • Matemático
  • Mensajes: 3,105
  • Karma: +0/-3
  • Sexo: Masculino
Los números no calculables son los que no se puede hacer un programa en ningún lenguaje que halle todas sus cifras, no quiere decir que no se puedan aproximar hasta cierto digito decimal. ¿QUé es lo que no entiendes?

01 Agosto, 2015, 09:33 pm
Respuesta #6

luis

  • Aprendiz
  • Mensajes: 304
  • Karma: +1/-0
  • Sexo: Masculino
Los números no calculables son los que no se puede hacer un programa en ningún lenguaje que halle todas sus cifras, no quiere decir que no se puedan aproximar hasta cierto digito decimal. ¿QUé es lo que no entiendes?

qué significa "intentar calcular". calcula aquello para lo que fue programado.

saludos

01 Agosto, 2015, 09:35 pm
Respuesta #7

Raúl Aparicio Bustillo

  • Matemático
  • Mensajes: 3,105
  • Karma: +0/-3
  • Sexo: Masculino
Vete a la pregunta simplificada. ¿Cómo sabe un ordenador que la constante de Chaitin no es computable? ¿Con qué algoritmo se   le puede programar para que decida eso?

02 Agosto, 2015, 01:29 am
Respuesta #8

Juan Pablo Sancho

  • Moderador Global
  • Mensajes: 4,880
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Si quieres calcular \(  \sqrt{2}  \) mediante la recurrencia:

\(  a_1 = 1.4  \)

\( \displaystyle a_{n+1} = \frac{1}{2} \cdot (a_n + \frac{2}{a_n})  \) para \(  n \geq 1  \).

Aparte de otras condiciones, sería bueno poner \(  a_{n+1} - a_n \neq 0  \) , por que dado un \(  n_0 \in \mathbb{N}  \) te dará que \(  a_{n+1} - a_n = 0  \).

En la siguiente recurrencia habría un error por dividir por cero.

En este caso \(  \sqrt{2}  \) no es calculable, pero puedes dar una condición a la computadora para saber donde terminar.   

02 Agosto, 2015, 02:41 am
Respuesta #9

Raúl Aparicio Bustillo

  • Matemático
  • Mensajes: 3,105
  • Karma: +0/-3
  • Sexo: Masculino
Pero los números algebráicos son todos calculables,  o por lo menos es lo que dicen. He puesto como ejemplo la constante de chaintin porque no es recursiva, y qusiera saber cómo se da cuenta un ordenador que no lo es. Porque  si no es capaz de darse cuenta, entonce nuestra   mente no podría ser como un ordenador. \( \sqrt[ ]{2} \) se puede calcular a mano, el algoritmo está bien definido, otra  cosa es que no tengamos tiempo infinito para sacar los infinitos decimales. Por eso entiendo que nuestro cerebro       , de memoria limitada, no puede deducir todos los     números no recursivos, pero algunos sí. Lo de que hallaun algoritmo o no es para comparar nuestra mente con la de un ordenador es una simple comprobación de que nuestra mente es algo más que un ordenador (o quizás es un ordenador muy bien diseñado)

Gracias

02 Agosto, 2015, 03:07 am
Respuesta #10

Juan Pablo Sancho

  • Moderador Global
  • Mensajes: 4,880
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Entonces esto va por otro camino, gracias por la aclaración.

Pensaría más bien en un ordenador bien diseñado (o de última generación).

La diferencia es que nuestros prueba y error tienen la edad del hombre.

Pensaba más en un problema de métodos numéricos pero los tiros no van por ahí.

Perdón por la intromisión (llevo 2 en una semana).

02 Agosto, 2015, 05:24 am
Respuesta #11

Raúl Aparicio Bustillo

  • Matemático
  • Mensajes: 3,105
  • Karma: +0/-3
  • Sexo: Masculino
Bueno, tampoco es tan grave como para pedir perdón. Lo que no entiendo es esa frase de que la prueba y error tiene la edad del hombre.No, no tiene nada que ver con metodos numéricos, aquí se trabaja con maquinas de turing (yo no, porque no sé usarlas), pero se dice que un número es computable o recursivo cuando un programa de longitud finita te saca todas las cifras (aunque la memoría se permite sea infinita), por eso \( \sqrt[ ]{2} \) o \( \pi \), se consideran calculables, y cualquier racional, por grande que sea su periodo o su parte no periódica.no es un concepto tan relacionado con los cálculos núméricos porque ahí hay números perfectamente calculables que se tienen que truncar por falta de recursos de memoria, y estimar el error, es algo diferente

02 Agosto, 2015, 11:42 am
Respuesta #12

Carlos Ivorra

  • Administrador
  • Mensajes: 9,097
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
He puesto como ejemplo la constante de chaintin porque no es recursiva, y qusiera saber cómo se da cuenta un ordenador que no lo es. Porque  si no es capaz de darse cuenta, entonce nuestra   mente no podría ser como un ordenador. \( \\sqrt[ ]{2}  \)se puede calcular a mano

¿Lees lo que escribes? ¿No ves que la fórmula en LateX te ha quedado mal? ¿No ves que todos los demás usan bien el LaTeX y tú no? Voy a empezar a borrarte mensajes con fómulas mal escritas. Y si ésta no se arregla en breve cerraré el hilo.

En cuanto a lo que preguntas, si hablas de un ordenador con un programa heurístico equiparable a la conciencia humana, la forma de darse cuenta es la obvia: buscando en internet un libro que demuestre que la constante no es recursiva, estudiándose la demostración y entendiéndola.

02 Agosto, 2015, 11:47 am
Respuesta #13

Raúl Aparicio Bustillo

  • Matemático
  • Mensajes: 3,105
  • Karma: +0/-3
  • Sexo: Masculino


En cuanto a lo que preguntas, si hablas de un ordenador con un programa heurístico equiparable a la conciencia humana, la forma de darse cuenta es la obvia: buscando en internet un libro que demuestre que la constante no es recursiva, estudiándose la demostración y entendiéndola.

Pero no hay algoritmo para que un ordenador lea un libro y lo entienda

02 Agosto, 2015, 12:09 pm
Respuesta #14

feriva

  • Matemático
  • Mensajes: 9,077
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
  • No soy matemático, eso es una etiqueta.


Pero no hay algoritmo para que un ordenador lea un libro y lo entienda

Pues si te refieres a un ordenador de hoy en día, y no a uno que hipotéticamente se pueda fabricar en el futuro con esa capacidad de comprensión, la respuesta es clara: el ordenador no sabe nada, lo sabe el programador, igual que un coche no sabe cuándo tiene que frenar o acelerar.

02 Agosto, 2015, 12:22 pm
Respuesta #15

Carlos Ivorra

  • Administrador
  • Mensajes: 9,097
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Pero no hay algoritmo para que un ordenador lea un libro y lo entienda

Pues si te refieres a un ordenador de hoy en día, y no a uno que hipotéticamente se pueda fabricar en el futuro con esa capacidad de comprensión, la respuesta es clara: el ordenador no sabe nada, lo sabe el programador, igual que un coche no sabe cuándo tiene que frenar o acelerar.

Correcto. Y la conclusión es que una mente humana es una máquina es superior a cualquier ordenador de los que existen hoy en día, al igual que un pájaro es un aparato volador superior a cualquier artefacto volador diseñado por Leonardo da Vinci. Eso es evidente.

02 Agosto, 2015, 12:25 pm
Respuesta #16

Carlos Ivorra

  • Administrador
  • Mensajes: 9,097
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal