Autor Tema: Sobre Relaciones semirrecursivas

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

10 Agosto, 2017, 09:52 pm
Leído 835 veces

alexpglez

  • Novato
  • Mensajes: 119
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Tenía una duda acerca de las relaciones semirrecursivas, en concreto en el libro de Lógica de Carlos Ivorra (es el que voy siguiendo), se menciona: "una relación es semirrecursiva si existe un algoritmo que, cuando
se cumple, nos permite comprobar que se cumple, pero si no se cumple, tal vez no lleguemos nunca a saber que no se cumple (el algoritmo puede prolongarse indefinidamente en el tiempo de modo que nunca tengamos la certeza de si terminará en algún momento o si no parará nunca)".

Entiendo que si es semirrecursiva ([texx] \Sigma_1 [/texx]), entonces por la completitud de Q para esta clase de fórmulas, si se da, entonces es demostrable (pero no se puede decir lo mismo de si no se da). Pero no veo cómo se utiliza la tesis de Church-Turing en tal argumento, para poder decir que existe un algoritmo que lo demuestre.

Gracias, saludos.

10 Agosto, 2017, 10:14 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 9,065
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Consideremos una relación de la forma \( R(x) \) si y sólo si existe un natural \( y \) tal que \( S(x, y) \), donde \( S(x,y) \) es una relación recursiva.

El hecho de que \( S \) sea recursiva implica que existe un algoritmo que permite calcularla en un un tiempo finito para cada par de números naturales \( x, y \). Esto no requiere la tesis de Church-Turing, sino que la definición de relación recursiva muestra que siempre existen algoritmos para calcular las relaciones recursivas.

Esto nos da un algoritmo que, cuando un número \( x \) cumple \( R(x) \), nos comprueba que es así. Basta ir comprobando si se cumple \( S(x 0) \), \( S(x, 1) \), \( S(x, 2) \), etc. Si se cumple \( R(x) \), tras un número finito de pasos, llegaremos a un \( y \) que cumpla \( R(x, y) \), y el algoritmo se detendrá diciéndonos cuál es el mínimo \( y \) posible.

En cambio, si no se cumple \( R(x) \), el algoritmo no se detendrá, sino que iremos comprobando que no se cumple \( S(x 0) \), ni \( S(x, 1) \), etc., pero siempre nos quedará la duda de si en algún momento llegaremos a un \( y \) que pare el algoritmo.

Si lo dejamos aquí, para esto no hace falta Church-Turing.

Ahora, supongamos que \( R(x) \) es semirrecursiva pero NO recursiva. Entonces, por Church-Turing sabemos que no existe ningún algoritmo que permita verificar si se cumple \( R(x) \) para cualquier número. Pero sabemos que si \( x \) cumple \( R(x) \), entonces podemos comprobarlo algorítmicamente, luego concluimos que cualquier algoritmo que pretenda comprobar \( R(x) \) no dará respuesta para algunos valores de \( x \) que NO cumplen la relación.

No estoy seguro de si era esto lo que preguntabas.

11 Agosto, 2017, 02:45 am
Respuesta #2

alexpglez

  • Novato
  • Mensajes: 119
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
En realidad, tampoco sé muy bien a qué te referías con la frase del libro.

Respecto a la explicación, la comprendo bien. No había pensado en tal algoritmo para demostrar que se da R.

Gracias

11 Agosto, 2017, 11:08 am
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 9,065
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Se puede decir más:

Supón que \( R(x) \) es una relación para la que tienes un algoritmo que, cuando es cierto \( R(x) \), confirma que así es, pero que si no se cumple \( R(x) \) tal vez no se detenga o no concluya nada. Entonces puedes considerar la relación \( S(x, n) \) que se cumple si y sólo si el algoritmo ha confirmado que se cumple \( R(x) \) al cabo de \( n \) pasos. Esta relación siempre la puedes calcular en un tiempo finito, luego por la tesis de Church-Turing es recursiva, y  \( R(x) \) equivale a la existencia de un \( n \) que cumpla \( S(x, n) \), luego es semirrecursiva.