불해독성 문제

Undecidable problem

계산가능성 이론과 계산 복잡성 이론에서, 해석할 수 없는 문제는 항상 정확한 예-아니오 답으로 이어지는 알고리즘을 구성하는 것이 불가능하다는 것이 증명된 의사결정 문제다. 중단 문제는 예를 들어, 임의 프로그램이 실행될 때 결국 중단되는지 여부를 정확하게 결정하는 알고리즘이 없다는 것을 증명할 수 있다.

배경

의사결정 문제는 무한정 입력 집합에 대한 임의의 예, 아니오 질문이다. 이 때문에, 결정 문제를 문제가 "예"로 반환하는 입력값 집합으로 동등하게 정의하는 것이 전통적이다. 이러한 입력은 자연스러운 숫자일 수 있지만, 형식 언어의 문자열과 같은 다른 종류의 값도 될 수 있다. 괴델 번호 부여와 같은 일부 인코딩을 사용하면 문자열을 자연 숫자로 인코딩할 수 있다. 따라서, 공식 언어의 측면에서 비공식적으로 표현되는 의사결정 문제는 또한 자연수 집합과 동등하다. 형식적인 정의를 단순하게 유지하기 위해, 그것은 자연수의 하위 집합의 관점에서 표현된다.

공식적으로, 의사결정 문제는 자연수의 하위 집합이다. 해당 비공식적인 문제는 주어진 숫자가 집합에 있는지 여부를 결정하는 것이다. 의사결정 문제 A는 재귀적 집합이고 달리 해석할 수 없는 집합이면 해독 가능하거나 효과적으로 해결할 수 있다고 한다. A가 재귀적으로 열거할 수 있는 집합인 경우 문제를 부분적으로 결정하거나, 반 결정하거나, 해결할 수 있거나, 증명할 수 있다고 한다.[1]

예제: 계산가능성 이론의 중지 문제

연산성 이론에서 중단 문제는 다음과 같이 말할 수 있는 의사결정 문제다.

임의의 프로그램과 한정된 입력에 대한 설명을 고려하여 프로그램이 실행을 완료하는지 또는 영구적으로 실행될 것인지를 결정한다.

앨런 튜링은 1936년에 가능한 모든 프로그램 입력 쌍의 중지 문제를 해결하는 튜링 기계에서 실행되는 일반 알고리즘은 반드시 존재할 수 없다는 것을 증명했다. 따라서, 중지 문제는 튜링 기계에 대해 이해할 수 없는 것이다.

괴델의 불완전성 정리와의 관계

괴델의 불완전성 이론에 의해 제기되는 개념은 정지 문제에 의해 제기되는 개념과 매우 유사하며, 그 증명들은 상당히 유사하다. 사실 제1차 불완전성 정리의 약한 형태는 중단 문제의 불찰의 쉬운 결과물이다. 이 약한 형태는 완전성과 음성을 겸비한 자연수의 공리화가 불가능하다고 주장함으로써 불완전성 정리의 표준적 진술과 다르다. "건전한" 부분은 약하다는 것이다: 그것은 우리가 자연수에 대한 진실된 진술만을 증명하기 위해 문제의 자명적인 시스템을 요구한다는 것을 의미한다. 건전성은 일관성을 내포하고 있기 때문에 이 약한 형태는 강한 형태의 골격으로 볼 수 있다. 괴델의 제1차 불완전성 정리 표준형식의 진술은 진술의 진가에 전혀 무관심하지만, 수학적 증거를 통해 그것을 찾아낼 수 있는가에 대한 문제만을 염려하는 것이 중요하다.

정리의 약한 형태는 다음과 같은 중지 문제의 불분명함에서 증명할 수 있다. 우리가 건전한(따라서 일관성이 있다고) 가정하고 자연수에 대한 모든 진정한 1차 논리 진술의 완전한 공리화를 가정해보자. 그러면 우리는 이 모든 문장을 열거하는 알고리즘을 만들 수 있다. 즉, 자연수 n이 주어진 경우 자연수에 대한 진정한 1차 논리문을 계산하는 알고리즘 N(n)이 있고, 모든 참 문장에 대해 N(n)이 그러한 문장을 산출하는 알고리즘 N(n)이 적어도 하나 있다는 것을 의미한다. 이제 표현 알고리즘이 입력 i에서 정지되는지 여부를 결정하려고 한다. 우리는 이 진술이 1차 논리 진술로 표현될 수 있다는 것을 알고 있다, 라고 H(a, i)라고 말한다. 공리화가 완료되었으므로 N(n) = H(a, i) 또는 N(n) = H(a, i) = such H(a, i)와 같은 n'이 있는 것으로 뒤따른다. 그래서 만약 우리가 H(a, i)나 그것의 부정을 발견할 때까지 모든 n을 반복한다면, 우리는 항상 멈출 것이고, 나아가 그것이 우리에게 주는 답은 진실일 것이다(건전성에 의해). 이것은 우리에게 중단 문제를 결정할 알고리즘을 제공한다는 것을 의미한다. 우리는 그러한 알고리즘이 있을 수 없다는 것을 알고 있기 때문에, 자연수에 관한 모든 참된 1차 논리 문장의 일관되고 완전한 공리화가 있다는 가정은 반드시 거짓이어야 한다는 것을 따른다.

