계산 가능성 이론 - 위키백과, 우리 모두의 백과사전 계산 가능성 이론 위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 재귀 이론은 여기로 연결됩니다. 다른 뜻에 대해서는 재귀 이론 ( 동음이의 ) 문서를 참조하십시오. 계산 가능성 이론 ( [UNK] [UNK] 可 能 性 理 論, 영어 : computability theory ) 또는 재귀 이론 ( [UNK] [UNK] 理 論, 영어 : recursion theory ) 은 수학기초론의 중요한 분야이자 컴퓨터 과학에서는 계산 이론의 한 갈래이다. 계산 가능성 이론의 기초는 가산 집합 상에서 함수의 해를 찾는 문제와 관련이 있다. 1930년대 불완전성 정리와 함께 람다 대수와 튜링 기계라는 계산 모형이 만들어지면서, 어떤 집합이 효율적으로 계산 가능한지의 문제는 실질적으로 그 집합을 효율적으로 계산해 내
지 않고도 계산 가능성을 증명할 수 있는 것이다. 이에 따라 대안적인 공리계를 모색하기 위한 이론적 토대가 마련되었고, 수리논리학과 증명론에서 직관주의가 입지를 공고히 했으며, 형 이론과 고차 논리, 자연 연역, 헤이팅 대수의 비약적 발전에 영향을 주었다. 계산 복잡도 이론에서는 계산 가능한 집합을 그 함수의 해를 찾는 효율적인 알고리즘에 의해 소모되는 시공간적 자원의 추세를 토대로 분류한다. 이에 따라 계산 복잡도 이론과 계산 가능성 이론 중 어느 쪽이 상위의 개념인지에 관해 다소 논쟁이 있다. 목차 1 소개 2 계산 모형 3 계산모형의 계산능력 3. 1 유한상태기계의 계산능력 3. 2 내리누름 오토마타의 계산능력 3. 3 튜링 기계의 계산능력 3. 3. 1 정지 문제 3. 3. 2 순환
서 모순이다. 따라서 정지 언어의 여집합은 순환 열거 언어가 아니다. 가상의 계산모형 [ 편집 ] 처치 - 튜링 명제를 통해, 튜링 기계보다 더 강력하면서 논리적인 모형은 없다고 추측할 수 있다. 그러나 비논리적인 모형은 생각할 수 있는데, 여기서 몇몇 모형을 살펴볼 것이다. 컴퓨터 과학자들은 많은 종류의 초계산기 ( hypercomputer ) 를 생각해냈다. 재귀 이론은 수리논리학의 한 갈래로 이런 계산 모형들을 엄밀하게 다룬다. 무한실행 [ 편집 ] 어떤 기계가 단계를 수행하는 데 전 단계의 반만큼의 실행 시간이 걸린다고 하자. 만일 처음 단계의 실행 시간을 1이라고 둔다면 총 실행시간은 1 1 2 1 4 [UNK] { [UNK] displaystyle 1 { 1 [UNK] over 2 } { 1 [UNK] over 4 } [UNK] cdot
일부 상태는 수락 ( accepting ) 상태로 정의되는데, 일련의 입력 끝에서 기계가 수락 상태에 있다면 해당 입력 전체를 수락한다. 내리누름 오토마타 정해지지 않은 크기를 가진 실행 스택을 가졌다는 것을 제외하고는 위의 유한 상태 기계와 거의 같다. 상태 천이는 기존의 기능 외에, 부가적으로 스택에 기호 ( symbol ) 를 추가하거나 [UNK] 수 있으며 스택 위의 기호에 따라 다른 상태로 이동할 수도 있다. 튜링 기계 입력 방식이 실행 테이프 ( tape ) 라는 점을 빼고는 내리누름 오토마타와 유사하다. 실행 테이프는 헤드 ( head ) 를 이동시키는 방식으로 읽고 쓰기를 수행하며 무한히 길다. 튜링 기계는 실제 기계와는 달리 유한성을 고려하지 않지만 컴퓨터 과학에서 가장 중요한 계산 모형이다
있다. 1930년대 불완전성 정리와 함께 람다 대수와 튜링 기계라는 계산 모형이 만들어지면서, 어떤 집합이 효율적으로 계산 가능한지의 문제는 실질적으로 그 집합을 효율적으로 계산해 내는 함수를 만들어 내는 것과 같은 일이 되었다. 계산 가능성 이론의 초기 성과는 이들 집합을 계산적으로 동치인 것들로 묶어 위계로 분류한 것이다. 수학적으로 유한히 정의된 함수를 계산 가능성에 따라 분류했을 때 어떤 함수의 계산 가능성 문제를 다른 함수 ( 다른 함수들 ) 의 문제로 환원할 수 있다는 것을 보임으로써, 굳이 알고리즘 자체를 증명에 끌어들이지 않고도 계산 가능성을 증명할 수 있는 것이다. 이에 따라 대안적인 공리계를 모색하기 위한 이론적 토대가 마련되었고, 수리논리학과 증명론에서 직관주의가 입지를 공고히 했으며
계산모형의 계산능력 3. 1 유한상태기계의 계산능력 3. 2 내리누름 오토마타의 계산능력 3. 3 튜링 기계의 계산능력 3. 3. 1 정지 문제 3. 3. 2 순환 언어를 넘어서 4 가상의 계산모형 4. 1 무한실행 4. 2 신탁 기계 4. 3 초월계산의 한계 5 계산가능성 이론의 역사 6 같이 보기 7 참고 문헌 소개 [ 편집 ] 컴퓨터 과학의 핵심과제는 컴퓨터로 푸는 문제들을 이해하여 연산장치의 한계를 밝히는 것이다. 현대의 연산장치는 거의 무한대의 계산능력을 지닌 것처럼 보인다. 그래서 충분한 시간이 있으면 우리는 어떤 문제든 컴퓨터로 풀 수 있을 거라고 생각하기 쉽다. 그러나 문제가 쉬워 보이고 또 엄청난 자원이 주어졌다고 해도 컴퓨터의 계산능력에는 한계가 있으며 한계성을 증명할 수 있다. 컴퓨터 과학자들
계산 모형은 유한 상태 기계보다 더 강력하다. 하지만 내리누름 오토마타로도 표현할 수 없는 언어가 있다. 정규 언어에서와 비슷하게 찾을 수 있는데, 예로는 소수의 집합이 있다 ( 상세히 설명하지는 않겠다. ) 정규 언어와 비슷하게, 문맥 자유 언어에 대한 펌핑 렘마도 있다. 튜링 기계의 계산능력 [ 편집 ] 튜링 기계는 모든 문맥 자유 언어를 표현할 수 있으며 내리누름 오토마타로 표현할 수 없는 언어도 표현할 수 있다. 예를 들어 소수로 이루어진 언어를 표현할 수 있다. 따라서 이 모형은 앞의 두 모형보다 더욱 강력하다. 튜링 기계는 자신의 입력 테이프에 내용을 저장하는 기능이 있기 때문에 긴 시간이 주어진다면 다른 계산 모형으로는 할 수 없었던 일들을 할 수 있다.
계산 문제 계산 가능성 이론의 주요 논문 참고 문헌 [ 편집 ] Michael Sipser, Introduction to the Theory of Computation, PWS Publishing ISBN 0 - 534 - 94728 - XPart Two : Computability Theory, chapters 3 - 6, pp. 123 - 222. Christos Papadimitriou, Computational Complexity, Addison Wesley ISBN 0 - 201 - 53082 - 1, Chapter 3 : Computability, pp. 57 - 70. vdeh집합론집합 원소 공집합 한원소 집합 부분 집합 교집합 합집합 여집합 대칭차 [UNK] ( [UNK] 공리 ) 곱집합 ( 순서쌍 ) 유한 집합 무한 집합 ( 무한 공리 ) 가산 집합 드 모르간의 법칙 함수 정의역 공역 치역 상 전사 함수 단사 함수 전단사
로 - [UNK] 집합론 새 기초론 폰 노이만 - 베르나이스 - 괴델 집합론 모스 - 켈리 집합론 선택 공리 가산 선택 공리 의존적 선택 공리 초른의 보조정리 슈필라인 확장정리 바나흐 - 타르스키 역설 티호노프 정리 집합론의 모형 구성 가능 전체 추이적 집합 추이적 모형 순서수 정의 가능 집합 강제법 큰 기수도달 불가능한 기수 · 가측 기수 · 약콤팩트 기수 · 강콤팩트 기수 · 초콤팩트 기수ZF와 독립된 명제 연속체 가설 특이 기수 가설 수슬린 가설 화이트헤드 문제 결정 공리 마틴 공리 다이아몬드 원리 vdeh컴퓨터 과학의 주요 분야수학적 기초 수리논리학 집합론 정수론 그래프 이론 형 이론 범주론 수치해석학 이산수학 계산 이론 오토마타 이론 계산 가능성 이론 계산 복잡도 이론 양자 계산 이론 알고리즘 & 자료 구조 알고리즘 알고리즘 설계 알고리즘 해석 자료 구조 계산기하학 프로그래밍 언어 & 컴파
을 가진 튜링 기계는 임의의 튜링 기계와 입력에 대해 정지 문제를 바로 판정할 수 있다. 초월계산의 한계 [ 편집 ] 이런 기계들이 기존의 한계를 벗어난 것처럼 보여도 다시 각각의 한계를 찾을 수 있다. 이런 기계들이 튜링 기계에 대한 정지 문제를 판정할 수는 있지만 그 기계들 사이의 정지 문제는 결정 불가능하다. 예를 들어 신탁 기계는 임의의 신탁 기계가 멈추는지 아닌지를 판정할 수 없다. 계산가능성 이론의 역사 [ 편집 ] 계산가능성 이론은 일차 논리에 그 뿌리를 두고 있으며, 정지 문제 및 재귀와 관련된 많은 문제들은 불완전성 정리와 밀접하게 연관되어 있다. 다비트 힐베르트와 쿠르트 괴델은 일차논리의 기초를 쌓았다. 계산가능성 이론에 앞서 알론조 처치와 스티븐 콜 클레이니 ( 영어 : St
계산 가능성 이론(計算可能性理論, 영어: computability theory) 또는 재귀 이론(再歸理論, 영어: recursion theory)은 수학기초론의 중요한 분야이자 컴퓨터 과학에서는 계산 이론의 한 갈래이다. 계산 가능성 이론의 기초는 가산 집합 상에서 함수의 해를 찾는 문제와 관련이 있다. 1930년대 불완전성 정리와 함께 람다 대수와 튜링 기계라는 계산 모형이 만들어지면서, 어떤 집합이 효율적으로 계산 가능한지의 문제는 실질적으로 그 집합을 효율적으로 계산해 내는 함수를 만들어 내는 것과 같은 일이 되었다. 계산 가능성 이론의 초기 성과는 이들 집합을 계산적으로 동치인 것들로 묶어 위계로 분류한 것이다. 수학적으로 유한히 정의된 함수를 계산 가능성에 따라 분류했을 때 어떤 함수의 계산 가능성 문제를 다른 함수(다른 함수들)의 문제로 환원할 수 있다는 것을 보임으로써, 굳이 알고리즘 자체를 증명에 끌어들이지 않고도 계산 가능성을 증명할 수 있는 것이다. 이에 따라 대안적인 공리계를 모색하기 위한 이론적 토대가 마련되었고, 수리논리학과 증명론에서 직관주의가 입지를 공고히 했으며, 유형 이론과 고차 논리, 자연 연역, 헤이팅 대수의 비약적 발전에 영향을 주었다. 계산 복잡도 이론에서는 계산 가능한 집합을 그 함수의 해를 찾는 효율적인 알고리즘에 의해 소모되는 시공간적 자원의 추세를 토대로 분류한다. 이에 따라 계산 복잡도 이론과 계산 가능성 이론 중 어느 쪽이 상위의 개념인지에 관해 다소 논쟁이 있다.