에 혼란 Turings 의 증거 undecidability 의 Entscheidungsproblem

Question

내가 읽기 튜링의 종이에 계산할 수있는 숫자와 Entscheidungsproblem.가의이 부분은 섹션 9,파트 II 할 수 없는 아주는 것을 이해합니다.그는 말합니다:

그것은 바로 앞으로까지 그 소개 $\mathfrak{U}$.그래서 $\mathfrak{U}$, 말 포함되어 있 페아노 공리;하지만 그것은 다른 무엇이 포함되어 있습니까?나는 그것을 포함한 공리에 대한 $G(x)$ 뿐만 아니라,때문에만 다음 $\mathfrak{U}$ 할 수 있을 정의합니다""순서 $\alpha$ 되는 계산 $G(x)$.나는 단어"정의하는"여기에서 그것의 일반적인 의미하지만,튜링은 무엇인지 설명하는 의미로"$\mathfrak{U}$ 정의 $\alpha$"as:

그래서 $\mathfrak{U}$ 정의 $\alpha$, $-\mathfrak{U}$ 야 지 야에 오면 저렴하지 않습니다.나는 확실하지 않는 왜 필요한가?기 때문에 제한하여는 $-\mathfrak{U}$ 해야 하지 않을 증명할 수 있는 우리가 말하고 있는 $\mathfrak{U}$ 야 지 수 refutable,는 것을 의미하는 순서 $\alpha$ 할 수 없 모든 0s(또는 그래서 나는 생각한다).그런데 왜 우리가 원하는 $\alpha$ 하지 않는 모든 0 니까?

저도 혼란에 대한 두 개의 공식($A_n$ 고 $B_n$)그가 그 위의 기록됩니다.자가 공유하는 경우 포함하고있다 $F^{(n)}$ 부분입니다.는 경우 $x$ 맞 페아노 공리와의 공리 $G(x)$, 다음 $U$ 인 conjection 의 이러한 모든 원칙에게 주어진할 TRUE, 면 $x$ 을 만족하지 않는 이러한 원칙이 다음 $\mathfrak{U}$ 분명 FALSE.그래서 그냥 기반 $\mathfrak{U}$ 우리가 말할 수 있는지 여부를 $A_n$ 가 TRUE 나 $B_n$.그래서 어떤 시점 $F^{(n)}$ 까요?나는 생각한 다음 설정의 의미를 말한 거의 동일한 것으로 무엇 튜링은?

죄송하는 경우 나는 내가 여기 있다.

편집 1:

여기에 각주:

Answer 1

의 음역을 통과으로 현대적인 언어 갈 것으로 다음과 같습니다.

우리는 확장하는 언어의 순서 페아노산과 단항 조건자 $G$ (그리고 공리에 대한 $G$).수 $n\\에서 mathbb{N}$, 자 $\overline{n}$ 다 숫자 $$\underbrace{S(S(\cdots S}_{n}(0)))$$ 가 $S$ 은 후계자 상징입니다.예를 들어, $\overline{3}=S(S(S(0))$.

을 고려한 수식 $\mathfrak{U}(x)$ 쓰이는 언어,그에만 변수를 무료 $x$ 는 것과 같은 모든 $n\\에서 mathbb{N}$:

1. 페아노 공리 증명 $\mathfrak{U}(\overline{n}) ightarrow G(\overline{n})$, 나
2. 페아노 공리 증명 $\mathfrak{U}(\overline{n}) ightarrow\lnot G(\overline{n})$.
3. 페아노 공리지 지 증명 $\lnot\mathfrak{U}(\overline{n})$.

정의 $\alpha:\mathbb{N} o\{0,1\}$ by $$\alpha(n)= \시작하느니라 1& ext{경우 페아노 공리 증명$\mathfrak{U}(\overline{n}) ightarrow G(\overline{n})$},\\ 0& ext{경우 페아노 공리 증명$\mathfrak{U}(\overline{n}) ightarrow\lnot G(\overline{n})$.} \끝느니라 $$ 우리가 말 $\mathfrak{U}$ 정의 시퀀스 $\alpha$.

직관적으로,우리는 우리의 생각 $G(x)$ 로는"이 $x$번째 숫자의 $\alpha$ 가 $1$"고 $\lnot G(x)$ 로는"이 $x$번째 숫자의 $\alpha$ 가 $0$".

첫 번째와 두 번째에서 조건 $\mathfrak{U}$ 는지 확인 $\mathfrak{U}$ 항상 할당 $\alpha(n)$ 값 $0$ 거나 값 $1$.

세 번째 조건 보장 $\mathfrak{U}$ 지 않 할당 모두 $0$ 고 $1$ 하기 $\alpha(n)$ (기 때문에 그것이 다음과 같이에서 첫 번째는 두 가지 조건 $\lnot\mathfrak{U}(\overline{n})$ 은 equiprovable 과 $G(\overline{n})\땅\lnot G(\overline{n})$).

예제: 식 $G(x)$ 정의 시퀀스 $1, 1, 1, 1, 1, \ldots$.

예제: 식 $G(S(x))$ 를 정의하지 않기 때문에 순서 $G(S(0)))$ 의미하지는 않습 $G(0)$ 고 그것이 의미하지는 않습 $\lnot G(0)$.(는 것을 기억 $G$ 은 원시인 기호와는 우리가 원칙에 대해니다.)

예제: 식 $G(0)\땅\forall x\,.\, \lnot G(S(x))$ 정의 시퀀스 $1, 0, 0, 0, 0, \ldots$

예제: 식 $x eq0\땅 ightarrow G(x)$ 하지 않는 순서를 정의하기 때문에 페아노 공리 증명 $\lnot(0 eq0\땅 G(0)$, 따라서 세 번째 조건을 위반했습니다.만약 우리가 사용하려고 이 수식을 정의 시퀀스에서,그것은 할당 $0$ 고 $1$ 하기 $\alpha(0)$ (및 할당 $1$ 다른 모든 약관 $\alpha$).

예제: 식 $G(0)\땅\lnot G(S(0))\땅\forall x.G(S(S(x)))$ 정의 시퀀스 $1, 0, 1, 1, 1, 1, \ldots$

예제: 식 $$((\존재 y.x=2\cdot y) ightarrow G(x))\땅 ((\존재 y.x=S(2\cdot y)) ightarrow\lnot G(x)) $$ 정의 시퀀스 $0, 1, 0, 1, 0, 1, \ldots$