29/01/2020, 08:30:17 am *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Homenaje a NUMERARIUS
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Church-Turing  (Leído 2252 veces)
0 Usuarios y 1 Visitante están viendo este tema.
Raúl Aparicio Bustillo
Pleno*
*****

Karma: +0/-3
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 3.067


Ver Perfil
« : 21/10/2015, 02:58:01 am »

Informáticos, ¿aceptáis la tesis de Church-Turing,  que toda función recursiva (definición de recursividad en matemáticas, a partir de las funciones recursivas elementales?)  se puede programar en un ordenador, sea físicamente fabricable o no, vamos, lo que es una maquina de Turing, y  que toda función programable en un ordenador en nuestro universo (esta vez no digo maquina de Turing) es matemáticamente recursiva. ¿Por qué?

Es la parte en negrita de la tesis la que no termino de ver claro
En línea
avmath
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 82


Ver Perfil
« Respuesta #1 : 04/11/2015, 17:27:11 pm »

No te voy a dar una respuesta bien formada, de hecho es la primera vez que veo dicha tesis. Pero de igual manera, creo que sí. Todo bucle, que básicamente es una estructura condicional, puede transformarse en un algoritmo recursivo con un caso base que sería igual a la condición de parada del bucle.

Si dicho caso base se cumple se termina la llamada recursiva y si no se haría lo que había dentro del cuerpo del bucle(donde puede haber cualquier cosa, incluso otros bucles susceptibles de ser funciones recursivas).

Y básicamente todo en programación(al menos imperativa) son bucles y estructuras condicionales al fin y al cabo. De hecho hay lenguajes puramente funcionales tales como Haskell o Lisp.

Un saludo.
En línea
Raúl Aparicio Bustillo
Pleno*
*****

Karma: +0/-3
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 3.067


Ver Perfil
« Respuesta #2 : 19/11/2015, 04:35:28 am »

Cita
Todo bucle, que básicamente es una estructura condicional, puede transformarse en un algoritmo recursivo con un caso base que sería igual a la condición de parada del bucle.

Aquí es donde surge mi duda. ¿Por qué un bloque se puede transformar en un algoritmo recursivo siempre? De hecho, creo que es esta parte de la respuesta la que incluye mi pregunta
En línea
argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.283

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #3 : 19/11/2015, 13:09:40 pm »

Cita
Todo bucle, que básicamente es una estructura condicional, puede transformarse en un algoritmo recursivo con un caso base que sería igual a la condición de parada del bucle.

Aquí es donde surge mi duda. ¿Por qué un bloque se puede transformar en un algoritmo recursivo siempre? De hecho, creo que es esta parte de la respuesta la que incluye mi pregunta

Las funciones recursivas no son sólo las definidas por recurrencia,
sino también otras definidas por composición,
y otras definidas tomando un mínimo.

En línea

Raúl Aparicio Bustillo
Pleno*
*****

Karma: +0/-3
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 3.067


Ver Perfil
« Respuesta #4 : 19/11/2015, 15:23:17 pm »

Gracias, el_manco, pero lo que no veo es la relación con la maquina de Turing. En realidad, mi problema real es ese. Lo he leído en el libro varias veces y en otros sitios de Internet y no. Porque está demostrado formalmente que las funciones recursivas de Gödel son las que puede calcular una maquina de Turing, ¿no? Aunque Ivorra dice que hay una parte de la demostración que no se puede formalizar, que es metamatemática. No llego a entender la idea de computabilidad por más que me esfuerce. A ver, de las 2 partes recíprocas de la tesis, la de que se puede programar un ordenador para calcular una función recursiva es trivial. Evidentemente es la otra parte la que no entiendo
En línea
argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.283

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #5 : 19/11/2015, 17:10:48 pm »

Gracias, el_manco, pero lo que no veo es la relación con la maquina de Turing. En realidad, mi problema real es ese. Lo he leído en el libro varias veces y en otros sitios de Internet y no. Porque está demostrado formalmente que las funciones recursivas de Gödel son las que puede calcular una maquina de Turing, ¿no? Aunque Ivorra dice que hay una parte de la demostración que no se puede formalizar, que es metamatemática. No llego a entender la idea de computabilidad por más que me esfuerce. A ver, de las 2 partes recíprocas de la tesis, la de que se puede programar un ordenador para calcular una función recursiva es trivial. Evidentemente es la otra parte la que no entiendo

Es que los cálculos son complejos.

Quizás en algún momento podríamos discutir a fondo los cálculos.
En este momento no se me ocurre cómo expresarlos de forma simplificada.

Saludos.
En línea

Carlos Ivorra
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 9.081


Ver Perfil WWW
« Respuesta #6 : 19/11/2015, 17:19:46 pm »

Gracias, el_manco, pero ...

Aunque Ivorra dice que hay una parte de la demostración que no se puede formalizar, que es metamatemática.

Ivorra nunca ha dicho eso. Sigues confundiendo lo que dicen los libros con lo que tú entiendes cuando los lees. Y va como del día a la noche.

Firmado: el_manco
En línea
Raúl Aparicio Bustillo
Pleno*
*****

Karma: +0/-3
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 3.067


Ver Perfil
« Respuesta #7 : 19/11/2015, 23:16:47 pm »


Cita
Ivorra nunca ha dicho eso. Sigues confundiendo lo que dicen los libros con lo que tú entiendes cuando los lees. Y va como del día a la noche.

Firmado: el_manco

En la página 120 del libro Lógica y Teoría de Conjuntos (Carlos Ivorra Castillo), en la introducción al capítulo 5:

"...Es muy importante tener presente que el contenido de este capítulo es enteramente
metamatemático, es decir, nada de lo que digamos tiene ninguna relación
con ningún sistema deductivo formal ni, en particular, con ningún lenguaje formal..."

