계산가능성이론

Computability theory

계산 가능성 이론(Computability theory)은 1930년대에 계산 가능한 함수와 튜링 학위에 대한 연구로 시작된 수학적 논리학, 컴퓨터 과학, 계산 이론의 한 분야입니다.이 분야는 이후 일반화된 계산 가능성과 정의 가능성에 대한 연구로 확장되었습니다.이러한 영역에서 계산 가능성 이론은 증명 이론효과적인 설명 집합 이론과 중복됩니다.

계산 가능성 이론에서 다루는 기본 질문은 다음과 같습니다.

  • 자연수함수가 계산 가능하다는 것은 무엇을 의미합니까?
  • 계산 불가능한 함수는 어떻게 계산 불가능성 수준에 따라 계층으로 분류될 수 있습니까?

비록 지식과 방법 면에서 상당한 중복이 있지만, 수학적 계산 가능성 이론가들은 상대적 계산 가능성, 축소 가능성 개념, 그리고 정도 구조에 대한 이론을 연구합니다; 컴퓨터 과학 분야의 사람들은 하위 순환 계층, 형식적 방법, 그리고 형식 언어에 대한 이론에 집중합니다.

서론

n 2 3 4 5 6 7 ...
σ(n) 4 6 13 4098 ? > 3.5x1018267 > 1010101018705353 ?
비지 비버 함수 σ(n)이 계산 가능한 함수보다 더 빨리 증가하는 것으로 나타나지 않습니다.
따라서 계산할 수 없습니다.[1] 몇 가지 값만 알려져 있습니다.

계산 가능성 이론은 1930년대에 쿠르트 괴델, 알론조 교회, 로자 페터, 알란 튜링, 스티븐 클린, 에밀 포스트의 연구로 시작되었습니다.[2][nb 1]

연구자들이 얻은 기본적인 결과는 튜링 계산 능력을 효과적인 계산이라는 비공식적인 아이디어의 올바른 공식화로 확립했습니다.1952년, 클라인은 "교회의 논문"[3]: 300 과 "튜링의 논문"이라는 두 가지 이름을 만들었습니다.[3]: 376 오늘날 이것들은 종종 하나의 가설로 간주되는데, 이것은 알고리즘에 의해 계산 가능한 함수는 계산 가능한 함수라는 것입니다.처음에는 회의적이었지만 1946년 괴델은 이 논문을 지지했습니다.[4]: 84

"타르스키는 강의에서 일반 재귀성(또는 튜링의 계산 가능성) 개념의 중요성을 강조했습니다.이 중요성은 이 개념으로 처음으로 흥미로운 인식론적 개념, 즉 선택된 형식주의에 의존하지 않는 절대적 개념을 제공하는 데 성공했기 때문인 것 같습니다."[4]: 84 [5]

효과적인 계산의 정의와 함께 수학에는 효과적으로 결정할 수 없는 문제가 있다는 첫 번째 증거가 나왔습니다.1936년, 처치와[6][7] 튜링은[8] 괴델이 그의 불완전성 정리를 증명하기 위해 사용한 기술에 영감을 받았습니다 - 1931년, 괴델은 독립적으로 Entscheidungs 문제가 효과적으로 결정할 수 없다는 것을 증명했습니다.이 결과는 임의의 수학적 명제가 참인지 거짓인지를 정확하게 판단할 수 있는 알고리즘 절차가 없다는 것을 보여주었습니다.

수학의 많은 문제들은 이러한 초기 사례들이 확립된 후 결정할 수 없는 것으로 나타났습니다.1947년, 마코프와 포스트는 세미그룹의 단어 문제가 효과적으로 결정될 수 없다는 것을 보여주는 독립적인 논문을 발표했습니다. 결과를 확장하면서 표트르 노비코프와 윌리엄 분은 1950년대에 집단에 대한 단어 문제가 효과적으로 해결될 수 없다는 것을 독립적으로 보여주었습니다: 유한하게 제시된 집단에 주어진 단어가 그 단어로 표현되는 요소가 그 집단의 정체성 요소인지를 결정하는 효과적인 절차는 없습니다.1970년, 유리 마티야세비치는 (줄리아 로빈슨의 결과를 이용하여) 힐베르트의 번째 문제가 효과적인 해를 갖지 않는다는 것을 암시하는 마티야세비치의 정리를 증명했습니다. 이 문제는 정수 위에 디오판토스 방정식이 정수 안에 해를 갖는지 결정하는 효과적인 절차가 있는지 물었습니다.결정할 수 없는 문제의 목록은 계산 가능한 해결책이 없는 문제의 추가적인 예를 제공합니다.

수학적 구성을 효과적으로 수행할 수 있는 연구를 때때로 재귀 수학이라고 합니다. 재귀 수학[9] 핸드북에서는 이 분야에서 알려진 많은 결과를 다룹니다.

튜링 연산성

계산 가능성 이론에서 연구된 계산 가능성의 주요 형태는 1936년 튜링에 의해 소개되었습니다.[8]자연수 집합은 n주어진 튜링 기계가 n이 집합에 있으면 출력 1로 정지하고 n이 집합에 없으면 출력 0으로 정지하는 계산 가능 집합(결정 가능, 재귀적 또는 튜링 계산 가능 집합이라고도 함)이라고 합니다.자연수에서 자연수로 가는 함수 f는 (튜링) 계산 가능한 함수이며, 입력 n에서 출력 f(n)를 중단하고 반환하는 튜링 기계가 있는 경우 재귀 함수입니다.여기서 튜링 기계의 사용은 필요하지 않습니다. 튜링 기계와 동일한 계산 능력을 가진 다른 많은 모델이 있습니다. 예를 들어 원시 재귀 및 μ 연산자에서 얻은 μ-재귀 함수입니다.

