불가능성증명

Proof of impossibility

수학에서 불가능성의 증명은 특정 문제가 청구항에 설명된 것처럼 해결될 수 없거나 특정 문제 집합이 일반적으로 해결될 수 없음을 보여주는 증명입니다.이러한 경우를 의 증명, 불가능성 정리의 증명 또는 음의 결과라고도 합니다.불가능하다는 증거는 종종 해결책을 찾기 위해 수십 년 또는 수백 년 동안 노력한 결과, 결국 해결책이 없다는 것을 증명하는 것입니다.어떤 것이 불가능하다는 것을 증명하는 것은 보통 반대의 과제보다 훨씬 어렵습니다. 왜냐하면, 단지 특정한 [1]예를 보여주는 것이 아니라, 일반적으로 효과가 있는 증명을 개발하는 것이 종종 필요하기 때문입니다.불가능성 정리는 일반적으로 논리학에서 부정적인 존재 명제 또는 보편적인 명제로 표현할 수 있습니다.

2의 제곱근의 비합리성은 불가능성의 가장 오래된 증거 중 하나입니다.2의 제곱근을 두 정수비율로 표현하는 것은 불가능함을 보여줍니다.불가능성에 대한 또 다른 결과적인 증거는 1882년 페르디난트 린데만의 증명인데, 이 증명은 숫자 ρ초월적이기 때문에 (즉, 대수적이지 않은) 원을 제곱하는 문제는 해결될[2] 수 없으며, 대수적 숫자의 부분집합만이 나침반과 직선으로 구성될 수 있다는 것을 보여주었습니다. 다른 두 가지 고전적인 문제들인 일반각비틀고 정육면체를 두 배로 늘리는 것은 19세기에 불가능한 것으로 증명되었고, 이 모든 문제들은 더 복잡한 수학적 구조에 대한 연구를 야기시켰습니다.

16세기에 발생한 문제는 고정된 k의 다항식의 해를 표현하기 위해 라디칼을 사용하는 일반적인 공식을 만드는 이었다. 1820년대에 아벨-루피니 정리(아벨의 불가능성 정리라고도 알려진)는 이것이 [3]불가능하다는 것을 보여주었고,추상대수학의 새로운 하위 분야인 갈루아 이론의 풀이 가능한 군과 같은 개념을 사용합니다.

20세기에 발견된 불가능성의 가장 중요한 증거들 중 일부는 결정 불가능성과 관련된 것들이었는데, 는 어떤 알고리즘으로도 일반적으로 해결할 수 없는 문제들이 있다는 것을 보여주었고, 그 중 가장 두드러진 것 중 하나는 중단 문제입니다.Gödel의 불완전성 정리는 형식적인 [4]시스템의 가능성에 있어서 근본적인 한계를 발견한 다른 예들이었습니다.

계산 복잡도 이론에서 상대화(오라클의 추가)와 같은 기술은 상대화에 영향을 받지 않는 증명 기술은 P NP [5]문제를 해결할 수 없다는 점에서 불가능성에 대한 "약한" 증명을 허용합니다. 다른 기법은 복잡성 수업에 대한 완전성의 증명으로, 수업에서 다른 문제들만큼 풀기 어렵다는 것을 보여줌으로써 문제의 난이도에 대한 증거를 제공합니다.특히, 완전한 문제는 반에서 발생하는 문제 중 하나라면 다루기 힘든 문제입니다.

증명의 종류

모순으로

불가능성 증명의 일반적인 유형 중 하나는 모순에 의한 증명입니다.이러한 유형의 증명에서 특정 종류의 방정식에 대한 해와 같은 명제가 성립한다고 가정하면, 공제를 통해 짝수와 홀수 또는 음수와 양수 모두와 같이 서로 상반되는 두 가지를 나타낼 수 있음을 알 수 있습니다.그 모순은 원래의 가정에서 비롯되기 때문에, 이것은 가정된 가정이 불가능해야 한다는 것을 의미합니다.

혈통별