En la página 159 del mismo volumen:
"...Algunos autores afirman que la tesis de Church-Turing es indemostrable, porque la noción de computabilidad mediante un algoritmo
no admite una definición precisa. Lo que hay de verdad en esta afirmaciones que la noción de computabilidad es metamatemática, y cualquier intento de
formalización, por ejemplo, a través de la noción de función computable por una máquina de Turing, suscita la duda de si realmente estamos capturando la
totalidad de las funciones computables en sentido metamatemático..."

Son estos 2 parráfos los que me llevan a confusión. La Wikipedia (tengo algo de recelo - creo que justificado - hacia ella pero...) afirma que la equivalencia entre función recursiva y función Turing-computable está demostrada (aunque no sé si la demostración es metamatemática o formalizada realmente rn ZFC) Gracias por adelantado, Argentinator, por si pudieras aclararme en un futuro dichas nociones.

En línea
Carlos Ivorra
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 9.081


Ver Perfil WWW
« Respuesta #8 : 20/11/2015, 18:10:41 pm »

En la página 120 del libro Lógica y Teoría de Conjuntos (Carlos Ivorra Castillo), en la introducción al capítulo 5:

"...Es muy importante tener presente que el contenido de este capítulo es enteramente metamatemático, es decir, nada de lo que digamos tiene ninguna relación con ningún sistema deductivo formal ni, en particular, con ningún lenguaje formal..."

Eso lo he dicho yo, y es cierto.

En la página 159 del mismo volumen:
"...Algunos autores afirman que la tesis de Church-Turing es indemostrable, porque la noción de computabilidad mediante un algoritmo no admite una definición precisa. Lo que hay de verdad en esta afirmaciones que la noción de computabilidad es metamatemática, y cualquier intento de formalización, por ejemplo, a través de la noción de función computable por una máquina de Turing, suscita la duda de si realmente estamos capturando la totalidad de las funciones computables en sentido metamatemático..."

Eso lo he dicho yo, y es cierto.

Porque está demostrado formalmente que las funciones recursivas de Gödel son las que puede calcular una maquina de Turing, ¿no? Aunque Ivorra dice que hay una parte de la demostración que no se puede formalizar, que es metamatemática.

Eso lo has dicho tú, luego es falso.

Son estos 2 parráfos los que me llevan a confusión.

Eso lo has dicho tú, luego es falso. No son esos párrafos los que te llevan a confusión. Lo que te lleva a confusión es que estás haciendo preguntas sobre las funciones recursivas y sobre la tesis de Church--Turing sin tener ni      idea de lo que son las funciones recursivas ni de lo que afirma la tesis de Church-Turing.

Por ejemplo, tu "confusión" deja traslucir que crees que la tesis de Church-Turing equivale a que las funciones recursivas coinciden con las Turing-computables. Y eso no es cierto. (Sí que es cierto que las funciones recursivas equivalen a las Turing-computables, lo que digo que no es cierto es que eso sea la tesis de Church-Turing.)
En línea
argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.283

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #9 : 20/11/2015, 21:49:02 pm »

Estimado Raul.
Este tema es tan arduo de explicar que he llegado a comprender que cuando Ivorra te dice que no tienes ni idea de lo que estás hablando, no es algo agraviante, sino la màz generosa respuesta que alguien pudiera darte. ¡Ivorra es bueno! ¡Aleluya!
En línea

feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 8.731



Ver Perfil
« Respuesta #10 : 21/11/2015, 07:16:47 am »


En la página 120 del libro Lógica y Teoría de Conjuntos (Carlos Ivorra Castillo), en la introducción al capítulo 5...


Dice que “eso” de lo que se está hablando (de lo que yo tampoco tengo ni puñetera idea) podría no ser demostrable según algunos autores (de donde se deduce que podrían existir otros autores que opinaran que, aunque no esté demostrado aún, sí se podría demostrar). También añade que los autores que piensan que no es demostrable lo hacen porque sostienen que la noción de computabilidad mediante un algoritmo no tiene una definición precisa (y es de suponer que piensan que nunca la podrá tener y, de ahí, su afirmación).

 Se dice, igualmente, que cualquier intento de formalización hace dudar de si realmente se está capturando la totalidad de las funciones computables; lo que quiere decir que se puede intentar demostrar (mediante una formalización, claro) al igual que se puede intentar demostrar cualquier conjetura; que se llegue a conseguirlo o no, ya, es otra cosa.

Sea lo que sea “eso” de lo que se está hablando, no es lo único en matemáticas que no se ha demostrado todavía o que, quizá, no se pueda demostrar, hay muchas conjeturas no demostradas. Como es natural, nadie puede formalizar el teorema que resuelve la hipótesis de Riemann, por ejemplo, sin demostrarlo, como no se puede comer sin abrir la boca. Entiendo que lo que Carlos trata de decirte es que el que no esté demostrado algo, o el que sea indemostrable, no equivale a decir que no sea formalizable; un ejemplo: a toda cosa que podemos ver le podemos asignar una palabra, pero si no la vemos, o no la sentimos ni tenemos noticia de ella, pues no la podemos definir; pero no porque no sea definible en sí, no es ésa la causa. A lo mejor algún día aparece algo “visible” a lo que no podemos asignar una palabra (aunque me resulta imposible imaginar esto) y entonces podremos decir “a tal cosa no se le puede poner un nombre”  (lo cual es contradictorio, pues para poder decir eso, también tendríamos que poder ponerle un nombre). Por eso, no cabe en la cabeza fácilmente que algo no sea formalizable, lo que sí cabe en la cabeza es que algo se no sea demostrable.
En línea

Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!