계산 가능한 함수와 집합에 대한 용어는 완전히 표준화되어 있지 않습니다.Gödel에 의한 재커시브 함수의 다른 정의뿐만 아니라 μ-재귀 함수의 관점에서의 정의는 튜링 기계에 의해 계산될 수 있는 집합과 함수에 대한 전통적인 이름 재커시브로 이어졌습니다.결정할 수 있는 단어는 튜링과 다른 사람들의 원래 논문에서 사용되었던 독일어 Entscheidungs 문제에서 비롯되었습니다.현대의 사용에서 "계산 가능 함수"라는 용어는 다양한 정의를 가지고 있습니다: 나이젤 J. 커틀랜드에 따르면,[10] 그것은 부분 재귀 함수이고 반면 로버트 I에 따르면. 총 재귀적(동일하게 일반 재귀적) 함수인 것도 마찬가지입니다[11].이 글은 이 협약의 두 번째 내용을 따릅니다.1996년에 소어는[12] 용어에 대해 추가적인 언급을 했습니다.

모든 자연수 집합이 계산 가능한 것은 아닙니다.입력 0에서 정지하는 튜링 기계의 집합인 정지 문제는 계산할 수 없는 집합의 잘 알려진 예입니다.계산할 수 없는 많은 집합이 존재한다는 것은 튜링 기계가 셀 수 있을 정도로 많고, 따라서 계산할 수 있는 집합이 셀 수 없을 정도로 많다는 사실에서 따온 것이지만, 칸토어의 정리에 따르면 자연수의 집합은 셀 수 없이 많습니다.

정지 문제는 계산이 불가능하지만, 프로그램 실행을 시뮬레이션하고 정지하는 프로그램의 무한한 목록을 생성하는 것이 가능합니다.따라서 중단 문제는 튜링 기계에 의해 열거될 수 있는 집합인 계산 가능하게 열거 가능한 집합(예: 계산 가능하게 열거 가능한 다른 용어에는 재귀적으로 열거 가능한 것과 반결정 가능한 것이 포함됨)의 예입니다.이와 동일하게 집합은 어떤 계산 가능한 함수의 범위인 경우에만 c.e.일반적으로 결정할 수는 없지만 ce.e. 집합은 계산 가능성 이론에서 자세히 연구되었습니다.

연구분야

위에서 설명한 계산 가능한 집합과 함수에 대한 이론을 시작으로 계산 가능성 이론 분야는 밀접하게 관련된 많은 주제의 연구를 포함하게 되었습니다.이들은 독립적인 연구 분야가 아닙니다. 이들 각 분야는 다른 분야로부터 아이디어와 결과를 도출하며, 대부분의 계산 가능성 이론가들은 대부분의 연구 분야에 익숙합니다.

상대적 연산성 및 튜링 정도

수학적 논리학에서의 계산 가능성 이론은 전통적으로 상대적 계산 가능성에 초점을 맞추고 있는데, 이것은 1939년 튜링이 도입한 오라클 튜링 기계를 사용하여 정의된 튜링 계산 가능성의 일반화입니다.[13]오라클 튜링 기계는 일반 튜링 기계의 동작을 수행하는 것 외에도 특정한 자연수 집합인 오라클에 대한 질문을 할 수 있는 가상의 장치입니다.오라클 머신은 "Is n is in oracle set?" 형태의 질문만 할 수 있습니다.오라클 세트가 계산할 수 없는 경우에도 각 질문은 즉시 올바르게 대답됩니다.따라서 계산할 수 없는 오라클이 있는 오라클 머신은 오라클이 없는 튜링 머신이 할 수 없는 집합을 계산할 수 있습니다.