모순에 의한 또 다른 증명 유형은 하강에 의한 증명으로, 어떤 것이 가능하다고 가정함으로써 먼저 진행되며, 예를 들어 방정식의 양의 정수[6] 해와 같이 가장 작은 해가 있어야 합니다(웰-오더링 원리에 의한).가장 작은 솔루션이라고 주장되는 것으로부터, 이전 솔루션이 가능한 가장 작은 솔루션이라는 전제와 모순되어, 솔루션이 존재한다는 원래의 전제가 거짓이어야 한다는 것을 보여줍니다.

반증 유형

무언가 불가능하다는 추측을 반증하는 두 가지 대안적인 방법이 있습니다: 반례(건설적 증명)와 논리적 모순(비건설적 증명).

불가능한 추측을 반증하는 명백한 방법은 단 하나의 반례를 제공하는 것입니다.예를 들어 오일러는 또 다른th n개의 거듭제곱을 합하기 위해서는 적어도 n개의 다른th 거듭제곱이 필요하다고 제안했습니다.이 추측은 1966년에 반증되었는데, 단지 4개의 다른 5개의 거듭제곱의 수를 다른 5개의 거듭제곱으로 합하는 반례를 포함합니다.

275 + 845 + 1105 + 1335 = 1445.

반례에 의한 증명은 주장을 반증하는 물건이 전시된다는 점에서 건설적인 증명의 한 형태입니다.반대로, 불가능한 주장에 대한 비건설적인 증거는 모든 가능한 반례가 무효라는 을 논리적으로 모순된다는 것을 보여줌으로써 진행될 것입니다. 가능한 반례 목록에 있는 항목 중 적어도 하나는 실제로 불가능한 추측에 대한 유효한 반례여야 합니다.예를 들어, 비합리적인 힘을 비합리적인 힘으로 끌어올리는 것이 불가능하다는 추측은 두 가지 가능한 반례 중 하나가 반드시 유효한 반례가 되어야 한다는 것을 보여줌으로써 그것이 어느 것인지를 보여줌으로써 반증되었습니다.

무리수의 존재에 대한 피타고라스의 증거.

피타고라스가 기원전 500년경에 증명한 것은 수학에 지대한 영향을 미쳤습니다.이것은 2의 제곱근을 두 정수의 비율로 표현할 수 없음을 보여줍니다.증명은 "숫자"를 두 개의 겹치지 않는 집합, 즉 유리수무리수로 분리했습니다.이 분기는 칸토어그의 대각선 방법에 사용한 것인데, 튜링은 힐베르트결정 문제인 엔츠샤이둥 문제가 결정할 수 없다는 것을 증명하는 데 사용했습니다.

"피타고라스의 정리"가 언제, 또는 누구에 의해 발견되었는지는 알려져 있지 않습니다.그 발견은 피타고라스 자신에 의해서는 거의 이루어질 수 없었지만, 확실히 그의 학교에서 이루어졌습니다.피타고라스는 기원전 570년에서 490년 정도 살았습니다.기원전 470년경에 태어난 데모크리토스는 비이성적인 선과 견고함에 대해...

Heath,[citation needed]

17개까지의 소수점들의 다양한 제곱근들에 대한 증명들이 뒤따랐습니다.

플라톤의 Theaetetus에는 Theodorus(플라톤의 스승)가 비합리성을 증명했다는 유명한 구절이 있습니다.

각각 다른 케이스들을 17평방 피트의 뿌리까지 끌어올리는 것...[7]

보다 일반적인 증거는 다음과 같습니다.

N정수 n"[8]의 m번째 거듭제곱이 아닌 한 정수 N의 m번째 뿌리는 비이성적입니다.

즉, 정수 N의 m번째 루트를 비율로 표현하는 것은 불가능합니다.b = 1인 경우를 제외하고 공통 소인수를 공유하지 않는 두 정수 a와 b의 ab.

고대 그리스인들이 추구했던 불가능한 건축물.