인식할 수 없는 문제의 예

주요 기사: 해결되지 않는 문제 목록

해석하기 어려운 문제는 논리, 추상적인 기계 또는 위상과 같은 다른 주제와 관련될 수 있다. 헤아릴 수 없을 정도로 많은 미해결 문제들이 있기 때문에,[2] 어떤 목록도, 심지어 무한대의 한 가지라도, 반드시 불완전하다.

해석할 수 없는 문장의 예

참고 항목: ZFC 및 독립성과 무관한 문장 목록(수학적 논리)

현대 용어로 "결정할 수 없는"이라는 단어의 두 가지 뚜렷한 감각이 있다. 이 중 첫 번째는 괴델의 이론과 관련하여 사용된 감각으로, 특정 연역 체계에서 증명할 수 없거나 반박할 수 없는 진술이다. 두 번째 감각은 계산가능성 이론과 관련하여 사용되며 진술이 아닌 결정 문제에 적용되며, 이것은 각각 예스 또는 무응답이 필요한 무한 질의 집합이다. 이러한 문제는 문제 집합의 모든 질문에 정확하게 답하는 계산 가능한 기능이 없는 경우 불문하다고 한다. 이 두 가지 사이의 연관성은 의사결정 문제가 (재귀 이론적 의미에서) 불분명할 경우, 문제의 모든 질문 A에 대해 "A에 대한 답은 예" 또는 "A에 대한 답은 아니오"를 증명하는 일관되고 효과적인 공식 시스템이 없다는 것이다.

해석할 수 없는 단어의 두 가지 의미 때문에, "증명이 불가능하거나 반박할 수 없는" 의미 대신에 독립된 용어를 사용하는 경우가 있다. 그러나 '독립'의 사용법도 모호하다. 그것은 단지 "증거할 수 없다"는 의미일 수 있고, 독립된 진술이 반박될 수 있는지 여부는 공개적이다.

특정 연역체계에서 진술의 불신성은 그 자체로 진술의 진가가 잘 정의되어 있는지, 아니면 다른 수단으로 판단될 수 있는지에 대한 문제를 다루지 않는다. 불신임이란 고려되고 있는 특정 연역체계가 진술의 진실이나 거짓을 증명하지 못한다는 것을 의미할 뿐이다. 진실의 가치를 결코 알 수 없거나 잘못 명시되어 있는 이른바 '절대 불답' 진술이 존재하는지는 여러 철학계 학교들 사이에서 논란이 되고 있는 대목이다.

이 용어의 두 번째 의미에서는, 이해할 수 없는 것으로 의심되는 첫 번째 문제들 중 하나는, 1911년 막스 딘에 의해 처음으로 제기된 집단들의 문제였는데, 이 단어들은 두 단어가 등가인지 여부를 결정하기 위한 알고리즘이 존재하지 않는 정밀하게 제시된 집단이 있는지를 묻는 것이었다. 1952년 이 경우로 나타났다.

괴델과 폴 코헨의 결합작품은 불변의 진술의 두 가지 구체적인 예를 제시하였다(이 용어의 첫 뜻에서). 연속 가설은 ZFC(세트 이론의 표준 공리화)에서 증명되거나 반박될 수 없으며, 선택의 공리는 ZF(선택의 공리를 제외한 모든 ZFC 공리)에서 증명되거나 반박될 수 없다. 이러한 결과는 불완전성 정리를 필요로 하지 않는다. 괴델은 1940년에 이러한 진술들 중 어느 것도 ZF나 ZFC 세트 이론에서 반증될 수 없다는 것을 증명했다. 1960년대에 코헨은 어느 것도 ZF로부터 증명할 수 없으며, 연속 가설은 ZFC로부터 증명할 수 없다는 것을 증명했다.

