Existe un natural de la medida sobre el conjunto de enunciados que son verdaderos en el modelo habitual (es decir,$\mathbb{N}$) de la aritmética de Peano que le permite a uno para preguntar si 'la mayoría' true sentencias son demostrables o no? Por la palabra 'natural' estoy tratando de excluir las medidas definidas en términos de la función característica del conjunto de verdaderas penas.
Respuestas
¿Demasiados anuncios?
A mí me parece que la probabilidad de que un enunciado es demostrable y que es indecidible de la que tanto se apartó de 0, para cualquier distribución de probabilidad.
Deje $C_n$ ser el número gramatical de las declaraciones de longitud $n$. Para cualquier declaración de $S$, la declaración de
$S$ o $1=1$
es un teorema. Por lo que el número de comprobable declaraciones de longitud $n$ está acotado abajo por $C_{n-k}$ donde $k$ es el número de caracteres necesarios para la etiqueta de "o $1=1$".
Por otro lado, vamos a $G$ ser una sentencia indecidible, y $S$ cualquier frase. Entonces
Cualquiera de las $S$ $1 \neq 1$ o más $G$
es indecidible. Por lo que el número de indecidible frases de longitud $n$ está acotado abajo por $C_{n-\ell}$, para algunas constantes $\ell$. Para cualquier razonable de la gramática, de las relaciones de $C_{n-k}/C_n$ $C_{n- \ell}/C_n$ de la que tanto se apartó de 0.
Actualmente estoy tratando de averiguar por qué mi cálculo es aparentemente incompatible con el 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 tengo problemas para entender. Alguna ayuda?
Arda Xi
Puntos
1099
Actualización: en respuesta al comentario de abajo, no estoy seguro de que más de la probabilidad en cuestión fue de 0.
Vamos a intentar en la medida en que le da un peso igual para cualquier verdadero declaración de longitud fija $N$ (escrito en matemática inglés).
A continuación, tenemos las declaraciones de la forma "S o 1+2=3" que se forma, a continuación, $1/10^{20}$th de todos los enunciados verdaderos de una longitud dada. Por otro lado, las declaraciones "S y Z" (donde Z es un problema indecidible) formulario de algunos positivos (delimitada a continuación) medida subconjunto en las declaraciones de una longitud dada así.
Así que, sí, para la medida descrita por encima de la medida de comprobable declaraciones es dentro de algunos límites $[a, b]$ cualquier $N$ mayor que en el $N_0$.
Pero esa medida es proporcional, por un determinado $N$, a la función característica del conjunto de todos los enunciados verdaderos, así que, no, mi respuesta no dar un "natural" de la medida.
Creo que la probabilidad de "aleatorio verdad es demostrable" es 0 en cualquier buena formalización de su problema.
He aquí el razonamiento: considere la posibilidad de un verdadero indecidible declaración S. Ahora yo diría que en cualquier definición razonable de probabilidad de la larga declaración contendrá S con probabilitiy que va a 1 como aumenta su longitud. Uno no puede probarlo hasta que no hay una definición de esta probabilidad, pero los relacionados con el hecho de cuerdas es sencillo:
Considere la posibilidad de cualquier cadena
S. Entonces la probabilidad de a $P(n) := \{$la cadena aleatoria de la longitud de la $n$ contiene `S$\}$ 1 $n\to \infty$.
La prueba puede hacerse teniendo en cuenta el azar cadenas de la forma (fragmento 1)(fragmento 2)...(pedazo N), donde todos los fragmentos son de la misma longitud como S.
Nikos Steiakakis
Puntos
2651
Ilya tenía la idea correcta en su respuesta.
En primer lugar, la medida natural que se utiliza generalmente cuando se tiene un conjunto discreto de objetos, cada uno de algunos finito "complejidad" n, y con sólo un número finito de complejidad n, es considerar la probabilidad fija de n, y luego dejar que n ir hasta el infinito (cf. la teoría de Grafos Aleatorios).
En segundo lugar, la probabilidad de una verdadera declaración de longitud n ser comprobable, de hecho, tiende a 0 a medida que n tiende a infinito. Esto ha sido demostrado por Cristian Calude y Helmut Jürgensen (Adv Appl Matemáticas 35 (2005), 1-15).
Gracias a dios que nuestro trabajo no es demostrar al azar declaraciones!
Advertencia: esto es para el sonido y coherente de teorías en las cuales la aritmética de Peano puede ser formalizada.
Prasham
Puntos
146
Hay un número infinito de verdad comprobable teoremas en la PA y un número infinito de verdad no demostrable teoremas. Por lo que cualquier medida debe ir a cero para todos, pero un número finito de oraciones creo que hay un problema con el conocimiento de p en la que uno puede buscar en todos los menores ponderado de las penas y encontrar el porcentaje de sentencias, de modo que un punto puede ser alcanzado en donde algunas frases puede ser indecidible para hacer que la probabilidad de trabajar. Si este es el caso, entonces el conocimiento de la probabilidad haría algunas frases decidable por lo que la probabilidad no puede ser conocido, y de la prueba tendría que ser no-constructiva que existe lo que podría causar problemas con algunas filosofías de las matemáticas como intuitionism. Recuerdo una pregunta similar sobre las computadoras cuánticas en la cual la respuesta fue de 1/2.
He encontrado una referencia que dice que no hay que detener la probabilidad es computable. Si la prueba se podría hacer en un proceso que se realiza correctamente o nunca se detiene, a continuación, que proporcionan evidencia de que la probabilidad de un indecidible es el teorema de uncomputable
http://en.wikipedia.org/wiki/Chaitin%27s_constant#Interpretation_as_a_probability