그리스 기하학의 세 가지 유명한 질문은 다음과 같습니다.

  1. 나침반과 직선을 이용해서 어떤 각도라도 분할할 수 있습니다.
  2. 주어진 정육면체의 부피의 두 배의 부피를 갖는 정육면체를 구성하기 위하여,
  3. 주어진 원의 면적과 동일한 넓이의 정사각형을 구성합니다.

2,000년 이상 동안 이러한 문제를 해결하기 위한 시도는 성공적이지 않았습니다. 마침내 19세기에 원하는 구성이 논리적으로 [9]불가능하다는 것이 증명되었습니다.

고대 그리스인들의 네 번째 문제는 그들이 어떻게 구성해야 하는지 알고 있는 기본적인 경우 n = 3, 4, 5, 6을 넘어 지정된 수의 n개의 변을 가진 정다각형을 구성하는 것이었습니다.

이 모든 것은 유클리드 구성의 문제이며, 유클리드 구성은 유클리드 숫자만을 포함하는 경우에만 수행할 수 있습니다([10]후자의 정의에 의해).무리수는 유클리드일 수 있습니다.좋은 예로 2의 제곱근(비합리적인 수)이 있습니다.다리가 모두 한 단위인 직각 삼각형의 빗변 길이이며, 직선형의 가장자리와 나침반으로 구성할 수 있습니다.그러나 유클리드 수는 덧셈, 뺄셈, 곱셈, 나눗셈, 제곱근의 추출 이외의 어떤 연산도 포함할 수 없다는 것이 유클리드 수 세기 후에 증명되었습니다.

각도 분할 및 큐브 2배 증가

일반 각도를 3으로 하는 것과 정육면체를 2배로 하는 것 모두는 나침반과 직선으로 구성할 수 없는 숫자인 정육면체 근을 취해야 합니다.

원의 사각형

