계산가능성 이론
위에서 설명한 재귀 집합 및 함수의 이론을 시작으로,재귀 이론의 분야는 많은 밀접한 관련 주제에 대한 연구를 포함하는 것으로 성장했다. 이들은 독립적 인 연구 영역이 아닙니다.이 영역은 각각 다른 영역에서 아이디어와 결과를 이끌어 내며 대부분의 재귀 이론가들은 대다수에 익숙합니다.
상대 계산 가능성 및 튜링 학위 편집
수학적 논리의 재귀 이론은 전통적으로 튜링(1939)이 도입 한 오라클 튜링 기계를 사용하여 정의 된 튜링 계산 가능성의 일반화 인 상대 계산 가능성에 중점을 두었습니다. 오라클 튜링 기계는 일반 튜링 기계의 작업을 수행하는 것 외에도 자연수의 특정 집합 인 오라클의 질문을 할 수있는 가상의 장치입니다. 오라클 머신은”오라클 세트에 있습니까?”. 오라클 세트를 계산할 수없는 경우에도 각 질문에 즉시 올바르게 답변됩니다. 따라서 계산 불가능한 오라클을 가진 오라클 머신은 오라클이없는 튜링 머신이 할 수없는 세트를 계산할 수 있습니다.
비공식적으로 자연수 집합 ㅏ 이다 튜링 로 환원 가능 세트 비 오라클 머신 숫자가 있는지 여부를 올바르게 알려주는 경우 ㅏ 실행할 때 비 오라클 집합으로(이 경우 집합 ㅏ 또한(상대적으로)계산 가능…에서 비 과 재귀 비). 만약 세트 ㅏ 이다 튜링 로 환원 가능 세트 비 과 비 이다 튜링 로 환원 가능 그런 다음 세트는 동일한 튜링 정도(용해 불가능한 정도라고도 함)를 가지고 있다고합니다. 세트의 튜링 정도는 세트가 얼마나 비교할 수 없는지에 대한 정확한 측정을 제공합니다.
정지 문제의 변형을 인코딩하는 여러 집합을 포함하여 계산할 수 없는 집합의 자연스러운 예에는 두 가지 속성이 공통적으로 있습니다:
- 그것들은 재귀 적으로 열거 가능하며,
- 각각은 다 하나의 감소를 통해 다른 것으로 번역 될 수 있습니다. 즉,주어진 이러한 세트 ㅏ 과 비,총 계산 가능한 함수가 있습니다 에프 그런 ㅏ={엑스:에프(엑스)에프(엑스)비}. 이 세트는 많은 것으로 알려져 있습니다-하나의 동등한(또는 미디엄-동등한).
다-하나의 감소는 튜링 감소보다”강하다”. 비 계산 세트의 자연적인 예는 모두 많은-하나의 동등한,재귀 적으로 열거 가능한 세트를 구성 할 수 있습니다 ㅏ 과 비 그러한 ㅏ 이다 튜링 환원 가능…에 비 그러나 많은 것은 아닙니다-하나 환원 가능 비. 모든 재귀 적으로 열거 가능한 세트는 정지 문제로 다원 환원 가능하다는 것을 알 수 있으며,따라서 정지 문제는 다원 환원 가능성과 튜링 환원 가능성과 관련하여 가장 복잡한 재귀 적으로 열거 가능한 세트입니다. 포스트(1944)는 재귀 적으로 열거 가능한 모든 세트가 계산 가능한지 또는 정지 문제와 동등한 튜링인지,즉 이들 둘 사이의 중간 튜링 학위를 가진 재귀 적으로 열거 가능한 세트가 없는지 물었다.
중간 결과로서,단순,초간단 및 초간단 세트와 같은 재귀 적으로 열거 가능한 세트의 자연 유형을 정의했습니다. 포스트는 이러한 집합이 계산 가능한 집합과 다원 환원성에 대한 정지 문제 사이에 엄격하게 있음을 보여주었습니다. 포스트는 또한 그들 중 일부는 튜링 환원성보다 강한 다른 환원성 개념 하에서 엄격하게 중간임을 보여 주었다. 그러나 포스트 중간 튜링 정도의 재귀 열거 세트의 존재의 주요 문제를 열어 왼쪽;이 문제는 포스트의 문제로 알려지게되었다. 10 년 후,크리네와 포스트는 1954 년 거기에 그 계산 가능한 세트와 정지 문제 사이의 중간 튜링도 있지만,그들은 이러한 학위를 재귀 적으로 열거 세트가 포함되어 표시 실패했다. 이 후 곧 프리드버그와 무슈닉은 재귀적으로 열거 가능한 중간 수준의 집합의 존재를 확립함으로써 포스트의 문제를 독립적으로 해결했다. 이 획기적인 결과는 매우 복잡하고 비-사소한 구조를 가지고 밝혀졌다 재귀 열거 세트의 튜링 학위의 폭 넓은 연구를 열었다.
재귀 적으로 열거 할 수없는 많은 세트가 있으며,모든 세트의 튜링 학위에 대한 조사는 재귀 적으로 열거 할 수있는 튜링 학위에 대한 조사만큼 재귀 이론에서 핵심입니다. 특별한 속성을 가진 많은 학위가 구성되었습니다:그 정도에 대한 계산 가능한 모든 함수가(비 관계화 된)계산 가능한 함수에 의해 전공되는 과 면역이없는 학위; 함수를 계산할 수있는 상대적인 높은 학위 에프 모든 계산 가능한 함수를 지배하는 지 상수가 있다는 의미에서 씨 에 따라 지 그런 지(엑스)<에프(엑스)모든 엑스>씨;알고리즘 적으로 무작위 세트를 포함하는 무작위 학위;1-일반 학위 1-일반 세트;그리고 한계 재귀 세트의 정지 문제 아래도.
임의의(반드시 재귀 적으로 열거 할 수있는 것은 아님)튜링 학위에 대한 연구는 튜링 점프에 대한 연구를 포함합니다. 어떤 세트의 튜링 점프는 항상 원래 세트보다 높은 튜링 정도이며,프리드 부르크의 정리는 정지 문제를 계산하는 모든 세트가 다른 세트의 튜링 점프로 얻을 수 있음을 보여줍니다. 포스트의 정리는 튜링 점프 연산과 산술 계층 사이의 밀접한 관계를 확립하는데,이는 산술에서의 정의 가능성에 기초한 자연수의 특정 하위 집합의 분류이다.
튜링 학위에 대한 최근의 많은 연구는 튜링 학위의 집합과 재귀 적으로 열거 가능한 집합을 포함하는 튜링 학위의 집합의 전체 구조에 초점을 맞추고있다. ㅏ 깊은 정리 의 해안 과 슬라 만(1999)는 학위 10 을 튜링 점프의 정도에 매핑하는 함수가 튜링 도의 부분 순서로 정의 할 수 있다고 말합니다. 암 보스-스파이와 페예(2006)의 최근 설문 조사는이 연구와 그 역사적 진행에 대한 개요를 제공합니다.
기타 환원편집
재귀 이론 연구의 지속적인 영역은 튜링 환원성 이외의 환원성 관계를 연구한다. 포스트(1944)는 몇 가지 강력한 환원성을 도입했는데,이는 진실 테이블 환원성을 의미하기 때문에 명명되었습니다. 이것은 수학적으로 정확한 유형 계층구조인,강력한 타입을 정의합니다. 약한 환원성은 환원 과정이 모든 신탁에 대해 종료되지 않을 수있는 것들이다;튜링 환원성이 하나의 예이다.
강한 환원성은 다음을 포함합니다:
하나-하나 환원성 ㅏ 이다 하나-하나 환원성(또는 1-환원성)…에 비 총 계산 가능한 주사 함수가있는 경우 에프 이러한 각 엔 에 ㅏ 경우 및 경우에만 에프(엔)에 비.다-하나 환원성 이것은 본질적으로 하나-하나 환원성 제약 조건없이 에프 주사합니다. ㅏ 이다 많은-하나 환원 가능(또는 미디엄-환원 가능)…에 비 총 계산 가능한 함수가있는 경우 에프 그런 각 엔 에 ㅏ 만약 그리고 경우에만 에프(엔)에 비. 진실 테이블 환원성 ㅏ 이다 진실 테이블 환원 가능 비 만약 ㅏ 이 튜링 환원 가능 비 통해 오라클 튜링 주어진 오라클에 관계없이 총 함수를 계산하는 기계. 칸토어 공간의 소형화 때문에,이것은 감소가 오라클에 대한 단일 질문 목록(입력에만 따라 다름)을 동시에 제시하고,그 답을 본 후에 오라클의 초기 쿼리에 대한 답변에 관계없이 추가 질문을하지 않고 출력을 생성 할 수 있다고 말하는 것과 같습니다. 진실 테이블 환원성의 많은 변종도 연구되었습니다.
추가 환원 가능성(긍정적,분리 적,결합 적,선형 적 및 그 약하고 제한된 버전)은 감소(재귀 이론)기사에서 논의됩니다.
강력한 환원성에 대한 주요 연구는 재귀 적으로 열거 가능한 모든 집합의 클래스뿐만 아니라 자연수의 모든 하위 집합의 클래스에 대한 이론을 비교하는 것이 었습니다. 또한 환원성 간의 관계를 연구했습니다. 예를 들어,모든 튜링 학위는 진실 테이블 학위이거나 무한히 많은 진실 테이블 학위의 결합 인 것으로 알려져 있습니다.
튜링 환원성보다 약한 환원성(즉,튜링 환원성에 의해 암시되는 환원성)도 연구되었다. 가장 잘 알려진 것은 산술 환원성과 초 산적 환원성입니다. 이러한 환원성은 표준 산술 모델에 대한 정의 가능성과 밀접한 관련이 있습니다.
라이스의 정리와 산술 계층편집
라이스는 모든 사소한 클래스에 대해 씨(일부는 포함되지만 전부는 아님)인덱스 세트 이자형={이자형:이자형 이자형. 설정 우리는 에 씨}는 속성을 가지고 그 중 하나 정지 문제 또는 그 보완은 많은-하나 환원 가능 에 이자형,즉,사용하여 매핑 할 수 있습니다 많은-하나 환원 에 이자형(참조 쌀의 정리 자세한 내용은). 그러나 이러한 인덱스 세트 중 상당수는 정지 문제보다 훨씬 복잡합니다. 이러한 유형의 집합은 산술 계층 구조를 사용하여 분류 할 수 있습니다. 예를 들어,모든 유한 세트의 클래스의 인덱스 세트 핀은 레벨 2 에 있고,모든 재귀 세트의 클래스의 인덱스 세트 렉은 레벨 2 에 있으며,모든 코피 나이트 세트의 인덱스 세트 코핀은 레벨 2 에 있으며,모든 튜링-완료 세트의 클래스의 인덱스 세트 컴포지션은 레벨 2 에 있습니다. 이러한 계층 구조 수준은 유도 적으로 정의되며,1 은 재귀 적으로 열거 가능한 모든 세트를 포함합니다. 즉,이 레벨의 모든 세트는 주어진 인덱스 세트로 축소 될 수 있습니다.
역수학편집
역수학의 프로그램은 2 차 산술의 하위 시스템에서 수학의 특정 정리를 증명하기 위해 어떤 집합-존재 공리가 필요한지 묻는다. 이 연구는 하비 프리드먼에 의해 시작되었다 스티븐 심슨과 다른 사람에 의해 상세하게 연구되었다;심슨(1999)프로그램에 대한 자세한 설명을 제공합니다. 문제의 집합 존재 공리는 자연수의 힘 집합이 다양한 환원성 개념 하에서 닫혀 있다고 말하는 공리와 비공식적으로 일치합니다. 역수학에서 연구된 가장 약한 공리는 재귀적 이해력이며,이는 원주민의 힘셋이 튜링 환원성 하에서 닫혀 있다고 말한다.
번호 편집
번호 매기기는 함수 열거형입니다. 번호 매기기는 부분 재귀적일 수 있지만 일부 멤버는 총 재귀,즉 계산 가능한 함수입니다. 허용되는 번호는 다른 모든 것을 번역 할 수있는 번호입니다. ㅏ 프리드 버그 번호 매기기(발견 자의 이름을 따서 명명 됨)는 모든 부분 재귀 함수의 일대일 번호 매기기입니다. 나중에 연구는 재귀 적으로 열거 가능한 세트의 클래스와 같은 다른 클래스의 번호 매기기도 다루었습니다. 곤차 로프 예를 들어 재귀 적으로 열거 가능한 집합의 클래스를 발견했습니다.이 집합은 재귀 동형과 관련하여 정확히 두 개의 클래스로 분류됩니다.
우선 순위 방법편집
자세한 설명은 섹션 게시물의 문제와 기사 튜링 학위의 우선 순위 방법을 참조하십시오.
포스트의 문제는 우선 순위 방법이라는 방법으로 해결되었다;이 방법을 사용하여 증명은 우선 순위 인수라고합니다. 이 메서드는 주로 특정 속성을 가진 재귀 적으로 열거 가능한 집합을 생성하는 데 사용됩니다. 이 메서드를 사용하려면 생성할 집합의 원하는 속성이 요구 사항이라고 하는 무한한 목표 목록으로 구분되므로 모든 요구 사항을 충족하면 생성된 집합이 원하는 속성을 갖게 됩니다. 각 요구 사항은 요구 사항의 우선 순위를 나타내는 자연수에 할당되므로 0 은 가장 중요한 우선 순위에,1 은 두 번째로 중요한 우선 순위에 할당됩니다. 이 세트는 다음 단계로 구성되며,각 단계는 최종 집합이 요구 사항을 충족 할 수 있도록 집합에 숫자를 추가하거나 집합에서 숫자를 금지하여 요구 사항 중 하나를 충족하려고합니다. 하나의 요구 사항을 충족 시키면 다른 요구 사항이 만족스럽지 않게 될 수 있으며,우선 순위는 그러한 이벤트에서 수행 할 작업을 결정하는 데 사용됩니다.
우선 순위 인수는 재귀 이론의 많은 문제를 해결하기 위해 사용되었으며 복잡성에 따라 계층 구조로 분류되었습니다(1987 년). 복잡한 우선 순위 인수는 기술적이고 따르기가 어려울 수 있기 때문에 전통적으로 우선 순위 인수없이 결과를 증명하거나 우선 순위 인수로 입증 된 결과가 없이는 입증 될 수 있는지 확인하는 것이 바람직하다고 여겨져 왔습니다. 예를 들어,쿠머는 프리드 버그 번호 매김의 존재에 대한 증거에 우선 순위 방법을 사용하지 않고 논문을 발표했다.
재귀 적으로 열거 가능한 집합의 격자 편집
포스트가 단순한 집합의 개념을 다음과 같이 정의했을 때 아르 자형. 설정,그는 포함에서 재귀 적으로 열거 세트의 구조를 연구하기 시작했다. 이 격자는 잘 연구 된 구조가되었습니다. 재귀 집합은 집합과 그 보완이 모두 재귀 적으로 열거 가능한 경우에만 집합이 재귀 적이라는 기본 결과에 의해이 구조에서 정의 할 수 있습니다. 그러나 반면에 단순 집합은 존재하지만 공동 무한 재귀 수퍼 세트를 가지고 있지 않습니다. 포스트(1944)는 이미 초간단 및 초간단 세트를 도입했습니다. 상위 집합 은 주어진 최대 집합의 유한 변형이거나 공동 유한 한 것입니다. 이 격자의 연구에 게시물의 원래 동기 부여는이 속성을 만족하는 모든 집합도 재귀 세트의 튜링 정도도 정지 문제의 튜링 정도입니다 구조적 개념을 찾을 수 있었다. 포스트는 그러한 속성을 찾지 못했고 그의 문제에 대한 해결책은 우선 순위 방법을 대신 적용했습니다.
자형성 문제편집
또 다른 중요한 질문은 재귀-이론 구조에 자형성이 존재한다는 것이다. 이러한 구조 중 하나는 재귀 적으로 열거 가능한 집합 중 하나입니다 포함 모듈로 유한 차이;이 구조에서 ㅏ 아래 비 만약 그리고 경우에만 세트 차이 비-ㅏ 유한. 최대 집합(이전 단락에서 정의한대로)은 최대 집합이 아닌 집합으로 자동 형성 될 수 없다는 속성,즉 방금 언급 한 구조 아래에 재귀 열거 가능한 집합의 자동 형태가있는 경우 모든 최대 집합은 다른 최대 집합에 매핑됩니다. 소아레(1974)는 또한 컨버스 보유,즉 두 개의 최대 세트마다 자동화가 있음을 보여주었습니다. 따라서 최대 세트는 궤도를 형성하며,즉 모든 자동 형태는 최대 성을 유지하고 두 개의 최대 세트는 일부 자동 형태에 의해 서로 변환됩니다. 해링턴은 자동적 속성의 또 다른 예를 제시했다:창조적 인 집합의 집합,많은 집합-정지 문제에 해당하는 하나.
재귀 적으로 열거 가능한 세트의 격자 외에도 모든 세트의 튜링 도의 구조뿐만 아니라 튜링 도의 구조에 대해서도 자동 형성이 연구됩니다. 두 경우 모두 쿠퍼는 일부 학위를 다른 학위와 매핑하는 사소한 자동 형태를 구성했다고 주장합니다; 이 건설은,그러나,확인되지 않은 일부 동료들은 건설 오류가 포함되어 있다고 생각하고 튜링 학위의 사소한자가 형성이 있는지 여부의 문제는 여전히이 지역의 주요 미해결 질문 중 하나입니다(슬라 맨과 우딘 1986,암 보스-스파이와 페예 2006).
콜모고로프 복합편집
콜모고로프의 복잡성과 알고리즘 무작위성은 1960 년대와 1970 년대에 차이틴,콜모고로프,레빈,마르틴-엘,솔로모노프,그리고 솔로모노프에 의해 개발되었다. 주요 아이디어는 보편적 인 튜링 기계를 고려하는 것입니다 유 그리고 숫자(또는 문자열)의 복잡성을 측정 엑스 가장 짧은 입력의 길이 피 그런 유(피)출력 엑스. 이 접근법은 유한 객체에 대한 임의성 개념을 호출하여 무한 시퀀스(자연수의 하위 집합의 특성 함수)가 무작위인지 아닌지를 결정하는 이전 방법에 혁명을 일으켰습니다. 콜 모고 로프의 복잡성은 독립적 인 연구의 대상이되었다뿐만 아니라 증거를 얻기위한 도구로 다른 과목에 적용됩니다.이 분야에는 여전히 많은 열린 문제가 있습니다. 이러한 이유로,이 분야에서 최근 연구 회의는 2007 년 1 월에 개최 된 오픈 문제의 목록은 조셉 밀러와 안드레 니스에 의해 유지된다.
주파수 계산편집
이 재귀 이론은 다음과 같은 질문을 분석했습니다…,엑스 엔 튜플 엔 숫자 와이 1,와이 2,…,엔 그러한 적어도 미디엄 의 방정식 ㅏ(엑스 케이)=와이케 이 참입니다. 이러한 세트를(미디엄,엔)-재귀 세트. 이 재귀 이론의 첫 번째 주요 결과는 트라 크텐 브로트의 결과 집합이 계산 가능한 경우(미디엄,엔)-일부에 대한 재귀 미디엄,엔 2 미디엄>엔. 다른 한편으로,조 커쉬의 반수술 세트(조 커쉬가 1968 을 소개하기 전에 이미 비공식적으로 알려짐)는 세트의 예입니다(미디엄,엔)-재귀 적 그리고 경우에만 2 엠<엔+1. 이 집합에는 헤아릴 수 없을 정도로 많은 집합과 재귀 적으로 열거 할 수 있지만이 유형의 계산 불가능한 집합이 있습니다. 나중에 데그 테프는(1,엔+1)-재귀 적이지만(1,엔)-재귀 적이 아닌 재귀 적으로 열거 가능한 세트의 계층 구조를 확립했습니다. 러시아 과학자들의 오랜 연구 단계 후에,이 주제는 위에서 언급 한 제한된 환원성 및 기타 관련 개념과 주파수 계산을 연결 한 제한된 쿼리에 대한 베이겔의 논문에 의해 서구에서 다시 보급되었습니다. 주요 결과 중 하나는 커머의 카디널리티 이론은 그 집합은 계산 가능한 경우 및 경우에만 해당 해당 해당 알고리즘의 각 튜플에 대한 열거 엔 다른 숫자까지 엔 이 집합의 카디널리티의 많은 가능한 선택 엔 숫자 교차.; 이러한 선택은 진정한 카디널리티를 포함하지만 적어도 하나의 거짓 하나를 생략해야합니다.
귀납적 추론편집
이것은 학습 이론의 재귀-이론적분야이다. 1967 에서 한계에 학습의 마크 골드의 모델과 학습의 그 이후 점점 더 많은 모델을 개발했다. 일반적인 시나리오는 다음과 같습니다:주어진 클래스 에스 계산 가능한 함수의 학습자(즉,재귀 기능)는 폼의 모든 입력에 대해 출력합니다(에프(0),에프(1),…,에프(엔))가설. 학습자 미디엄 함수를 배운다 에프 거의 모든 가설이 동일한 인덱스 인 경우 이자형 의 에프 이전에 합의 된 것에 대해 허용 가능한 모든 계산 가능한 함수의 번호 매기기;미디엄 배운다 에스 만약 미디엄 배운다 모든 에프 에 에스. 많은 관련 모델을 고려 하 고 또한 긍정적인 데이터에서 재귀적으로 열거 가능한 집합의 클래스의 학습 골드의 선구적인 종이 1967 년 이후에서 공부 하는 주제입니다.
튜링 전산성의 일반화편집
재귀 이론은 산술 환원성,과산수 환원성,그리고 색스(1990)에 의해 설명 된 바와 같이,이 분야의 일반화 된 개념의 연구를 포함한다. 이러한 일반화 된 개념은 튜링 기계에 의해 실행될 수없는 환원성을 포함하지만 그럼에도 불구하고 튜링 환원성의 자연스러운 일반화입니다. 이러한 연구는 개별 숫자를 통해 정량화뿐만 아니라 자연수의 집합을 통해 정량화를 허용하여 산술 계층 구조와 다른 분석 계층 구조를 조사하는 방법을 포함한다. 예를 들어 무한 가지가없는 재귀(이진이 아닌)나무의 모든 지수 집합은 레벨에 대해 완료됩니다._{1}^{1}}
분석 계층 구조. 튜링 환원성 과 과다수 환원성 효과적인 설명 집합 이론 분야에서 중요합니다. 구성 가능성의 정도에 대한 더욱 일반적인 개념은 집합 이론에서 연구됩니다.
연속 계산성 이론편집
디지털 계산을 위한 계산성 이론이 잘 발달되어 있다. 계산성 이론은 아날로그 컴퓨터,아날로그 신호 처리,아날로그 전자,신경망 및 연속 시간 제어 이론에서 발생하는 아날로그 계산을 위해 덜 잘 개발되었으며,미분 방정식과 연속 동적 시스템으로 모델링되었습니다(오르포넨 1997;무어 1996).