비공식적으로, 자연수 A의 집합은 B를 오라클 집합으로 실행할 때 숫자가 A에 있는지 여부를 정확하게 알려주는 오라클 기계가 있다면 집합 B튜링 축소 가능합니다(이 경우 집합 A는 (상대적으로) B에서 계산 가능하고 B에서 재귀적이라고도 합니다.집합 A가 집합 B로 튜링 축소 가능하고 BA로 튜링 축소 가능한 경우 집합들은 동일한 튜링 정도(해결 불가능 정도라고도 함)를 갖는다고 합니다.집합의 튜링 정도는 집합이 얼마나 계산할 수 없는지를 정확하게 측정합니다.

정지 문제의 변형을 인코딩하는 많은 다른 집합을 포함하여 계산할 수 없는 집합의 자연적인 예는 두 가지 공통적인 특성을 가집니다.

  1. 이들은 계산적으로 열거할 수 있으며,
  2. 각각은 다원 축소를 통해 다른 것으로 번역될 수 있습니다.즉, 그러한 집합 AB가 주어졌을 때, A = {x : f(x) ∈ B}인 총 계산 가능 함수 f가 존재합니다.이 집합들은 다원 동치(또는 m 동치)라고 합니다.

집합 A가 집합 B로 다중 1 축소 가능하다면, A는 B로 튜링 축소 가능하지만, 그 역이 항상 성립하지는 않습니다.계산할 수 없는 집합의 자연적인 예는 모두 다원 동치이지만, 계산할 수 있는 열거 가능 집합 AB를 구성하여 AB로 튜링을 축소할 수 있지만 B로 축소할 수는 없습니다.모든 계산적 열거 가능 집합은 중단 문제에 대해 다원 축소 가능하며, 따라서 중단 문제는 다원 축소 가능성 및 튜링 축소 가능성과 관련하여 가장 복잡한 계산적 열거 가능 집합임을 알 수 있습니다.1944년, 포스트는[14] 모든 계산 가능한 집합이 계산 가능한지 또는 튜링이 정지 문제와 동등한지, 즉 그 둘 사이에 튜링 정도의 중간값을 갖는 계산 가능한 집합이 없는지 물었습니다.

중간 결과로 Post는 단순, 초단순 및 초단순 집합과 같이 계산 가능하게 열거 가능한 집합의 자연 유형을 정의했습니다.포스트는 이 집합들이 다원 환원성과 관련하여 계산 가능한 집합과 중단 문제 사이에 엄격하게 있다는 것을 보여주었습니다.포스트는 또한 그들 중 일부가 튜링 환원성보다 더 강한 다른 환원성 개념 하에서 엄격하게 중간적이라는 것을 보여주었습니다.그러나 포스트는 계산적으로 열거할 수 있는 중간 튜링 학위 집합의 존재에 대한 주요 문제를 열어두었습니다. 이 문제는 포스트의 문제로 알려지게 되었습니다.10년 후, 클라인과 포스트는 1954년에 계산 가능한 집합과 정지 문제 사이에 중간 튜링 학위가 있다는 것을 보여주었지만, 이들 학위 중 어떤 것도 계산 가능한 집합을 포함한다는 것을 보여주지 못했습니다.그 직후 프리드버그와 무치니크는 계산적으로 열거할 수 있는 중간 학위 집합의 존재를 확립함으로써 포스트의 문제를 독립적으로 해결했습니다.이 획기적인 결과는 매우 복잡하고 사소한 구조를 가지고 있는 것으로 밝혀진 계산 가능한 열거 가능한 집합의 튜링 정도에 대한 광범위한 연구를 열었습니다.

계산적으로 열거할 수 없는 집합은 셀 수 없이 많고, 모든 집합의 튜링 정도에 대한 조사는 계산적으로 열거할 수 있는 튜링 정도에 대한 조사만큼 계산 가능성 이론에서 중심적입니다.특별한 특성을 가진 많은 학위들이 구성되었습니다: 그 정도에 대해 계산 가능한 모든 함수가 (상대화되지 않은) 계산 가능한 함수에 의해 주요화되는 과면역 자유도; 다음에 따라 일정한 c가 있다는 의미에서 모든 계산 가능한 함수 g를 지배하는 함수 f를 계산할 수 있는 높은 정도.g 모든 x > c에 대해 g(x) < f(x); 알고리즘적으로 무작위한 집합을 포함하는 무작위한 정도; 1-generic 집합의 1-generic 정도; 및 한계 계산 가능한 집합의 중단 문제 미만의 정도.

임의 연구(반드시 계산적으로 열거할 수 있는 것은 아님)튜링 학위는 튜링 점프에 대한 연구를 포함합니다.집합 A가 주어지면, A튜링 점프는 오라클 A와 함께 실행되는 오라클 튜링 기계의 중단 문제에 대한 해결책을 인코딩하는 자연수의 집합입니다.임의의 집합의 튜링 점프는 항상 원래 집합보다 높은 튜링 정도이며, 프리드버그의 정리는 정지 문제를 계산하는 임의의 집합은 다른 집합의 튜링 점프로 구할 수 있음을 보여줍니다.포스트의 정리는 튜링 점프 연산과 산술 계층 간의 밀접한 관계를 설정하는데, 이는 산술에서의 정의 가능성에 기초하여 자연수의 특정 부분 집합을 분류하는 것입니다.

튜링 학위에 대한 많은 최근의 연구는 튜링 학위 집합과 계산 가능하게 열거 가능한 집합을 포함하는 튜링 학위 집합의 전체 구조에 초점을 맞추고 있습니다.쇼어와 슬라만의[15] 깊은 정리는 x도를 튜링 점프 정도로 매핑하는 함수는 튜링 도의 부분 순서로 정의할 수 있다고 말합니다.Ambos-Spies and Fejer의[16] 조사는 이 연구와 역사적 진행에 대한 개요를 제공합니다.

기타 축소 가능성

튜링 환원성 이외의 환원성 관계를 연구하는 계산 가능성 이론의 지속적인 연구 분야.포스트는[14] 몇 가지 강력한 축소 가능성을 소개했는데, 이는 진실을 의미하는 축소 가능성을 암시하기 때문에 붙여진 이름입니다.강력한 축소성을 구현하는 튜링 머신은 어떤 오라클과 관계없이 총 함수를 계산합니다.약한 축소성은 모든 오라클에 대해 축소 프로세스가 종료되지 않을 수 있는 것을 말합니다.튜링 환원성이 그 한 예입니다.

강력한 축소 기능은 다음과 같습니다.

1-1 축소 가능:f(n)가 B에 있는 경우에만 각각의 nA에 있도록 총 계산 가능한 주입 함수 f가 있는 경우 A는 B에 대해 1-1 축소 가능(또는 1 축소 가능)합니다.
다원 축소성:이는 근본적으로 f가 주사적이라는 제약 없이 일대일 축소 가능성입니다.f(n)가 B에 있는 경우에만 각각의 nA에 있도록 하는 총 계산 가능 함수 f가 있는 경우 AB에 대해 다원 축소 가능(또는 m 축소 가능)합니다.
Truth-table 축소 가능성:주어진 오라클에 관계없이 총 함수를 계산하는 오라클 튜링 기계를 통해 AB로 튜링 축소 가능하다면 AB로 축소 가능합니다.이는 칸토어 공간의 콤팩트함 때문에 축소가 오라클에 동시에 하나의 질문 목록(입력에 따라 다름)을 제시하고, 그 답변을 본 후 초기 질의에 대한 오라클의 답변과 관계없이 추가 질문을 하지 않고도 결과물을 생성할 수 있다는 것과 같습니다.진실표 축소 가능성의 많은 변형들도 연구되어 왔습니다.

추가적인 축소 가능성(긍정적, 접속적, 접속적, 선형 및 그 약한 버전과 경계적 버전)은 축소(계산 가능성 이론) 기사에서 논의됩니다.

강력한 축소 가능성에 대한 주요 연구는 계산할 수 있는 모든 집합의 클래스와 자연수의 모든 부분 집합의 클래스에 대한 이론을 비교하는 것이었습니다.또한 축소 가능성 간의 관계도 연구되었습니다.예를 들어, 모든 튜링 학위는 진리표 학위이거나 무한히 많은 진리표 학위의 결합이라고 알려져 있습니다.

튜링 환원성보다 약한 환원성(즉, 튜링 환원성에 의해 내포되는 환원성)도 연구되었습니다.가장 잘 알려진 것은 산술적 환원성과 초 산술적 환원성입니다.이러한 축소 가능성은 산술 표준 모형에 대한 정의 가능성과 밀접하게 관련되어 있습니다.

라이스의 정리와 산술적 위계

Rice는 모든 중요하지 않은 클래스 C에 대해 지수 집합 E = {e: 집합 WC에 있는 eth c.e}는 중단 문제 또는 그 보완이 E다원 환원될 수 있는 속성을 가지고 있음을 보여주었습니다(자세한 내용은 Rice의 정리 참조).그러나 이러한 인덱스 집합의 대부분은 중단 문제보다 훨씬 더 복잡합니다.이러한 유형의 집합은 산술 계층 구조를 사용하여 분류할 수 있습니다.예를 들어, 모든 유한 집합의 클래스의 인덱스 집합 FIN은 레벨 σ, 모든 재귀 집합의 클래스의 인덱스 집합 REC는 레벨 σ, 모든 유한 집합의 인덱스 집합 COFIN은 레벨 σ, 모든 튜링 완료 집합 σ의 클래스의 인덱스 집합 COFIN도 있습니다.이러한 계층 수준은 귀납적으로 정의되며, σ에는 σ에 대해 계산 가능하게 열거할 수 있는 모든 집합만 포함되며, σ에는 계산 가능하게 열거할 수 있는 집합이 포함됩니다.여기에 제공된 인덱스 집합은 수준에 대해 완료된 것으로, 즉 이러한 수준의 모든 집합을 주어진 인덱스 집합으로 줄일 수 있습니다.

역수학

역수학의 프로그램은 2차 산술의 하위 시스템에서 수학의 특정 정리를 증명하기 위해 어떤 집합 존재 공리가 필요한지를 묻습니다. 연구는 Harvey Friedman에 의해 시작되었고 Stephen Simpson과 다른 사람들에 의해 자세히 연구되었습니다; 1999년, Simpson은[17] 그 프로그램에 대해 상세한 토론을 하였습니다.문제의 집합 존재 공리는 다양한 축소 가능성 개념 하에서 자연수의 거듭제곱 집합이 닫혀 있다는 공리에 비공식적으로 해당합니다.역수학에서 연구된 그러한 공리 중 가장 약한 것은 튜링 환원성 하에서 자연의 멱집합이 닫혀 있다는 재귀적 이해입니다.

번호 매김

숫자는 함수들의 열거입니다; 그것은 ex의 두 개의 매개변수를 가지고 입력 x의 숫자로 e번째 함수의 값을 출력합니다. 숫자들은 비록 일부 구성원들이 총 계산 가능한 함수들이지만 부분적으로 계산될 수 있습니다.허용되는 숫자는 다른 모든 숫자를 번역할 수 있는 숫자입니다.프리드버그 넘버링(Friedberg numberg numbering, 발견자의 이름을 따서 명명됨)은 모든 부분 계산 가능 함수의 1-1 넘버링입니다. 반드시 허용 가능한 넘버링은 아닙니다.이후의 연구는 계산적으로 열거할 수 있는 집합의 클래스와 같은 다른 클래스의 수를 다루기도 했습니다.예를 들어, 곤차로프는 계산 가능한 동형 사상과 관련하여 숫자가 정확히 두 개의 클래스에 속하는 계산 가능한 열거 집합의 클래스를 발견했습니다.

우선순위방식

Post의 문제는 priority method라는 방법으로 풀었는데, 이 방법을 사용한 증명을 priority method라고 합니다.이 메서드는 주로 특정 속성을 가진 계산 가능한 열거형 집합을 구성하는 데 사용됩니다.이 방법을 사용하기 위해 구성할 집합의 원하는 속성을 요구사항으로 알려진 무한한 목표 목록으로 분할하여 모든 요구사항을 충족하면 집합이 원하는 속성을 갖도록 합니다.각 요구 사항은 요구 사항의 우선 순위를 나타내는 자연수에 할당되므로 0은 가장 중요한 우선 순위에 할당되고 1은 두 번째로 중요한 우선 순위에 할당됩니다.그런 다음, 각 단계는 단계적으로 구성되며, 최종 집합이 요구 사항을 충족하도록 집합에 숫자를 추가하거나 집합에서 숫자를 금지함으로써 요구 사항 중 하나를 충족하려고 시도합니다.한 가지 요구 사항을 충족하면 다른 요구 사항이 충족되지 않을 수 있습니다. 우선 순위는 이러한 경우에 무엇을 해야 할지 결정하는 데 사용됩니다.

우선순위 인수는 계산 가능성 이론에서 많은 문제를 해결하기 위해 사용되어 왔으며, 그 복잡성에 따라 계층 구조로 분류되었습니다.[11]복잡한 우선순위 인수는 기술적이고 따르기 어려울 수 있기 때문에, 전통적으로 우선순위 인수 없이 결과를 증명하거나, 우선순위 인수로 증명된 결과가 또한 이 인수 없이 증명될 수 있는지 확인하는 것이 바람직하다고 여겨졌습니다.예를 들어, Kummer는 우선순위 방법을 사용하지 않고 프리드버그 숫자의 존재를 증명하는 논문을 발표했습니다.

계산적으로 열거할 수 있는 집합들의 격자

포스트가 단순한 집합의 개념을 무한한 c.e.e. 집합을 포함하지 않는 무한 보어를 갖는 c.e. 집합으로 정의했을 때, 그는 포함하에 계산적으로 열거할 수 있는 집합의 구조를 연구하기 시작했습니다.이 격자는 잘 연구된 구조가 되었습니다.계산 가능한 집합은 집합과 그 보어가 모두 계산 가능한 경우에만 집합이 계산 가능하다는 기본 결과에 의해 이 구조에서 정의될 수 있습니다.무한 집합은 항상 무한 계산 가능한 부분 집합을 갖지만, 반면에 단순 집합은 존재하지만 항상 무한 계산 가능한 부분 집합을 갖는 것은 아닙니다.이미 도입된 초단순 및 초단순 집합을 게시합니다[14]. 나중에 모든 초단순 집합이 주어진 최대 집합의 유한 변형이거나 공-무한이 되도록 c.e. 집합인 최대 집합을 구성되었습니다.이 격자에 대한 연구에서 포스트의 원래 동기는 이 성질을 만족시키는 모든 집합이 계산 가능한 집합의 튜링 정도나 정지 문제의 튜링 정도가 아닌 구조적 개념을 찾는 것이었습니다.포스트는 그러한 부동산을 발견하지 못했고 그의 문제에 대한 해결책은 대신 우선순위 방법을 적용했습니다; 1991년에 해링턴과 소는[18] 결국 그러한 부동산을 발견했습니다.

오토모피즘 문제

또 다른 중요한 질문은 계산 가능성 이론 구조에서 오토모픽의 존재입니다.이러한 구조 중 하나는 포함 모듈로 유한 차분 하에서 계산적으로 열거 가능한 집합 중 하나입니다. 이 구조에서 집합 차분 B - A가 유한한 경우에만 A는 B 아래입니다.최대 집합(앞 단락에서 정의된 바와 같이)은 비 최대 집합에 자동화될 수 없다는 속성을 갖습니다. 즉, 방금 언급한 구조 아래에서 계산 가능하게 열거할 수 있는 집합의 자동화가 존재하면 모든 최대 집합은 다른 최대 집합에 매핑됩니다.1974년, 소어는[19] 또한 역홀드, 즉 두 개의 최대 집합이 모두 오토모픽이라는 것을 보여주었습니다.따라서 최대 집합들은 궤도를 형성하는데, 즉 모든 자기 변형은 최대성을 보존하고 어떤 자기 변형에 의해 두 개의 최대 집합이 서로 변환됩니다.해링턴은 오토모픽 특성의 또 다른 예를 제시했습니다. 즉, 정지 문제와 동일한 다중 1 집합인 크리에이티브 집합입니다.

계산할 수 있게 열거할 수 있는 집합의 격자 외에도, 모든 집합의 튜링 학위의 구조뿐만 아니라 c.e. 집합의 구조에 대해서도 자기 변형이 연구됩니다.두 경우 모두 Cooper는 어느 정도 다른 정도로 지도를 만드는 중요하지 않은 자기 변형을 만들었다고 주장합니다. 그러나 이 구성은검증되지 않았고 몇몇 동료들은 그 구성이 오류를 포함하고 있고 튜링 학위의 하찮은 자기 변형이 있는지에 대한 문제는 여전히 이 영역에서 해결되지 않은 주요 문제 중 하나입니다.[20][16]

콜모고로프 복잡도

콜모고로프 복잡성알고리즘 무작위성 분야는 1960년대와 1970년대에 차이틴, 콜모고로프, 레빈, 마르틴-뢰프, 솔로몬로프에 의해 개발되었습니다(여기에 알파벳 순서로 이름이 주어졌습니다; 많은 연구가 독립적이었고, 무작위성 개념의 통일성은 당시에 이해되지 않았습니다).주요 아이디어는 보편적 튜링 기계 U를 고려하고 U(p)가 x를 출력하는 가장 짧은 입력 p의 길이로 수(또는 문자열) x의 복잡도를 측정하는 것입니다.이 접근법은 유한한 객체에 대한 무작위성 개념을 호출함으로써 무한 시퀀스(자연수 부분 집합의 특징 함수와 동등하게)가 무작위인지 아닌지를 결정하는 이전의 방법에 혁명을 일으켰습니다.콜모고로프 복잡성은 독립적인 연구의 주제가 되었을 뿐만 아니라 증명을 얻기 위한 도구로서 다른 주제에도 적용됩니다.이 지역에는 아직도 미해결 문제가 많이 남아 있습니다.공개된 문제의[nb 2] 목록은 조셉 밀러와 안드레 나이스에 의해 유지됩니다.

주파수 계산

계산 가능성 이론의 이 분과에서는 다음 질문을 분석했습니다.0 < m < n인 고정 mn에 대해, 이 함수 A에 대해 방정식 A(x) = y적어도 m이 되도록 n개다른 입력 x, x, ..., x 튜플에 대해 계산할 수 있습니다.이러한 집합을 (m, n)-재귀 집합이라고 합니다.이 계산 가능성 이론의 첫 번째 주요 결과는 집합이 어떤 m에 대하여 (m, n)-반복이면 계산 가능하다는 트라흐텐브로트의 결과이며, n은 2m > n입니다. 반면에, (1968년 Jockusch가 집합을 소개하기 전에 이미 비공식적으로 알려진) Jockusch의 반반복 집합은 (m,n- 2m < n + 1인 경우에만 recursive합니다.셀 수 없이 많은 이러한 집합들과 계산할 수 있지만 계산할 수 없는 이러한 유형의 집합들이 있습니다.나중에 Degtev는 (1, n + 1)-재귀적이지만 (1, n)-재귀적이 아닌 계산적으로 열거할 수 있는 집합의 계층을 설정했습니다.러시아 과학자들의 오랜 연구 끝에, 이 주제는 주파수 계산을 위에서 언급한 경계 감소성 및 기타 관련 개념과 연결한 경계 쿼리에 대한 베이겔의 논문으로 서양에서 다시 대중화되었습니다.주요한 결과 중 하나는 집합 An개의 다른 수들의 각 튜플에 대해 어떤 알고리즘이 n개의 다른 수들의 가능한 선택들을 열거하는 경우에만 계산 가능하다는 Kummer의 카디널리티 이론이었다; 이러한 선택들은 참된 카디널리티 부틀을 포함해야 합니다.적어도 하나의 거짓된 것을 제거합니다.

귀납적 추론

이것이 학습이론의 계산 가능성 이론 분야입니다.그것은 E를 기준으로 합니다. Mark Gold의 학습 모델은 1967년부터 한계에 도달했고 그 이후로 점점 더 많은 학습 모델을 발전시켜 왔습니다.일반적인 시나리오는 다음과 같습니다. 계산 가능한 함수의 클래스 S가 주어졌을 때, (f(0), f(1), ..., f(n) 가설의 형태의 입력에 대해 출력하는 학습자(즉, 계산 가능한 함수)가 있습니까?학습자 M은 모든 계산 가능한 함수의 허용 가능한 숫자에 대해 거의 모든 가설이 동일한 인덱스 e of f이면 함수 f를 학습합니다. MS의 모든 f를 학습하면 S를 학습합니다. 기본적인 결과는 모든 계산 가능한 함수의 클래스 REC는 학습 가능한 반면 모든 계산 가능한 함수의 클래스 REC는 학습 가능하지 않다는 것입니다.학식이 있는많은 관련 모델이 고려되었고 또한 긍정적인 데이터로부터 계산할 수 있는 열거 가능한 집합의 클래스 학습은 1967년 이후 골드의 선구적인 논문에서 연구된 주제입니다.

튜링 계산가능성의 일반화

계산 가능성 이론에는 Sacks가 1990년에 설명한 산술 축소성, 초 산술 축소성α-재귀 이론과 같은 이 분야의 일반화된 개념에 대한 연구가 포함됩니다.[21]이러한 일반화된 개념은 튜링 기계에 의해 실행될 수 없는 축소성을 포함하지만 그럼에도 불구하고 튜링 축소성의 자연스러운 일반화입니다.이러한 연구에는 개별 숫자에 대한 정량화 외에 자연수 집합에 대한 정량화를 허용함으로써 산술 계층과 다른 분석 계층을 조사하는 방법이 포함됩니다.이 영역은 순서 및 트리 이론과 연결되어 있습니다. 예를 들어 무한 분기가 없는 계산 가능한(이진) 트리의 모든 인덱스 집합은 분석 계층 구조의 레벨π 11 _1}^{1}}에 대해 완전합니다.튜링 환원성과 초 산술 환원성 모두 효과적인 설명 집합 이론 분야에서 중요합니다.구성 가능성의 정도에 대한 훨씬 더 일반적인 개념은 집합 이론에서 연구됩니다.

연속 계산 가능성 이론

디지털 계산을 위한 계산 가능성 이론이 잘 발달되어 있습니다.계산 가능성 이론은 아날로그 컴퓨터, 아날로그 신호 처리, 아날로그 전자 장치, 신경망 및 연속 시간 제어 이론에서 발생하는 아날로그 계산에 대해 덜 잘 개발되어 있으며, 미분 방정식과 연속 동적 시스템에 의해 모델링됩니다.[22][23]예를 들어, Blum과 같은 계산 모델이 있습니다.Shub-Smale 기계 모델은 실제에 대한 공식화된 계산을 가지고 있습니다.

정의 가능성, 증명 및 계산 가능성 간의 관계

자연수 집합의 튜링 정도와 1차 공식을 사용하여 해당 집합을 정의하는 난이도(산수 계층 구조의 관점) 사이에는 밀접한 관계가 있습니다.그러한 관계 중 하나는 포스트의 정리에 의해 정확하게 만들어집니다.쿠르트 괴델은 그의 완전성 정리불완전성 정리의 증명에서 약한 관계를 증명했습니다.괴델의 증명은 효과적인 1차 이론의 논리적 결과의 집합이 계산 가능하게 열거할 수 있는 집합이며, 이론이 충분히 강력하다면 이 집합은 계산할 수 없을 것이라는 것을 보여줍니다.마찬가지로, 타르스키의 무한성 정리는 정의 가능성과 계산 가능성의 관점에서 해석될 수 있습니다.

계산 가능성 이론은 자연수와 자연수의 집합에 대한 공식 이론인 2차 산술과도 연결됩니다.특정 집합이 계산 가능하거나 비교적 계산 가능하다는 사실은 종종 이러한 집합이 2차 산술의 약한 하위 시스템에서 정의될 수 있음을 의미합니다.역수학 프로그램은 이러한 하위 시스템을 사용하여 잘 알려진 수학 정리에 내재된 계산 불가능성을 측정합니다.1999년 심슨은[17] 2차 산술과 역수학의 많은 측면을 논의했습니다.

증명 이론 분야는 2차 산술과 페아노 산술에 대한 연구와 페아노 산술보다 약한 자연수의 형식 이론을 포함합니다.이러한 약한 시스템의 강도를 분류하는 한 가지 방법은 시스템이 완전한 것으로 증명할 수 있는 계산 가능한 함수를 특성화하는 것입니다.[24]예를 들어, 원시 재귀적 산술에서 총합일 가능성이 있는 계산 가능한 함수는 실제로 원시 재귀적인 반면, 페아노 산술은 원시 재귀적이 아닌 아커만 함수와 같은 함수가 총합임을 증명합니다.그러나 모든 계산 가능한 함수가 피아노 산술에서 완전한 것은 아닙니다. 그러한 함수의 예는 굿스타인의 정리에 의해 제공됩니다.

이름.

계산 가능성과 그 일반화를 다루는 수학적 논리학 분야는 초창기부터 "재귀 이론"이라고 불려왔습니다.로버트 1세. 이 분야의 저명한 연구자인 Soare는 이 분야를 대신 "계산 가능성 이론"이라고 불러야 한다고 제안했습니다[12].그는 "계산 가능한"이라는 단어를 사용하는 튜링의 용어가 클라인이 소개한 "재귀적"이라는 단어를 사용하는 용어보다 더 자연스럽고 더 널리 이해되고 있다고 주장합니다.많은 현대 연구자들이 이 대체 용어를 사용하기 시작했습니다.[nb 3]이러한 연구자들은 부분 재귀 함수재귀 열거 가능(r.e.) 집합 대신 부분 계산 가능 함수 및 계산 가능 열거 가능(c.e. set)과 같은 용어도 사용합니다.그러나 포트나우와 심슨이 설명한 것처럼[25] 모든 연구자들이 확신한 것은 아닙니다.[26]일부 논자들은 재귀 이론이라는 이름과 계산 가능성 이론 모두 계산 가능성 이론에서 연구되는 대부분의 대상이 계산 가능하지 않다는 사실을 전달하지 못한다고 주장합니다.[27]

1967년 로저스는[28] 계산 가능성 이론의 핵심 속성은 자연수에 대한 계산 가능한 사영하에서 결과와 구조가 불변해야 한다는 것이라고 제안했습니다(이 제안은 기하학에서 에를랑겐 프로그램의 아이디어를 기반으로 합니다.이 아이디어는 유클리드 평면의 회전이 그 위에 그려진 선들의 기하학적 측면을 바꾸지 않는 것처럼 계산 가능한 사영은 집합 내의 어떤 구조를 나타내기보다는 집합 내의 숫자의 이름만 바꾼다는 것입니다.임의의 두 무한 계산 가능 집합은 계산 가능한 비투영에 의해 연결되므로, 이 제안은 모든 무한 계산 가능 집합을 식별합니다(유한 계산 가능 집합은 사소한 것으로 간주됨).로저스에 따르면, 계산 가능성 이론에 관심이 있는 집합은 계산 불가능한 집합이며, 자연수의 계산 가능한 투영에 의해 동등성 클래스로 분할됩니다.

전문기관

연산성 이론의 주요 전문 단체는 상징 논리학 협회이며, 매년 여러 연구 회의를 개최합니다.학제간 연구 협회인 유럽의 계산 가능성(Computability in Europe, CiE)은 또한 일련의 연례 회의를 조직합니다.

참고 항목

메모들

  1. ^ 이러한 기초 논문의 대부분은 마틴 데이비스(Martin Davis)가 편집한 미결정(The Undecision)(1965)에서 수집됩니다.
  2. ^ 안드레 나이스의 홈페이지에는 콜모고로프 복잡성에 대한 공개된 문제 목록이 있습니다.
  3. ^ MathSciNet에서 "computable enumerable" 및 "c.e."와 같은 제목을 검색한 결과, 많은 논문이 다른 용어뿐만 아니라 이 용어와 함께 출판되었음을 알 수 있습니다.

참고문헌

  1. ^ Radó, Tibor (May 1962). "On non-computable functions". Bell System Technical Journal. 41 (3): 877–884. doi:10.1002/j.1538-7305.1962.tb00480.x.
  2. ^ Soare, Robert Irving (2011-12-22). "Computability Theory and Applications: The Art of Classical Computability" (PDF). Department of Mathematics. University of Chicago. Archived (PDF) from the original on 2022-06-30. Retrieved 2017-08-23.
  3. ^ a b Kleene, Stephen Cole (1952). Introduction to Metamathematics. North-Holland. pp. 300, 376. ISBN 0-7204-2103-9.
  4. ^ a b Davis, Martin, ed. (2004) [1965]. The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions. Dover Publications, Inc. p. 84. ISBN 978-0-486-43228-1. p. 84: Kurt Gödel (1946): Tarski has stressed in his lecture (and I think justly) the great importance of the concept of general recursiveness (or Turing's computability). It seems to me that this importance is largely due to the fact that with this concept one has for the first time succeeded in giving an absolute notion to an interesting epistemological notion, i.e., one not depending on the formalism chosen.
  5. ^ Gödel, Kurt (1990). "[Gödel (1946)]". In Feferman, Solomon; et al. (eds.). Kurt Gödel Publications 1938–1974 Volume II. Vol. II. New York, USA: Oxford University Press. pp. 144ff. ISBN 978-0-19-514721-6. p. 150: To be more precise: a function of integers is computable in any formal system containing arithmetic if and only if it is computable in arithmetic, where a function f is called computable in S if there is in S a computable term representing f. (NB. 이 권에는 Kurt Gödel의 1946년 논문도 포함되어 있습니다. Charles Parsons의 해설 포함 pp. 144ff.)이 1990년 판에는 Gödelon p. 150에 의해 인용된 각주가 추가되어 있습니다. (Davis의 1965년 편집본에서 Gödel의 재인쇄본에도 추가되었습니다.)
  6. ^ Church, Alonzo (1936a). "An unsolvable problem of elementary number theory". American Journal of Mathematics. 58 (2): 345–363. doi:10.2307/2371045. JSTOR 2371045. 1965년 데이비스에서 재인쇄.
  7. ^ Church, Alonzo (1936b). "A note on the Entscheidungsproblem". Journal of Symbolic Logic. 1 (1): 40–41. doi:10.2307/2269326. JSTOR 2269326. S2CID 42323521. 1965년 데이비스에서 재인쇄.
  8. ^ a b Turing, Alan Mathison (1937) [1936]. "On computable numbers, with an application to the Entscheidungsproblem". Proceedings of the London Mathematical Society. 2. 42 (1): 230–265. doi:10.1112/plms/s2-42.1.230. S2CID 73712. Turing, Alan Mathison (1938). "On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction" (PDF). Proceedings of the London Mathematical Society. 2. 43 (1): 544–546. doi:10.1112/plms/s2-43.6.544. Archived (PDF) from the original on 2022-07-18. Retrieved 2022-08-08. Reprinted in Davis 1965.
  9. ^ Ershov, Yury Leonidovich; Goncharov, Sergei Savostyanovich [at Wikidata]; Nerode, Anil; Remmel, Jeffrey B. (1998). Handbook of Recursive Mathematics. North-Holland. ISBN 0-7204-2285-X.
  10. ^ Cutland, Nigel J. (1980). Computability, An introduction to recursive function theory. Cambridge University Press. ISBN 0-521-29465-7.
  11. ^ a b Soare, Robert Irving (1987). Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic. Springer-Verlag. ISBN 0-387-15299-7.
  12. ^ a b Soare, Robert Irving (1996). "Computability and recursion" (PDF). Bulletin of Symbolic Logic. 2 (3): 284–321. doi:10.2307/420992. JSTOR 420992. S2CID 5894394.
  13. ^ Turing, Alan Mathison (1939). "Systems of logic based on ordinals". Proceedings of the London Mathematical Society. 2. 45 (1): 161–228. doi:10.1112/plms/s2-45.1.161. hdl:21.11116/0000-0001-91CE-3. 1965년 데이비스에서 재인쇄.
  14. ^ a b c Post, Emil Leon (1944). "Recursively enumerable sets of positive integers and their decision problems". Bulletin of the American Mathematical Society. 50 (5): 284–316. doi:10.1090/S0002-9904-1944-08111-1. MR 0010514. 1965년 데이비스에서 재인쇄.
  15. ^ Shore, Richard Arnold; Slaman, Theodore Allen (1999). "Defining the Turing Jump". Mathematical Research Letters. 6 (6): 711–722. doi:10.4310/mrl.1999.v6.n6.a10. ISSN 1073-2780. MR 1739227.
  16. ^ a b Ambos-Spies, Klaus; Fejer, Peter A. (2014). "Degrees of unsolvability" (PDF). In Siekmann, Jörg H. (ed.). Computational Logic. Handbook of the History of Logic. Vol. 9. Amsterdam: Elsevier/North-Holland. pp. 443–494. doi:10.1016/B978-0-444-51624-4.50010-1. ISBN 978-0-444-51624-4. MR 3362163. Archived from the original (PDF) on 2013-04-20.
  17. ^ a b Simpson, Steven George (1999). Subsystems of Second Order Arithmetic. Springer-Verlag. ISBN 3-540-64882-8.
  18. ^ Harrington, Leo Anthony; Soare, Robert Irving (1991). "Post's Program and incomplete recursively enumerable sets". Proceedings of the National Academy of Sciences USA. 88 (22): 10242–10246. Bibcode:1991PNAS...8810242H. doi:10.1073/pnas.88.22.10242. PMC 52904. PMID 11607241.
  19. ^ Soare, Robert Irving (1974). "Automorphisms of the lattice of recursively enumerable sets, Part I: Maximal sets". Annals of Mathematics. 100 (1): 80–120. doi:10.2307/1970842. JSTOR 1970842.
  20. ^ Slaman, Theodore Allen; Woodin, William Hugh (1986). "Definability in the Turing degrees". Illinois Journal of Mathematics. 30 (2): 320–334. doi:10.1215/ijm/1256044641. MR 0840131.
  21. ^ Sacks, Gerald Enoch (1990). Higher Recursion Theory. Springer-Verlag. ISBN 3-540-19305-7.
  22. ^ Orponen, Pekka (1997). "A Survey of Continuous-Time Computation Theory". Advances in Algorithms, Languages, and Complexity. pp. 209–224. CiteSeerX 10.1.1.53.1991. doi:10.1007/978-1-4613-3394-4_11. ISBN 978-1-4613-3396-8.
  23. ^ Moore, Cris (1996). "Recursion theory on the reals and continuous-time computation". Theoretical Computer Science. 162 (1): 23–44. CiteSeerX 10.1.1.6.5519. doi:10.1016/0304-3975(95)00248-0.
  24. ^ Fairtlough, Matt; Wainer, Stanley S. (1998). "Hierarchies of Provably Recursive Functions". In Buss, Samuel R. (ed.). Handbook of Proof Theory. Elsevier. pp. 149–208. ISBN 978-0-08-053318-6.
  25. ^ Fortnow, Lance Jeremy (2004-02-15). "Is it Recursive, Computable or Decidable?". Archived from the original on 2022-08-07. Retrieved 2018-03-22.
  26. ^ Simpson, Stephen George (1998-08-24). "What is computability theory?". FOM email list. Archived from the original on 2021-12-18. Retrieved 2006-01-09.
  27. ^ Friedman, Harvey (1998-08-28). "Renaming recursion theory". FOM email list. Archived from the original on 2022-03-01. Retrieved 2006-01-09.
  28. ^ Rogers, Hartley Jr. (1987). The Theory of Recursive Functions and Effective Computability (2nd ed.). MIT Press. ISBN 0-262-68052-1.

추가열람

학부 수준의 텍스트
고급 텍스트
설문지 및 자료집
연구논문 및 자료집

외부 링크