{\ \pi(는) 유클리드 수가 아니므로 단위 지름의 원둘레와[11] 같은 길이를 유클리드 방법으로 구성하는 것은 합니다.

유클리드 수가 대수적 수임을 증명할 수 있는 증명이 존재합니다. 즉, 어떤 다항식의 해가 되는 수입니다.따라서 π 는 1882년에 초월수임이 증명되었기 때문에, 대수적인 수가 아닌 정의상 유클리드 수가 아닙니다.따라서 단위 원에서 {\(를) 구성할 [12]수 없으며 원을 제곱할 수 없습니다.

등변 n-곤 구성

가우스-완첼 정리는 1837년에 n의 대부분의 값에 대하여 등변 n-곤을 구성하는 것이 불가능하다는 것을 보여주었습니다.

유클리드 평행 공준

유클리드의 원소들의 평행 공준은 직선과 그 선 위에 있지 않은 점이 주어지면 그 점을 통해 그 선과 평행한 하나만 그려질 수 있다는 과 같습니다.다른 가설들과 달리, 그것은 덜 자명하게 여겨졌습니다.Nagel과 Newman은 이것이 공준이 "무한히 먼" 공간 영역에 관한 것이기 때문일 수 있다고 주장합니다. 특히 평행선은 [13]점근선과는 대조적으로 "무한대"에서도 만나지 않는 것으로 정의됩니다.이러한 인식된 자기 증거 부족은 다른 유클리드 공리와 가설로부터 증명될 수 있는지에 대한 질문으로 이어졌습니다.가우스, 볼라이, 로바체프스키, 리만의 작품에서 다른 것들로부터 평행 공준을 추론하는 것의 불가능성이 증명된 것은 19세기의 일이었습니다.이 연구들은 평행 공준이 대안으로 대체될 수 있다는 것을 보여주었고, 이는 비유클리드 기하학으로 이어졌습니다.

나겔과 뉴먼은 평행선 추론에 의해 제기된 질문을 "... 아마도 이후 수학 [13]역사에 대한 그것의 장기적인 영향에서 가장 중요한 발전"이라고 생각합니다.특히, 그들은 그 결과를 "[이 경우, 평행 공준] 특정 명제를 [[이 경우, 유클리드의 첫 번째 네 개의 공준]][14] 시스템 내에서 증명하는 것이 불가능하다는 증거를 제공할 수 있다"고 보여주었듯이, "가장 지적으로 중요한" 것으로 간주합니다.

페르마의 마지막 정리

페르마의 마지막 정리는 1600년대에 피에르 드 페르마에 의해 되었으며 > x n + y n=z n{\ x + } = 양의 정수에서 해를 찾는 것의 불가능성을 말합니다. 페르마 자신은 무한 강하 기술과 다른 특수한 경우들을 사용하여 n = 4인 경우에 대한 증명을 했습니다.나중에 증명되었지만 일반적인 경우는 1994년 앤드류 와일스에 의해 증명되지 않았습니다.

리처드의 역설

1905년에 리차드에 의해 제시된 이 심오한 역설은 쿠르트[15] 괴델과 알란 튜링의 업적을 알려주었습니다.간결한 정의는 Principia [16]Mathematica에서 찾을 수 있습니다.

리처드의 역설은 다음과 같습니다.한정수의 단어를 사용하여 정의할 수 있는 모든 소수점을 생각해 보십시오. ["단어"는 기호이고 강조를 위해 굵은 글씨가 추가됩니다.] E를 그러한 소수점의 클래스라고 가정합니다. 다음 E는 ℵ{\0무한수] 항을 가지므로, 그 구성원은 1, 2, 3, ...로 주문할 수 있습니다.X를 다음과 같이 정의된 수라고 하자 [Whitehead & Russell은 이제 Cantor 대각선 방법을 사용합니다.
n번째 소수에서 n번째 숫자가 p이면 X의 n번째 숫자를 p + 1(또는 p = 9인 경우 0)이라고 합니다.그렇다면 X는 E의 모든 구성원과 다르며, 유한한 값 n이 무엇이든 X의 n번째 도형은 E를 구성하는 소수점의 n번째 도형과 다르므로 X는 n번째 소수점과 다릅니다.그럼에도 불구하고 우리는 X를 한정된 수의 단어로 정의했습니다. [즉, 위의 "단어"의 바로정의.] 따라서 X는 E의 멤버여야 합니다.따라서 X는 모두 E의 멤버이며 E의 멤버가 아닙니다.

Principia Mathematica, 2nd edition 1927, p. 61

쿠르트 괴델은 그의 증명을 리처드의 역설의 "유사한 것"이라고 여겼고, 그는 이를 "리처드의 반유대성"[17]이라고 불렀습니다. (아래 참조).

앨런 튜링은 이 역설을 기계로 구성하고 이 기계가 간단한 질문에 답할 수 없다는 것을 증명했습니다: 이 기계는 어떤 기계가 (자신을 포함하여) 비생산적인 '무한 루프'에 갇히게 될지(즉, 대각선 숫자의 계산을 계속하지 못하는지).

공리계의 불완전성: 괴델의 증명

Nagel과 Newman의 말을 인용하자면, "Gödel의 논문은 어렵습니다.46개의 예비 정의와 몇 가지 중요한 예비 정의를 모두 숙지한 후에 주요 결과에 도달해야 합니다."사실, Nagel과 Newman은 그들의 증명에 대한 67페이지의 소개를 요구했습니다.그러나 독자가 논문을 다룰 만큼 충분히 강력하다고 느낀다면, 마틴 데이비스는 "이 놀라운 논문은 지적 랜드마크일 뿐만 아니라 읽기에 즐거움을 줄 정도로 명료하고 활기차게 쓰여졌다"고 관찰합니다(Davis in Undecision, p. 4).대부분의 독자들은 나겔과 뉴먼을 먼저 보는 것이 좋습니다[by whom?].

괴델은 자신의 말로 다음과 같이 증명했습니다.

"당연한 일입니다...…이라는 추측을 하다[[the]] 공리 [[Principia Mathematica and Peano]]는 주어진 체계에서 공식적으로 표현될 수 있는 모든 수학 문제를 결정하기에 충분합니다.다음의 내용을 보면 이것은 사실이 아니라 오히려 ...라는 것을 알 수 있을 것입니다.공리에 기초하여 결정될 수 없는 일반적인 정수 이론의 비교적 간단한 문제들이 존재합니다(Gödel in Undecision, p. 4).

괴델은 그의 증명을 "리처드의 안티노미"("Antinomy"는 모순 또는 역설이다.)와 비교했습니다.

"리처드의 반대론과 이 결과의 유사성은 즉시 명백합니다. 거짓말쟁이 역설과도 밀접한 관련이 있습니다 [14] (괴델의 각주 14: 모든 인식론적 반대론은 결정 불가능성에 대한 유사한 증거를 위해 사용될 수 있습니다) ...따라서, 우리는 자신의 입증 불가능성을 주장하는 제안을 우리 앞에 두고 있습니다 [15].(그의 각주 15: 그러한 명제는 겉보기와는 달리 순환론적이지 않으며, 우선은 매우 확실한 공식의 증명 불가능성을 주장하기 때문입니다.)"[17]

문제 중지:튜링의 최초 증명

  • 결정 문제인 엔체이둥 문제는 1935년 4월 교회에 의해 처음으로 답을 받았고 1936년 [18]5월 튜링의 논문이 출판을 위해 접수되면서 튜링보다 1년 이상 앞섰습니다.
  • 튜링의 증명은 필요한 정의의 수와 미묘한 성격 때문에 어려워집니다.자세한 내용은 튜링 기계와 튜링의 증명참조하세요.
  • 튜링의 첫 번째 증명은 리처드의 역설의 도식을 따릅니다.튜링의 컴퓨팅 머신은 "컴퓨팅 머신"에서 일곱 글자의 문자열로 표현되는 알고리즘입니다.그 "계산"은 모든 컴퓨팅 머신(자체 포함)에 대해 "원"을 테스트하고, 비원형 또는 "성공적인" 컴퓨팅 머신의 계산으로부터 대각선 숫자를 형성하는 것입니다.이것은 1부터 순서대로 숫자(베이스 8)를 테스트할 7개의 문자로 구성된 문자열로 변환하여 수행합니다.자신의 번호에 도달하면 자신의 문자 문자열을 만듭니다.이것은 성공적인 기계의 문자 문자열이라고 결정하지만, 이 기계의 (자체) 계산을 하려고 하면 원형으로 잠겨서 계속할 수 없습니다.따라서 리처드의 역설에 도달한 것입니다. (만약 당신이 어리둥절하다면 튜링의 증명을 참고하세요.)

튜링의 증명 전후에 많은 유사한 결정 불가능성 증명들이 나타났습니다.

  1. 1935년 4월: 알론조 교회의 증명("초수론의 풀 수 없는 문제")그의 증명은 "...효과적인 계산 가능성의 정의를 제안하고... 예를 들어 이 클래스의 모든 문제를 해결할 수 있는 것은 아니라는 것을 보여주는 것"이었습니다(결정할 수 없는 페이지 90).
  2. 1946: 통신 후 문제 (cf Hopcroft and Ullman[19] p. 193ff, p. 407 참조)
  3. 1947년 4월: 에밀 포스트의 증명 (화의 문제의 재발적 해결 불가능) (결정할 수 없는 페이지 293).이것은 이후 "화의 단어 문제" 또는 "화의 단어 문제"로 알려지게 되었습니다(Axel Thue는 1914년의 논문에서 이 문제를 제안했습니다(cf References to the Post in Undecision, p. 303).
  4. 라이스의 정리: 튜링의 두 번째 정리의 일반화된 공식 (cf Hopcroft and Ullman[19] p. 185ff)[20]
  5. 그리바흐의 정리: 언어 이론의 결정 불가능성(cf Hopcroft and Ullman[19] p. 205ff 및 p. 401 ibid 참조:Greibach [1963] "최소 선형 문법에 대한 모호성 문제의 결정 불가능성", 정보와 통제 6:2, 117–125, 또한 페이지 402 ibid:Greibach [1968] "형식 언어의 결정할 수 없는 특성에 대한 주석", 수학 체계 이론 2:1, 1-6.)
  6. 펜로즈 타일링 질문.
  7. 디오판토스 방정식에 대한 해의 문제와 MRDP 정리의 결과 답을 참조하십시오. 아래 항목을 참조하십시오.

문자열 압축성:차이틴 증명

비전문가에게 적합한 박람회는 Beltrami p. 108ff를 참조하십시오.프란젠 챕터 8 페이지 137-148, 데이비스 페이지 263-266 참조.프란젠의 논의는 Beltrami의 논의보다 훨씬 더 복잡하며, Ⅲ-Gregory Chaitin의 소위 "중단 확률"을 자세히 다룹니다.데이비스의 오래된 치료법은 튜링 기계의 관점에서 질문에 접근합니다.차이틴은 그의 노력과 그로 인한 철학적, 수학적 여파에 관한 많은 책을 썼습니다.

문자열을 더 짧은 컴퓨터 프로그램에서 생성할 수 없는 경우에는 (알고리즘적으로) 랜덤이라고 합니다.대부분의 문자열은 랜덤이지만, 많은 짧은 문자열을 제외하고는 특정 문자열을 증명할 수 없습니다.

"차이틴의 결과를 의역하면 충분히 긴 끈이 임의적이라는 공식적인 증거는 있을 수 없다는 것입니다.."[21]

벨트라미는 "차이틴의 증명은 20세기 초 옥스퍼드 사서 G. 베리가 '1000자 미만의 영어 문장으로 정의할 수 없는 가장 작은 양의 정수'를 요구하는 역설과 관련이 있다"고 지적합니다.분명히 이 숫자의 가장 짧은 정의는 1000자 이상이어야 합니다.그러나 인용문 안의 문장은 그 자체로 주장되는 숫자의 정의로 1000자 미만입니다!"[22]

디오판토스 방정식의 정수해:힐베르트의 열 번째 문제

임의의 디오판토스 방정식이 정수해를 가지고 있는가라는 질문은 결정할 수 없습니다.즉, 모든 경우에 대해 질문에 답하는 것은 불가능합니다.

프란젠은 힐베르트의 열 번째 문제와 "디오판토스 방정식이 어떤 해를 갖는지 결정할 수 있는 알고리즘이 존재하지 않는다"는 MRDP 정리를 소개합니다.MRDP는 튜링의 결정 불가능성 증명을 사용합니다. "... 풀이 가능한 디오판토스 방정식의 집합은 계산할 수 있지만 결정할 수 없는 집합의 예이며, 풀이 불가능한 디오판토스 방정식의 집합은 계산할 [23]수 없습니다."

사회과학에서

정치학에서 애로우의 불가능 정리는 특정한 다섯 개의 공리의 집합을 만족시키는 투표 시스템을 고안하는 것은 불가능하다는 것을 말합니다.이 정리는 네 개의 공리가 함께 다섯 번째 공리의 반대를 암시한다는 것을 보여줌으로써 증명됩니다.

마찬가지로, Gibbard-Satterthwaite 정리는 어떤 투표 시스템도 두 가지 이상의 대안을 가질 수 없으며, 전략적 투표에 강하며 한 명의 유권자가 결과를 결정하는 것을 막을 수 없다고 말합니다.

경제학에서 홀름스트룀의 정리는 대리인 팀에 대한 어떤 인센티브 시스템도 세 가지 바람직한 기준을 모두 만족시킬 수 없다는 것을 증명하는 불가능한 정리입니다.

자연과학에서

자연과학에서 불가능한 주장은 (다른 주장과 마찬가지로) 도전할 수 없을 정도로 증명되기 보다는 압도적으로 가능성이 높은 것으로 널리 받아들여지게 됩니다.이 강력한 수용의 근거는 어떤 일이 일어나지 않는다는 광범위한 증거와 기본 이론이 결합되어 있고, 예측을 하는데 매우 성공적이며, 그 가정은 논리적으로 어떤 일이 불가능하다는 결론으로 이어집니다.

물리학에서 널리 받아들여지는 불가능성의 두 가지 예는 에너지 보존 법칙을 위반하는 영구 운동 기계와 특수 상대성 이론의 의미를 위반하는 빛의 속도를 초과하는 입니다.다른 하나는 입자의 위치와 운동량을 동시에 아는 것이 불가능하다는 양자역학불확정성 원리입니다.벨의 정리도 있습니다: 국소 숨은 변수에 대한 물리적 이론은 양자역학의 모든 예측을 결코 재현할 수 없다는 것입니다.

자연과학에서 불가능한 주장은 절대적으로 증명될 수 없지만, 단 하나의 반례의 관찰로 반박될 수 있습니다.그러한 반례는 불가능성을 암시하는 이론의 기초가 되는 가정을 다시 검토할 것을 요구합니다.

참고 항목

참고 및 참고 자료

  1. ^ 푸들라크, 255-256쪽.
  2. ^ Weisstein, Eric W. "Circle Squaring". mathworld.wolfram.com. Retrieved 2019-12-13.
  3. ^ Weisstein, Eric W. "Abel's Impossibility Theorem". mathworld.wolfram.com. Retrieved 2019-12-13.
  4. ^ Raatikainen, Panu (2018), "Gödel's Incompleteness Theorems", in Zalta, Edward N. (ed.), The Stanford Encyclopedia of Philosophy (Fall 2018 ed.), Metaphysics Research Lab, Stanford University, retrieved 2019-12-13
  5. ^ Baker, Theodore; Gill, John; Solovay, Robert (1975). "Relativizations of the P=?NP Question". SIAM Journal on Computing. 4 (4): 431–442. doi:10.1137/0204037. Retrieved 2022-12-11.
  6. ^ 일반적으로, 무한 강하에 의한 증명은 순서가 잘 잡힌 모든 집합에 적용될 수 있습니다.
  7. ^ 하디와 라이트, 페이지 42
  8. ^ 하디와 라이트, 페이지 40
  9. ^ 나겔과 뉴먼 p. 8
  10. ^ 하디와 라이트 159쪽
  11. ^ 하디와 라이트 p. 176
  12. ^ Hardy and Wright p. 159 E 참조.헤케 (1923).볼레성겐 위베르 다이 이론 대수학 잘렌.라이프치히:아카데미시 베를라그스게샤프트
  13. ^ a b Nagel and Newman, p.
  14. ^ Nagel and Newman, 페이지 10
  15. ^ Nagel, Ernest; Newman, James R. (1958). Gödel's proof. pp. 60 ff. ISBN 0-359-07926-1. OCLC 1057623639.
  16. ^ Principia Mathematica, 1927년 2판, p. 61, 64 in Principia Mathematica online, Vol.1 in Michigan 대학 역사수학 모음집
  17. ^ a b 결정할 수 없는 괴델, 9쪽
  18. ^ 1936년 (튜링보다 늦은 10월) 에밀 포스트가 튜링의 컴퓨팅 머신 모델과 매우 유사한 간단한 머신과 같은 "방법"으로 알고리즘을 축소하는 것에 대해 논의한 짧은 논문도 출판을 위해 받았습니다 (자세한 내용은 포스트-튜링 머신 참조).
  19. ^ a b c John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-X.
  20. ^ "...M [임의 기계]가 주어진 기호를 출력하는지 여부를 결정할 기계 E는 존재할 수 없습니다(0 say)"(결정할 수 없는 페이지 134).튜링은 이 증명의 마지막 부분에서 라이스의 정리와 매우 유사한 기묘한 주장을 합니다.
    "...이러한 각각의 "일반적인 과정" 문제는 주어진 정수 n이 G(n)의 성질을 갖는지를 결정하는 일반적인 과정에 관한 문제로 표현될 수 있습니다...그리고 이는 G(n)이 참이면 n번째 수치가 1이고 거짓이면 0인 수를 계산하는 것과 동등합니다(미결정 p134).유감스럽게도 그는 요점을 더 분명히 밝히지 않아 독자들은 혼란에 빠졌습니다.
  21. ^ 벨트라미 p. 109
  22. ^ Beltrami, 페이지 108
  23. ^ 프란젠 p.71

서지학

  • G. H. HardyE. M. Wright, 정수론 입문, 제5판, Clarendon Press, Oxford England, 1979, General Index(초판: 1938)와 함께 2000년 재인쇄.e와 pi가 초월적이라는 증거는 사소한 것이 아니라, 수학적으로 능숙한 독자는 그것들을 헤쳐나갈 수 있을 것입니다.
  • Alfred North Whitehead and Bertrand Russell, Principia Mathematica to *56, Cambridge at the University Press, 1962, 1927년 2판 재인쇄, 1913년 초판.제2장 I. "악순환의 원리" p. 37ff, 그리고 제2장VIII. "모순" p. 60ff.
  • Turing, A.M. (1936), "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, 2 (published 1937), vol. 42, no. 1, pp. 230–65, doi:10.1112/plms/s2-42.1.230, S2CID 73712 (그리고 . 온라인 버전 이것은 튜링이 튜링 기계를 정의하고 그것이 (Entscheidungs 문제뿐만 아니라) 해결할 수 없다는 것을 보여주는 획기적인 논문입니다.
  • 마틴 데이비스, 결정할 수 없는 제안, 해결할 수 없는 문제와 계산 가능한 함수에 관한 기초 논문, 레이븐 프레스, 뉴욕, 1965.튜링의 논문은 이 권에서 #3입니다.고델, 처치, 로서, 클린, 포스트의 논문들이 있습니다.
  • 마틴 데이비스의 장 "계산이란 무엇인가" 린 아서 스틴의 수학 투데이, 1978, 빈티지 북스 에디션, 뉴욕, 1980.그의 장은 튜링 기계를 더 간단한 포스트 튜링 기계의 용어로 설명한 다음 튜링의 첫 번째 증명과 차이틴의 기여에 대한 설명으로 진행합니다.
  • 앤드류 호지스, 앨런 튜링: 에니그마, 사이먼 앤 슈스터, 뉴욕.Cf 챕터 "진실의 정신" 그의 증명에 이르는 역사와 토론을 위한 것.
  • 한스 라이헨바흐, 상징 논리학의 요소들, 도버 출판사, 뉴욕, 1947다른 저자들이 자주 인용하는 참고 자료.
  • 어니스트 나겔제임스 뉴먼, 괴델의 증명, 뉴욕 대학 출판부, 1958.
  • 에드워드 벨트라미, 랜덤이란? 수학과 삶의 기회와 질서, Springer-Verlag New York, Inc., 1999.
  • Torkel Franzén, Godel's Theorem, 그 사용과 남용에 대한 불완전한 안내서, A.K. Peters, Wellsley Mass, 2005괴델의 정리와 그 남용에 대한 최근의 분석.작가가 믿는 것처럼 간단한 읽기는 아닙니다.용어를 명확히 하려는 프란젠(Franzén)의 시도 때문에 튜링의 세 번째 증명에 대한 논의는 유용합니다.고델의 정리를 사용하는 프리먼 다이슨, 스티븐 호킹, 로저 펜로즈, 그레고리 차이틴의 주장에 대한 토론과 그가 웹에서 발견한 철학적이고 형이상학적인 고델에서 영감을 받은 드렉에 대한 유용한 비판을 제공합니다.
  • 파벨 푸들라크, 수학과 계산 복잡도의 논리적 기초. 부드러운 소개, 스프링거 2013. (4장 "불가능의 증거" 참조)