힐베르트의 열 번째 문제

힐베르트의 열 번째 문제는 1900년 독일 수학자 데이비드 힐베르트가 제기한 수학 문제 목록 중 열 번째 문제입니다. 주어진 디오판토스 방정식(정수 계수와 유한한 수의 미지수를 갖는 다항식)에 대해 방정식이 정수 값을 취하는 모든 미지수의 해를 갖는지 여부를 결정할 수 있는 일반적인 알고리즘을 제공하는 것이 과제입니다.

예를 들어, 디오판토스 $3x^{2}-2xy-y^{2}z-7=0$ $3x^{2}-2xy-y^{2}z-7=0$ $3x^{2}-2xy-y^{2}z-7=0$ 2 - $3x^{2}-2xy-y^{2}z-7=0$ $3x^{2}-2xy-y^{2}z-7=0$ - y $3x^{2}-2xy-y^{2}z-7=0$ - 7 = ${\$ displaystyle 3x^{ $2$ }-2xy-y $^{2}$ z-7= $0}$ 은 정수 해를 갖습니다: x = 1, y = 2, z = - 2 {\displaystyle x=1,\ y =2,\ z =-2}. 반면, 디오판토스 방정식 x 2 + 1 = 0 {\displaystyle x^{2}+y^{2}+1=0}은 그런 해가 없습니다.

힐베르트의 열 번째 문제는 해결되었고, 그런 일반적인 알고리즘은 존재할 수 없다는 부정적인 답을 가지고 있습니다. 이것은 마틴 데이비스, 유리 마티야세비치, 힐러리 퍼트넘, 줄리아 로빈슨이 21년에 걸쳐 작업한 결과이며, 마티야세비치는 1970년에 이 정리를 완성했습니다.^[1] 이 정리는 현재 Matiyasevich 정리 또는 MRDP 정리(해법의 주요 기여자 4명의 성에 대한 초기주의)로 알려져 있습니다.

$모든$ 계수와 변수가 양의 정수로 제한되면 다항식 동일성 테스트의 관련 문제는 때때로 ${\overline {HSI}}.$ ¯로 표시되는 타르스키의 고등학교 대수 문제의 결정적인(확장이 필요 없는) 변형이 됩니다. ${\displaystyle {\overline$ {HSI}}}

배경

원제

힐베르트는 이 문제를 다음과 같이 공식화했습니다.^[3]

알 수 없는 양이 얼마든지 있고 유리 적분 수치 계수가 있는 디오판토스 방정식이 주어지면: 유리 정수에서 방정식을 풀 수 있는지 여부를 유한 번의 연산에서 결정할 수 있는 프로세스를 고안합니다.

"과정"과 "무한한 수의 연산"이라는 단어는 힐베르트가 알고리즘을 요구했다는 의미로 받아들여졌습니다. '합리적 적분'이라는 용어는 단순히 정수, 양, 음, 또는 0을 의미합니다: 0, ±1, ±2, .... 그래서 힐베르트는 정수 계수를 가진 주어진 다항식 디오판토스 방정식이 정수에 해를 갖는지를 결정하기 위한 일반적인 알고리즘을 요구하고 있었습니다.

힐버트의 문제는 해결책을 찾는 것과 관련이 없습니다. 일반적으로 하나 이상의 솔루션이 존재하는지 여부를 결정할 수 있는지 여부만 묻습니다. 이 질문에 대한 답은 부정적입니다. 그 질문에 대한 답에 대한 "과정을 고안할 수 없다"는 의미에서 말입니다. 현대적으로 볼 때, 힐베르트의 열 번째 문제는 결정할 수 없는 문제입니다. 힐베르트가 그런 가능성을 생각했을 것 같지는 않지만, 문제들을 열거하기 전에 그는 정확하게 다음과 같이 말했습니다.^[4]

때때로 우리는 불충분한 가설이나 잘못된 의미에서 해결책을 찾는 경우가 있는데, 이러한 이유로 성공하지 못합니다. 그러면 문제가 발생합니다: 주어진 가설 하에서 또는 고려된 의미에서 해결책의 불가능성을 보여주는 것입니다.

