1 votos

¿Es el PA+ TM doesnt halts consistente?

Supongamos que no hay una prueba en PA de si alguna TM se detiene o no.
Supongamos además que TM no se detiene y que PA es consistente. ¿Es necesario que PA+TM se detenga?
¿Es el paro de PA+TM necesariamente consistente?

1voto

Wojowu Puntos 6491

Supongamos que $PA$ es consistente.

Supongamos que $PA+S$ , donde $S$ es cualquier declaración, es inconsistente. Entonces $PA+S$ prueba $0=1$ . Esto significa que $PA$ solo demuestra $S\Rightarrow 0=1$ Así que $PA$ muestra que una afirmación falsa se desprende de $S$ Así que $S$ debe ser falso. Por lo tanto, $PA$ prueba $\neg S$ .

Por contraposición, si $PA$ hace no mostrar $\neg S$ entonces $PA+S$ es consistente. Aplique esto a $S$ siendo "TM se detiene" y "TM no se detiene" para conseguir que sea consistente que, respectivamente, TM no se detenga y que se detenga.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X