La confusione in Turings prova dell'indecidibilità dell'Entscheidungsproblem

Question

stavo leggendo L'articolo di Turing sui numeri computabili e l'Entscheidungsproblem.C'è questa parte della Sezione 9, Parte II che non riesco a capire del tutto.Lui dice:

È piuttosto semplice fino alla parte in cui presenta $\mathfrak{U}$.COSÌ $\mathfrak{U}$, dice, include gli assiomi di Peano;ma cos'altro comprende?Immagino che includa gli assiomi per $G(x)$ così, perché solo allora lo farebbe $\mathfrak{U}$ essere in grado di "definire" la sequenza $\alfa$ che viene calcolato da $G(x)$.Qui prendo la parola "definire" nel suo senso abituale, ma Turing spiega cosa intende con "$\mathfrak{U}$ definendo $\alfa$" COME:

Così per $\mathfrak{U}$ definire $\alfa$, $-\mathfrak{U}$ dovere non essere dimostrabile?Non sono sicuro del motivo per cui è richiesto?Perché limitandolo $-\mathfrak{U}$ non deve essere dimostrabile, lo stiamo dicendo $\mathfrak{U}$ dovere non essere confutabile, il che significa che la sequenza $\alfa$ non può essere tutti 0 (o almeno così penso).Ma perché dovremmo volerlo $\alfa$ per non essere tutti 0?

Sono anche confuso riguardo alle due formule ($A_n$ E $B_n$) ha scritto sopra.Non sono sicuro del motivo per cui ha incluso il file $F^{(n)}$ parte.Se $x$ soddisfa gli assiomi di Peano e gli assiomi di $G(x)$, Poi $U$ essere una concezione di tutti questi assiomi è dato per essere VERO, e se $x$ non soddisfa quindi questi assiomi $\mathfrak{U}$ è ovviamente FALSO.Quindi, basandomi solo su $\mathfrak{U}$ possiamo dire se $A_n$ È VERO O $B_n$.Allora qual è il punto $F^{(n)}$ Qui?Penso che la seguente serie di implicazioni dica più o meno la stessa cosa di ciò che ha Turing?

Scusate se sto trascurando qualcosa qui.

Modifica 1:

Ecco le note a piè di pagina:

Answer 1

La traslitterazione del brano in lingua moderna sarebbe la seguente.

Estendiamo il linguaggio dell'aritmetica di Peano del primo ordine con un predicato unario $G$ (e nessun assioma per $G$).Per un numero $n \in \mathbb{N}$, permettere $\sopra{n}$ essere il numero$$\underbrace{S(S(\cdots S}_{n}(0)))$$Dove $S$ è il simbolo successivo.Per esempio, $\sopralinea{3} = S(S(S(0))$.

Consideriamo una formula $\mathfrak{U}(x)$ scritto in questa lingua, la cui unica variabile libera è $x$ tale che, per ogni $n \in \mathbb{N}$:

1. Gli assiomi di Peano lo dimostrano $\mathfrak{U}(\overline{n}) ightarrow G(\overline{n})$, O
2. Gli assiomi di Peano lo dimostrano $\mathfrak{U}(\overline{n}) ightarrow \lnot G(\overline{n})$.
3. Gli assiomi di Peano lo fanno non dimostrare $\lnon \mathfrak{U}(\overline{n})$.

Definire $\alfa:\mathbb{N} o \{0,1\}$ di$$\alpha(n) = \begin{casi} 1 & ext{se gli assiomi di Peano dimostrano $\mathfrak{U}(\overline{n}) ightarrow G(\overline{n})$},\\ 0 & ext{if gli assiomi di Peano dimostrano $\mathfrak{U}(\overline{n}) ightarrow \lnot G(\overline{n})$.} \end{casi} $$Lo diciamo $\mathfrak{U}$ definisce la sequenza $\alfa$.

Intuitivamente, pensiamo $G(x)$ come affermando "il $x$-esima cifra di $\alfa$ È $1$", e di $\lnon G(x)$ come affermando "il $x$-esime cifre di $\alfa$ È $0$".

La prima e la seconda condizione sono attive $\mathfrak{U}$ assicurarsi che $\mathfrak{U}$ assegna sempre $\alfa(n)$ il valore $0$ o il valore $1$.

La terza condizione lo garantisce $\mathfrak{U}$ non assegna mai Entrambi $0$ E $1$ A $\alfa(n)$ (perché dalle prime due condizioni segue che $\lnon \mathfrak{U}(\overline{n})$ è equiparabile con $G(\overline{n}) \land \lnot G(\overline{n})$).

Esempio: La formula $G(x)$ definisce la sequenza $1, 1, 1, 1, 1, \ldots$.

Esempio: La formula $G(S(x))$ non definisce una sequenza perché $G(S(0)))$ non implica $G(0)$ e non implica $\lnon G(0)$.(Ricordati che $G$ è un simbolo primitivo e non abbiamo assiomi al riguardo.)

Esempio: La formula $G(0) \land \forall x \,.\, \lnot G(S(x))$ definisce la sequenza $1, 0, 0, 0, 0, \ldots$

Esempio: La formula $x eq 0 \land ightarrow G(x)$ non definisce la sequenza perché lo dimostrano gli assiomi di Peano $\lnot (0 eq 0 \land G(0)$, quindi la terza condizione è violata.Se provassimo a utilizzare questa formula per definire una sequenza, assegnerebbe $0$ E $1$ A $\alfa(0)$ (e assegnerebbe $1$ a tutti gli altri termini di $\alfa$).

Esempio: La formula $G(0) \land \lnot G(S(0)) \land \forall x .G(S(S(x)))$ definisce la sequenza $1, 0, 1, 1, 1, 1, \ldots$

Esempio: La formula$$((\esiste y .X = 2 CDOT Y) RightRow G (x)) Land (( esiste y.x = S(2 \cdot y)) \Freccia destra \lnot G(x)) $$definisce la sequenza $0, 1, 0, 1, 0, 1, \ldots$