1970년, 러시아의 수학자 유리 마티야세비치는 1900년에 다음 세기의 수학자들에 대한 도전으로 제기된 힐베르트의 열 번째 문제는 해결될 수 없다는 것을 보여주었다. 힐버트의 도전은 디오판틴 방정식의 모든 해결책을 찾는 알고리즘을 찾았다. 디오판틴 방정식은 페르마의 마지막 정리의 더 일반적인 경우로서, 우리는 정수 계수를 가진 모든 수의 변수에서 다항식의 정수 뿌리를 찾는다. 우리는 하나의 방정식을 가지고 있을 뿐 변수는 없기 때문에, 복잡한 평면에 무한히 많은 해법이 존재하며(그리고 찾기 쉽다) 그러나, 해법이 정수값으로만 구속된다면 문제는 불가능해진다. 마티야세비치는 디오판틴 방정식을 재귀적으로 열거할 수 없는 집합에 매핑하고 괴델의 불완전성 정리를 호출함으로써 이 문제를 해결할 수 없음을 보여주었다.[3]

1936년에 앨런 튜링은 중단되는 문제, 즉 튜링 기계가 특정 프로그램에서 정지하는지의 여부에 대한 질문이 이 용어의 두 번째 의미에서는 불분명하다는 것을 증명했다. 이 결과는 나중에 라이스의 정리하에 일반화되었다.

1973년, 사하론 셀라는 그룹 이론에서 화이트헤드 문제는 표준 집합 이론에서, 첫 번째 의미에서, 이해할 수 없는 것임을 보여주었다.[4]

1977년 파리와 해링턴은 램지 정리의 한 버전인 파리-해링턴 원리가 페이노 공리가 주는 산수의 공리화에서는 판독할 수 없지만 2차 산수의 더 큰 체계에서는 사실임을 증명할 수 있다는 것을 증명했다.

컴퓨터 공학에 응용이 있는 크러스칼의 트리 정리도 페이노 공리에서는 해독할 수 없지만 세트 이론에서는 증명할 수 있다. 사실 크루스칼의 트리 정리(또는 그것의 유한 형태)는 선험주의라고 불리는 수학철학에 기초하여 받아들일 수 있는 원리를 훨씬 더 강한 체계에서 해독할 수 없는 것이다.

굿스타인의 정리는 키르비와 파리가 피아노 산술에서 판독 불가해한 자연수의 램지 이론에 대한 진술이다.

그레고리 차이틴은 알고리즘 정보 이론에서 이해할 수 없는 진술을 만들어 냈고 그 설정에서 또 다른 불완전성 정리를 증명했다. 차이틴의 정리는 충분한 산수를 나타낼 수 있는 어떤 이론에 대해서도 그 이론에서 콜모고로프 복잡성이 c보다 크다는 것을 증명할 수 없는 상한이 c가 존재한다고 명시하고 있다. 괴델의 정리는 거짓말쟁이 역설과 관련이 있지만 차이틴의 결과는 베리의 역설과 관련이 있다.

2007년, 1970년대 J.H.콘웨이의 초기 연구를 바탕으로 한 연구자 커츠와 사이먼은 콜라츠 문제의 자연적인 일반화는 이해할 수 없는 것임을 증명했다.[5]

참고 항목

참조

  1. ^ 이것은 답이 '예'일 때 결국 중단되지만 '아니오'일 경우 영원히 실행될 수 있는 알고리즘이 존재한다는 것을 의미한다.
  2. ^ } 의 하위 집합은 셀 수 없이 많으며 이들 중 대부분은 알고리즘에 의해 결정될 수 있다. 그러나, 또한 모든 언어로만 결정 문제가 명시될 수 있다.
  3. ^ Matiyasevich, Yuri (1970). Диофантовость перечислимых множеств [Enumerable sets are Diophantine]. Doklady Akademii Nauk SSSR (in Russian). 191: 279–282.
  4. ^ Shelah, Saharon (1974). "Infinite Abelian groups, Whitehead problem and some constructions". Israel Journal of Mathematics. 18 (3): 243–256. doi:10.1007/BF02757281. MR 0357114.
  5. ^ 커츠, 스튜어트 A; 2007년 5월 중국 상하이에서 열린 제4차 연산모델의 이론과 응용에 관한 국제회의의 진행에서 사이먼, 야노스, "일반화된 콜라츠 문제의 불문율" ISBN 3-540-72503-2. doi:10.1007/978-3-540-72504-6_49