10번째 문제가 결정 불가능하다는 것을 증명하는 것은 "해의 불가능성"에 대한 증명이기 때문에 힐베르트의 용어로도 유효한 답입니다.

디오판토스 집합

디오판토스 방정식에는 매개변수와 미지수의 두 종류의 변수가 있습니다. 디오판토스 집합은 디오판토스 방정식을 풀 수 있는 파라미터 할당으로 구성됩니다. 대표적인 예가 두 미지수에서의 선형 디오판토스 방정식입니다.

a_{1}x+a_{2}y=a_{3}

a_{1}x+a_{2}y=a_{3}

a_{1}x+a_{2}y=a_{3}

+

a_{1}x+a_{2}y=a_{3}

a_{1}x+a_{2}y=a_{3}

=

a_{1}x+a_{2}y=a_{3}

3 {\displaystyle a_{1}x+a_

a_{1}x+a_{2}y=a_{3}

2}y = a_{3}},

최대 공약수 $\gcd(a_{1},a_{2})$ 1 $\gcd(a_{1},a_{2})$ a $\gcd(a_{1},a_{2})$ {\ $displaystyle \gcd(a_{1}, a_{2)}$ 가 $a_{3}$ {\ $display a_{3}}$ 을 균등하게 $\gcd(a_{1},a_{2})$ 나누는 경우에만 방정식을 풀 수 있습니다 $a_{3}$ 이 제약을 만족하는 모든 순서 삼중 $(a_{1},a_{2},a_{3})$ 1 $(a_{1},a_{2},a_{3})$ $(a_{1},a_{2},a_{3})$ $(a_{1},a_{2},a_{3})$ a $(a_{1},a_{2},a_{3})$ $(a_{1}, a_{2}, a_{3}$ 집합을 $a_{1}x+a_{2}y=a_{3}$ x $a_{1}x+a_{2}y=a_{3}$ + $a_{1}x+a_{2}y=a_{3}$ $a_{1}x+a_{2}y=a_{3}$ y = $a_{1}x+a_{2}y=a_{3}$ ${\$ displaystyle a_{1}x+a_{2}y = a_{3}}로 정의되는 디오판토스 집합이라고 합니다. 이러한 용어에서, 힐베르트의 열 번째 문제는 임의의 다항식에 해당하는 디오판토스 집합이 비어 있지 않은지를 판단하는 알고리즘이 있는지를 묻습니다.

문제는 일반적으로 임의의 정수가 아닌 자연수(즉 음이 아닌 정수)의 관점에서 이해됩니다. 그러나 두 문제는 동등합니다. 주어진 디오판토스 방정식이 정수 해를 갖는지 여부를 결정할 수 있는 모든 일반적인 알고리즘은 주어진 디오판토스 방정식이 자연수 해를 갖는지 여부를 결정하는 알고리즘으로 수정될 수 있으며, 그 반대의 경우도 마찬가지입니다. 라그랑주의 4제곱 정리에 따르면 모든 자연수는 4개 정수의 제곱의 합이므로 4개의 새로운 정수 값 매개변수의 제곱의 합으로 모든 자연 값 매개변수를 다시 쓸 수 있습니다. 마찬가지로 모든 정수는 두 자연수의 차이이므로 모든 정수 파라미터를 두 자연수의 차이로 다시 쓸 수 있습니다.^[5] 또한 항상 동시 방정식 $p_{1}=0,\ldots ,p_{k}=0$ $p_{1}=0,\ldots ,p_{k}=0$ = 0 $…,$ p $k$ = $p_{1}^{\,2}+\cdots +p_{k}^{\,2}=0$ {\ $displaystyle$ $p_{1$ } = 0,\ldots, p_{k} = 0}(여기서 각 pi {\displaystyle p_{i}}는 다항식입니다)를 단일 방정식 p 12 + ⋯ + p k 2 = 0 {\displaystyle p_{1}^{\,2}+\cdots + p_{k}^{\,2} = 0으로 재작성할 수 있습니다.

재귀적으로 열거 가능한 집합

재귀적으로 열거 가능한 집합은 집합의 멤버가 입력으로 제공될 때 궁극적으로 중단되지만 입력이 비멤버인 경우 무한히 계속될 수 있는 알고리즘이 존재하는 것을 특징으로 할 수 있습니다. 알고리즘 계산 가능성의 직관적인 개념을 정확하게 설명하여 재귀적 열거 가능성의 개념을 완벽하게 엄격하게 만든 것은 계산 가능성 이론(재귀 이론이라고도 함)의 발전이었습니다. 디오판토스 집합은 재귀적으로 열거 가능하다는 것을 알 수 있습니다. 알 수 없는 값의 가능한 모든 튜플을 순서대로 정렬한 다음 주어진 매개 변수 값에 대해 이 튜플을 차례로 테스트하여 해당 방정식의 해인지 확인할 수 있기 때문입니다. 힐베르트의 열 번째 문제의 해결 불가능성은 그 반대가 참이라는 놀라운 사실의 결과입니다.

재귀적으로 열거할 수 있는 모든 집합은 디오판토스입니다.

이 결과는 마티야세비치의 정리(그가 증명을 완성하는 중요한 단계를 제공했기 때문에)와 MRDP 정리(유리 마티야세비치, 줄리아 로빈슨, 마틴 데이비스, 힐러리 퍼트넘)로 다양하게 알려져 있습니다. 계산할 수 없는 재귀적으로 열거 가능한 집합이 존재하기 때문에 힐베르트의 열 번째 문제의 해결 불가능성은 즉각적인 결과입니다. 사실 더 말할 수 있는 것은 다항식이 있다는 것입니다.

p(a,x_{1}},\ldots,x_{n})

방정식이 있는 $a$ $a$ 의 값 집합과 같은 정수 계수를 사용하여

p(a,x_{1},\ldots ,x_{n})=0

자연수로 된 솔루션은 계산할 수 없습니다. 따라서 디오판토스 방정식의 용해성을 테스트하는 일반적인 알고리즘이 없을 뿐만 아니라 이 하나의 매개변수 방정식군에 대해서도 알고리즘이 없습니다.

역사

연도	이벤트
1944	에밀 레온 포스트는 힐베르트의 열 번째 문제가 "해결 불가능성의 증명을 요구한다"고 선언합니다.
1949	마틴 데이비스(Martin Davis)는 재귀적으로 열거 가능한 집합에 대한 정규 형식을 얻기 위해 중국어 잔차 정리를 적용하는 커트 괴델(Kurt Gödel)의 방법을 코딩 트릭으로 사용합니다. $\left\{a\mid \exists y\forall k\leqslanty\exists x_{1},\ldots,x_{n}:p\left(a,k,y,x_{1},\ldots,x_{n}\right)=0\right\$ 여기서 $p$ $p$ 는 $p$ 정수 계수를 갖는 다항식입니다. 순수하게 형식적으로, 이것이 디오판토스 집합의 정의가 되는 것을 방해하는 것은 경계가 있는 보편적인 양자뿐입니다. 비건설적이지만 쉬운 증명을 사용하여, 그는 보완이 디오판토스가 아닌 디오판토스 집합이 존재한다는 것을 보여줌으로써 디오판토스 집합이 보완 하에 닫혀 있지 않다는 이 정규 형태의 상관 관계로 도출합니다. 재귀적으로 열거할 수 있는 집합도 보완 하에 닫혀 있지 않기 때문에, 그는 두 클래스가 동일하다고 추측합니다.
1950	Davis의 연구를 알지 못한 Julia Robinson은 지수 함수와 문제의 연관성을 조사하고, = $a=b^{c}$ $a=b^{c}$ ${\displaystyle$ a=b^{c}에 대한 세쌍원소 $(a,b,c)$ , $(a,b,c)$ {\ $displaystyle(a,$ b, $c)}$ 집합인 EXP가 디오판토스임을 증명하려고 시도합니다. 성공하지 못한 그녀는 다음과 같은 가설을 세웁니다(나중에 J.R.라고 불림). There is a Diophantine set $D$ of pairs $(a,b)$ such that $(a,b)\in D\Rightarrow b<a^{a}$ and for every positive $k,$ there exists $(a,b)\in D$ such that $b>a^{k}.$ $b>a^{k$ $}$ 그녀는 Pell 방정식의 속성을 사용하여 J.R.가 EXP가 디오판토스임을 암시하고 이항 계수, 요인 및 소수를 의미한다는 것을 증명합니다.
1959	Davis와 Putnam은 함께 지수 디오판토스 집합을 연구합니다. 지수 중 일부가 알려지지 않은 디오판토스 방정식으로 정의할 수 있는 집합입니다. Robinson의 방법과 함께 Davis 정규 형식을 사용하고, 소수로 구성된 임의로 긴 산술 진행이 있다는 당시 증명되지 않은 추측을 가정하면, 그들은 재귀적으로 열거할 수 있는 모든 집합이 지수 디오판토스임을 증명합니다. 그들은 또한 J.R.가 재귀적으로 열거할 수 있는 모든 집합이 디오판토스라는 것을 암시하고, 이는 다시 힐베르트의 열 번째 문제가 해결되지 않는다는 것을 암시한다는 것을 증명합니다.
1960	로빈슨은 지수 디오판토스 집합에 대한 조건부 결과의 증명을 단순화하고 소수에 대한 추측으로부터 독립시켜 공식 정리를 만듭니다. 이것은 J.R. 가설을 힐베르트의 열 번째 문제의 해결 불가능성에 대한 충분한 조건으로 만듭니다. 하지만, 많은 사람들은 J.R.가 사실인지 의심하고 있습니다.^[6]
1961–1969	이 기간 동안 데이비스와 퍼트넘은 J.R.를 암시하는 다양한 명제를 발견하고 로빈슨은 이전에 J.R.가 소수의 집합이 디오판토스 집합임을 암시한다는 것을 보여주었는데, 이것은 이것이 if and only 조건임을 증명합니다. 유리 마티야세비치는 힐베르트의 열 번째 문제를 몇 가지 축소하여 발표합니다.
1970	마티야세비치는 피보나치 수에 대한 니콜라이 보로베프의 최근 발표된 연구에서 Fn {\displaystyle F_{n}가 n개의 피보나치 수이고, 기하급수적인 성장을 나타내는 $P=\{(a,b)\|a>0,b=F_{2a}\},$ P = $a$ $,$ b) a > 0, b = F_{2a}\}임을 증명합니다. 이것은 그 때까지 20년 동안 미해결 질문이었던 J.R. 가설을 증명합니다. 재귀적으로 열거할 수 있는 모든 집합이 지수 디오판토스라는 정리와 J.R.를 결합하면 재귀적으로 열거할 수 있는 집합이 디오판토스라는 것을 증명할 수 있습니다. 이것은 힐베르트의 열 번째 문제를 해결할 수 없게 만듭니다.

적용들

Matiyasevich/MRDP 정리는 계산 가능성 이론의 두 가지 개념과 정수론의 두 가지 개념을 연관시키고 몇 가지 놀라운 결과를 가져옵니다. 아마도 가장 놀라운 것은 보편적인 디오판토스 방정식의 존재일 것입니다.

다항식이 존재합니다.

p(a,n,x_{1},\ldots ,x_{k})

따라서, 임의의 디오판토스 집합이 주어지면,

S

숫자가 있습니다.

n_{0}

그런 식으로

S=\{\,a\mid \exists x_{1},\ldots ,x_{k}[p(a,n_{0},x_{1},\ldots ,x_{k})=0]\,\}.

이것은 단순히 디오판토스 집합이 재귀적으로 열거할 수 있는 집합과 같기 때문에 튜링 기계와 같다는 것입니다. 모든 알고리즘을 실행할 수 있는 보편적인 튜링 기계가 존재한다는 것은 튜링 기계의 잘 알려진 특성입니다.

힐러리 퍼트넘은 양의 정수로 이루어진 $S$ 임의의 디오판토스 $집합$ S ${\displaystyle$ S $}$ 에 대하여, 다항식이 존재한다고 지적했습니다.

q(x_{0},x_{1},\ldots ,x_{n})

$S$ $S$ 가 변수로 $q$ $q$ $q$ 가 가정한 값 중 정확히 양수로 구성되도록 $S$ ,

x_{0},x_{1},\ldots,x_{n}

모든 자연수에 걸쳐 있습니다. 이는 다음과 같이 볼 수 있습니다.

p(a,y_{1},\ldots ,y_{n})=0

는 S{\ $displaystyle$ S $}$ 의 Diophantine 정의를 제공합니다 $S$ 그러면 설정하기에 충분합니다.

q(x_{0},x_{1},\ldots ,x_{n})=x_{0}[1-p(x_{0},x_{1},\ldots ,x_{n})^{2}].

따라서 예를 들어, 그 범위의 양수 부분이 정확히 소수인 다항식이 있습니다. (반면 어떤 다항식도 소수값만을 취할 수 없습니다.) 요인, 이항 계수, 피보나치 수 등과 같이 재귀적으로 열거 가능한 다른 자연수 집합에서도 동일한 값을 갖습니다.

다른 응용 프로그램은 논리학자들이 $\Pi _{1}^{0}$ π 10 ${\displaystyle \Pi_{$ 1}^{0} 명제라고 부르는 것에 관한 것으로, 때때로 골드바흐 유형의 명제라고도 합니다. 이것들은 모든 자연수가 각각의 특정한 수에 대해 알고리즘적으로 확인할 수 있는 특정한 성질을 가지고 있다는 골드바흐의 추측과 같습니다.^[10] 마티야세비치/MRDP 정리는 각 명제가 어떤 특정 디오판토스 방정식이 자연수에서 해가 없다고 주장하는 문장과 동일하다는 것을 의미합니다.^[11] 특히 페르마의 마지막 정리, 리만 가설, 사색 정리 등 중요하고 유명한 문제들이 많이 있습니다. 또한 Peano 산술이나 ZFC와 같은 특정 형식 체계가 일치한다는 주장은 $\Pi _{1}^{0}$ π $10 {\displaystyle \Pi$ _{1}^{0} 문장으로 표현할 수 있습니다. 이 아이디어는 증명을 나타내는 숫자라는 속성을 알고리즘적으로 확인할 수 있도록 자연수에 의한 증명을 코딩하는 커트 괴델을 따르는 것입니다.

$10$ {\displaystyle \Pi _{1}^{0}} 문장은 거짓일 경우, 그 사실이 일반적인 형식적 체계 중 어느 것에서도 증명될 수 있다는 특별한 특성을 가지고 있습니다. 그 위증은 단순한 산술로 검증할 수 있는 반례의 존재에 해당하기 때문입니다. 따라서 $\Pi _{1}^{0}$ π 10 ${\displaystyle \Pi$ _{1}^{0} 문장이 이러한 시스템 중 하나에서 증명될 수 없는 문장이라면 그 문장은 참이어야 합니다.

괴델의 불완전성 정리의 특히 두드러진 형태는 마티야세비치/MRDP 정리의 결과이기도 합니다.

허락하다
$p(a,x_{1},\ldots ,x_{k})=0$

계산 불가능 집합의 디오판토스 정의를 제공합니다. $A$ $A$ 를 $A$ 대응하는 $n$ $n$ 이되도록 $자연수$ n {\ $displaystyle$ n $}$ 의 시퀀스를 출력하는 알고리즘이라 하자.

$p(n,x_{1},\ldots ,x_{k})=0$

자연수로는 해결책이 없습니다. 그런 다음 $A$ 에서A {\ $displaystyle A}$ 가 $A$ 출력하지 않는 $n_{0}$ $n_{0}$ ${\$ 이 있습니다.

$p(n_{0},x_{1},\ldots ,x_{k})=0$
자연수로는 해결책이 없습니다.

정리가 참임을 확인하려면, 만약 $n_{0}$ ${\$ 이 없다면 $n_{0}$ 알고리즘 $A$ ${\displaystyle$ $A$ $}$ 를 동시에 실행하여 $A$ $n$ ${\displaystyle$ n $}$ 이 $n$ 출력되는지 확인하는 동시에 가능한 $모든$ k ${\displaystyle$ k $}$ - 해결책을 찾는 자연수의 쌍을 $k$ 확인하여 이 계산 불가능한 집합에서 $n$ $n$ ${\displaystyle$ n $}$ 의 멤버쉽을 알고리즘적으로 테스트할 수 있습니다. 등식의

p(n,x_{1},\ldots ,x_{k})=0

그리고 알고리즘 $A$ $A$ 를 $A$ 페아노 산술 또는 ZFC와 같은 일반적인 형식 시스템과 연결하여 공리의 결과를 체계적으로 생성한 다음 형식의 문장이 나올 때마다 $n$ $n$ $n$ 이라는 숫자를 출력할 수 있습니다.

\neg \exists x_{1},\ldots ,x_{k}[p(n,x_{1},\ldots ,x_{k})=0]

생성됩니다. 그런 다음 이 정리는 이 형식의 거짓 진술이 증명되거나 실제 진술이 문제의 시스템에서 증명되지 않은 채로 남아 있음을 알려줍니다.

추가결과

우리는 디오판토스 집합의 차수를 그 집합을 정의하는 방정식에서 다항식의 최소 차수라고 말할 수 있습니다. 마찬가지로, 우리는 정의식에서 그러한 집합의 차원을 가장 작은 미지수라고 부를 수 있습니다. 보편적인 디오판토스 방정식이 존재하기 때문에, 이 두 양 모두에 절대적인 상한이 있다는 것이 분명하고, 이 경계들을 결정하는 데 많은 관심이 있었습니다.

이미 1920년대에 토랄프 스콜렘은 디오판토스 방정식이 4도 이하 중 하나와 같다는 것을 보여주었습니다. 그의 방법은 새로운 미지수를 방정식으로 풀어내거나 두 미지수의 곱과 같게 하는 것이었습니다. 이 과정을 반복하면 2차 방정식 체계가 생성되고 제곱을 합하면 4차 방정식이 얻어집니다. 그래서 모든 디오판토스 집합은 사소하게 4도 이하입니다. 이 결과가 최선인지는 알 수 없습니다.

줄리아 로빈슨과 유리 마티야세비치는 모든 디오판토스 집합의 차원이 13보다 크지 않다는 것을 보여주었습니다. 나중에 마티야세비치는 9개의 미지수가 충분하다는 것을 보여주기 위해 그들의 방법을 갈고 닦았습니다. 이 결과가 가능한 최선이 아닐 수도 있지만, 더 이상의 진전은 없었습니다.^[12] 그래서 특히 9 이하의 미지수를 가진 디오판토스 방정식을 자연수로 풀어내는 알고리즘이 없습니다. 유리 정수 해의 경우(힐버트가 원래 제안했던 것처럼), 4제곱 트릭은 36개 이하의 미지수를 갖는 방정식에 대한 알고리즘이 없음을 보여줍니다. 하지만 Zhi Wei Sun은 11개 이하의 미지수를 가진 방정식에서도 정수 문제가 해결되지 않는다는 것을 보여주었습니다.

마틴 데이비스(Martin Davis)는 디오판토스 방정식의 해의 수를 포함하는 알고리즘 질문을 연구했습니다. 힐베르트의 열 번째 문제는 그 숫자가 0인지 아닌지를 묻습니다. $A=\{0,1,2,3,\ldots ,\aleph _{0}\}$ = $A=\{0,1,2,3,\ldots ,\aleph _{0}\}$ { $A=\{0,1,2,3,\ldots ,\aleph _{0}\}$ 1, 2, 3, …,ℵ 0 } {\ $displaystyle$ A =\{0, 1, 2, 3,\ldots,\aleph _{0}\}라고 하고 C {\displaystyle C}를 A {\displaystyle A}의 적절한 비어 있지 않은 부분 집합이라고 합니다. 데이비스는 주어진 디오판토스 방정식을 시험하여 해의 $C$ 가 집합C {\ $displaystyle$ C $}$ 의 원소인지 여부를 결정하는 알고리즘이 없음을 증명했습니다 $C$ 따라서 디오판토스 방정식의 해의 개수가 유한한지, 홀수인지, 완전 제곱인지, 소수인지 등을 결정하는 알고리즘이 없습니다.

MRDP 정리의 증명은 Coq에서 공식화되었습니다.^[13]