¿Existe una natural medida sobre el conjunto de afirmaciones que son verdaderas en el modelo habitual (es decir. $\mathbb{N}$ ) de la aritmética de Peano que permite averiguar si "la mayoría" de las sentencias verdaderas son demostrables o no? Con la palabra "natural" intento excluir las medidas definidas en términos de la función característica del conjunto de sentencias verdaderas.
Respuestas
¿Demasiados anuncios?
Me parece que tanto la probabilidad de que una afirmación sea demostrable como la de que sea indecidible deberían estar acotadas lejos de 0, para cualquier distribución de probabilidad razonable.
Sea $C_n$ sea el número de enunciados gramaticales de longitud $n$ . Para cualquier afirmación $S$ la declaración
$S$ o $1=1$
es un teorema. Por tanto, el número de enunciados demostrables de longitud $n$ está limitada por debajo por $C_{n-k}$ où $k$ es el número de caracteres necesarios para etiquetar en "o $1=1$ ".
Por otra parte, dejemos que $G$ sea una sentencia indecidible, y $S$ cualquier frase. Entonces
O bien $S$ y $1 \neq 1$ o bien $G$
es indecidible. Así que el número de sentencias indecidibles de longitud $n$ está limitada por debajo por $C_{n-\ell}$ para una constante $\ell$ . Para cualquier gramática razonable, las proporciones $C_{n-k}/C_n$ y $C_{n- \ell}/C_n$ deben estar ambos acotados lejos de 0.
Actualmente estoy tratando de averiguar por qué mi cálculo es aparentemente incompatible con la papel de Calude y Jurgensen citado por Konrad . Sospecho que la respuesta está oculta en la definición de prefijo libre, en la página 4, pero me cuesta entenderla. ¿Alguna ayuda?
Arda Xi
Puntos
1099
Actualización: en respuesta al comentario de abajo, ya no estoy seguro de que la probabilidad en cuestión fuera 0.
Probemos la medida que da el mismo peso a cualquier afirmación verdadera de longitud fija $N$ (escrito en inglés matemático).
Entonces tenemos afirmaciones de la forma "S o 1+2=3" que forman más entonces $1/10^{20}$ de todas las afirmaciones verdaderas de una longitud determinada. Por otra parte, las afirmaciones "S y Z" (donde Z es un problema indecidible) forman también algún subconjunto de medida positiva (acotada por debajo) en los enunciados de longitud dada.
Así que, sí, para la medida descrita anteriormente la medida de declaraciones demostrables está dentro de unos límites positivos $[a, b]$ para cualquier $N$ mayor que algunos $N_0$ .
Pero esa medida es proporcional, para un fijo $N$ a la función característica del conjunto de todos los enunciados verdaderos, así que no, mi respuesta no da una medida "natural".
Creo que la probabilidad de "un enunciado verdadero aleatorio es demostrable" es 0 en cualquier buena formalización de tu problema.
He aquí el razonamiento: considere un enunciado verdadero indecidible S . Ahora yo diría que en cualquier definición razonable de probabilidad el enunciado largo contendrá S con una probabilidad que va a 1 a medida que aumenta su longitud. No se puede demostrar hasta que no hay una definición de esta probabilidad, pero el hecho relacionado con las cadenas es sencillo:
Considere cualquier cadena
S. Entonces la probabilidad $P(n) := \{$ la cadena aleatoria de longitud $n$ contiene `S $\}$ pasa a 1 a medida que $n\to \infty$ .
La prueba puede hacerse considerando las cadenas aleatorias de la forma (trozo 1)(trozo 2)...(trozo N ) donde todos los trozos tienen la misma longitud que S .
Nikos Steiakakis
Puntos
2651
Ilya acertó en su respuesta.
En primer lugar, la medida natural que se suele utilizar cuando se tiene un conjunto discreto de objetos, cada uno de cierta "complejidad" finita n y sólo con un número finito de complejidad n es considerar la probabilidad para n y, a continuación n van al infinito (véase la teoría de los grafos aleatorios).
En segundo lugar, la probabilidad de una afirmación verdadera de longitud n siendo demostrable efectivamente tiende a 0 como n llega hasta el infinito. Así lo han demostrado Cristian Calude y Helmut Jürgensen (Adv Appl Math 35 (2005), 1-15).
Menos mal que nuestro trabajo no consiste en demostrar afirmaciones aleatorias.
Advertencia: esto es válido para teorías sólidas y consistentes en las que se pueda formalizar la aritmética de Peano.
Prasham
Puntos
146
Hay un número infinito de teoremas verdaderos demostrables en PA y un número infinito de teoremas verdaderos indemostrables. Así que cualquier medida debe ir a cero para todos, pero un número finito de sentencias Creo que habrá un problema con el conocimiento de p en que uno puede buscar todas las sentencias de menor ponderación y encontrar el porcentaje de sentencias verdaderas de modo que se puede llegar a un punto en el que algunas sentencias pueden tener que ser indecidibles para que la probabilidad funcione. Si este es el caso, entonces el conocimiento de la probabilidad haría que algunas sentencias fueran indecidibles, por lo que la probabilidad no puede ser conocida y la prueba de que existe tendría que ser no constructiva, lo que podría causar problemas con algunas filosofías de las matemáticas como el intuicionismo. Recuerdo una pregunta similar sobre ordenadores cuánticos en la que la respuesta fue 1/2.
He encontrado una referencia que dice que ninguna probabilidad de detención es computable. Si la prueba pudiera convertirse en un proceso que o bien tiene éxito o bien nunca se detiene, entonces eso demostraría que la probabilidad de un teorema indecidible no es computable.
http://en.wikipedia.org/wiki/Chaitin%27s_constant#Interpretation_as_a_probability
