맨위로가기

계산 가능성 이론

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

계산 가능성 이론은 튜링 기계와 같은 계산 모델을 통해 문제를 해결하는 능력, 즉 계산 가능성을 연구하는 분야이다. 튜링 기계는 유한 상태 기계, 푸시다운 오토마타보다 강력한 계산 모델로, 정지 문제와 같은 계산 불가능한 문제의 존재를 보여준다. 계산 가능성 이론은 1930년대 앨런 튜링, 쿠르트 괴델 등에 의해 시작되었으며, 람다 계산법, 처치-튜링 명제 등 현대 컴퓨터 과학의 기초를 다지는 데 기여했다. 이 이론은 상대적 계산 가능성, 튜링 차수, 산술적 위계, 콜모고로프 복잡도 등 다양한 개념을 포함하며, 정의 가능성, 증명, 계산 가능성 간의 관계를 탐구한다. 또한 역수학, 귀납적 추론, 빈도 계산 등과 같은 분야와 연결되어 있으며, 전문 학회와 학술 대회를 통해 연구가 활발히 진행되고 있다.

더 읽어볼만한 페이지

  • 계산 가능성 이론 - 처치-튜링 논제
    처치-튜링 논제는 모든 효과적인 계산 과정이 튜링 기계로 수행될 수 있다는 가설로, 알고리즘과 계산 가능성의 본질에 대한 논의를 촉발하며 컴퓨터 과학과 철학 분야에서 활발히 연구되고 있다.
  • 계산 가능성 이론 - 튜링 기계
    튜링 기계는 앨런 튜링이 제시한 계산 모델로, 테이프 위에서 기계적으로 작동하며, 유한한 상태, 테이프, 헤드, 명령 표를 통해 작동하고, 계산 가능성과 알고리즘의 한계를 연구하는 데 사용된다.
  • 수학 - 회귀 분석
    회귀 분석은 종속 변수와 하나 이상의 독립 변수 간의 관계를 모델링하고 분석하는 통계적 기법으로, 최소 제곱법 개발 이후 골턴의 연구로 '회귀' 용어가 도입되어 다양한 분야에서 예측 및 인과 관계 분석에 활용된다.
  • 수학 - 수학적 최적화
    수학적 최적화는 주어진 집합에서 실수 또는 정수 변수를 갖는 함수의 최댓값이나 최솟값을 찾는 문제로, 변수 종류, 제약 조건, 목적 함수 개수에 따라 다양한 분야로 나뉘며 여러 학문 분야에서 활용된다.
계산 가능성 이론
개요
분야수학, 전산학
연구 대상계산 가능 함수 및 튜링 차수
역사적 맥락
배경수학기초론, 수리논리학
주요 개념계산가능성
결정 가능성
환원 가능성
튜링 완전성
주요 인물
주요 학자앨런 튜링
알론조 처치
쿠르트 괴델
스테판 클리니
에밀 포스트
핵심 개념
계산 가능성알고리즘적으로 계산 가능한 함수 및 문제의 속성
튜링 기계계산 가능성을 정의하는 데 사용되는 추상적인 계산 모델
튜링 차수계산 복잡도의 척도
주요 결과
처치-튜링 명제계산 가능한 함수는 튜링 기계로 계산 가능한 함수와 동일하다는 명제
정지 문제튜링 기계가 특정 입력에 대해 정지할지 여부를 결정하는 알고리즘이 존재하지 않는다는 문제
응용 분야
응용 분야전산학
수학
논리학
인공지능
참고 자료
참고 문헌Handbook of Recursive Mathematics

2. 계산 모형

계산 가능성 이론에서는 컴퓨터의 기능을 형식적으로 정의하기 위해 다양한 계산 모형을 사용한다. 대표적인 계산 모형은 다음과 같다.


  • '''결정적 유한 상태 기계''': 간단한 계산 모델로, 현재 사용되는 컴퓨터는 유한 상태 기계로 모델링할 수 있다.
  • '''푸시다운 오토마톤''': 유한 상태 기계와 유사하지만, 크기가 무한히 커질 수 있는 스택을 사용한다.
  • '''튜링 기계''': 유한 상태 기계와 유사하지만, 입력을 "테이프" 형태로 받으며, 읽고 쓰기가 가능하고 테이프를 앞뒤로 움직일 수 있다. 테이프의 크기는 무한하다. 튜링 기계는 컴퓨터 과학에서 가장 중요한 계산 모델이며, 자원 제약이 없는 계산을 시뮬레이션한다.


이 외에도 다양한 계산 모형이 존재하며, 이들은 컴퓨터 과학에서 중요한 역할을 한다.

2. 1. 유한 상태 기계 (결정적 유한 오토마타, DFA)

결정적 유한 오토마타(DFA), 간단히 유한 상태 기계는 비교적 간단한 계산 모형이다. 현존하는 모든 연산 장치들은 유한 상태 기계 모형으로 설명 가능하다. 유한 상태 기계는 상태, 입출력, 입력에 따른 상태 천이식으로 구성된다. 입력 장치에서 한 번에 문자 한 개를 전달하면, 현재 상태와 입력에 따라 상태 천이가 이루어진다. 만약 입력에 맞는 상태 천이가 존재한다면, 기계는 새로운 상태로 변하게 된다. 일부 상태는 수락(accepting영어) 상태로 정의되는데, 일련의 입력이 끝났을 때 기계가 수락 상태에 있다면 해당 입력 전체를 수락한다.

컴퓨터 과학자들은 유한 상태 기계가 받아들일 수 있는 언어를 정규 언어라고 한다. 유한 상태 기계에서 가능한 상태는 유한하다. 따라서 어떤 언어가 정규 언어가 아니라는 것을 보이려면, 그 언어를 표현하기 위해 무한개의 상태가 필요하다는 것을 보여야 한다.

예를 들어 a와 b를 같은 개수만큼 포함하는 문자열들의 집합을 생각해 보자. 이 언어가 유한 상태 기계로 다룰 수 없다는 것을 보이기 위해 그런 기계 M이 있다고 가정한다. M은 유한하므로 상태의 수를 n개라고 할 수 있다. 한편 a가 (n+1)개, 뒤에 b가 (n+1)개 있는 문자열 x를 생각하자.

기계 M이 문자열 x를 읽으면, 문자열 'a'를 읽을 때 적어도 한 상태를 두 번 거치게 된다. 'a'가 (n+1)개 있고 상태가 n개 있으므로 비둘기집 원리를 적용할 수 있기 때문이다. 이 상태를 S라고 하자. 그리고 상태 S가 처음 나온 때부터 두 번째 등장할 때까지 읽은 'a'의 개수를 d라고 하자. 즉, S에서 d만큼의 'a'를 받아들였을 때 다시 S 상태가 된다는 것이고, 따라서 기계가 (n+d+1)개의 'a' 문자를 읽든 (n+1)개의 'a'를 읽든 최종 상태는 같다. 이는 곧 기계가 문자열 x를 받아들인다면, (n+d+1)개의 'a'와 (n+1)개의 'b'로 구성된 문자열도 받아들인다는 것이다. 이것은 M이 'a'와 'b'가 같은 개수인 문자열만 받아들인다는 점에서 모순이다.

따라서 이 언어는 어떤 유한 상태 기계로도 표현할 수 없으며, 따라서 정규 언어가 아니다. 더 일반적인 형태로 보이기 위해 정규 언어에 대한 펌핑 렘마를 쓰는데, 많은 언어들이 유한 상태 기계로 나타낼 수 없다는 것을 보이는 데 쓰인다.

이러한 결과는 의아하게 생각될 수 있다. 이러한 언어를 인식하는 프로그램을 컴퓨터로 작성하는 것은 매우 쉽기 때문이다. 하지만 앞서 데스크톱 PC 등 현존하는 모든 컴퓨터들이 유한 상태 기계라고 언급하였다. 이는 컴퓨터에도 메모리 용량 같은 제한이 존재하기 때문이다. 문자열의 길이가 길어지면 문자의 개수를 세는 데 컴퓨터의 메모리 용량을 다 쓸 것이고, 결국 용량이 부족하여 오버플로우가 발생할 것이다. 아무리 많은 문자열을 인식할 수 있다고 해도 결국 인식할 수 없는 문자열이 존재한다. 이러한 사실은 정규 언어가 어떻게 데스크톱 PC 등에 적용되는지를 이해하는 데 도움을 준다.

2. 2. 푸시다운 자동 기계 (내리누름 오토마타)

내리누름 오토마타는 유한 상태 기계와 비슷하지만, 임의의 크기로 성장 가능한 실행 스택을 이용할 수 있다는 점이 다르다. 상태 천이 시에 기호를 스택에 쌓거나 스택에서 기호를 제거하는 것을 지정할 수 있다.

푸시다운 오토마타가 수용하는 언어의 클래스를 '''문맥 자유 언어'''라고 부르며, '''문맥 자유 문법'''에 의해 기술된다. 정규 언어가 아닌 'a'와 'b'를 같은 수만큼 포함하는 문자열로 구성된 언어는 푸시다운 오토마톤으로 판별할 수 있다. 또한 일반적으로, 푸시다운 오토마톤을 유한 상태 기계처럼 작동시킬 수도 있으므로, 정규 언어도 판별할 수 있다. 따라서 이 계산 모델은 유한 상태 기계보다 강력하다.

그러나, 푸시다운 오토마톤으로도 판별할 수 없는 언어가 있다. 문맥 자유 언어의 반복 보조정리를 통해 찾을 수 있으며, 예를 들어 소수의 집합이 이에 해당한다.

2. 3. 튜링 기계

유한 상태 기계에 무한한 길이의 테이프를 추가한 계산 모형이다. 테이프에 정보를 읽고 쓸 수 있으며, 헤드를 움직여 테이프의 위치를 조작할 수 있다. 현존하는 가장 강력한 계산 모형으로 알려져 있으며, 컴퓨터 과학에서 가장 중요한 계산 모형이다. 튜링 기계는 실제 기계와 달리 유한성을 고려하지 않지만, 계산 가능성의 한계를 연구하는 데 중요한 도구이다.

튜링 기계는 내리누름 오토마타와 유사하지만, 입력 방식을 실행 테이프(tape영어)를 통해 받는다는 차이점이 있다. 실행 테이프는 헤드(head영어)를 통해 읽고 쓰기가 가능하며, 헤드를 움직여 테이프의 위치를 조작할 수 있으며 무한히 길다.

튜링 기계는 모든 문맥 자유 언어를 표현할 수 있으며, 내리누름 오토마타로 표현할 수 없는 언어(예: 소수로 이루어진 언어)도 표현할 수 있다. 따라서 튜링 기계는 더 강력한 모형이다.

튜링 기계는 입력 테이프에 내용을 저장할 수 있기 때문에, 시간이 충분히 주어진다면 다른 계산 모형으로는 불가능한 작업도 수행할 수 있다. 그러나 튜링 기계는 특정 입력에 대해 영원히 멈추지 않을 수 있다. 모든 입력에 대해 멈추고 결과를 출력하는 튜링 기계를 '''결정한다'''고 하며, 해당 언어를 순환 언어라고 한다. 튜링 기계가 언어의 원소에 대해서는 항상 멈추고 결과를 출력하지만, 언어 외부의 문자열에 대해서는 멈추지 않을 수 있는 경우, 해당 언어를 순환 열거 언어라고 한다.

많은 사람들이 튜링 기계보다 강력한 기계를 만들려고 노력했지만, 모두 실패했다. 예를 들어, 튜링 기계의 테이프 수를 늘려 2차원 또는 3차원 무한 영역으로 확장하더라도, 이는 1차원 테이프로 구현할 수 있다. 이러한 모형들은 튜링 기계보다 편리할 수는 있지만, 더 강력하지는 않다. 사실상 튜링 기계 이상의 합리적인 계산 모형이 없다는 것은 처치-튜링 명제를 통해 추측할 수 있다. 튜링 기계 이상의 기능을 갖는 계산 모형들이 많이 제안되었지만, 대체로 비현실적이거나 비합리적이다.

3. 계산 모형의 계산 능력

각 계산 모형은 특정한 종류의 형식 언어를 인식할 수 있다는 점에서 그 한계를 파악할 수 있다. 라이스는 모든 비자명 집합 ''C''에 대해, 정지 문제 또는 그 여집합이 ''E''로 다대일 환원 가능하도록 하는 속성을 가진 인덱스 집합 ''E''가 존재함을 보였다. (자세한 내용은 라이스 정리 참조).

그러나 이러한 인덱스 집합 중 상당수는 정지 문제보다 훨씬 더 복잡하다. 이러한 유형의 집합은 산술적 위계를 사용하여 분류할 수 있다. 예를 들어, FIN(모든 유한 집합의 클래스)의 인덱스 집합은 Σ2 레벨에 있고, REC(모든 재귀적 집합의 클래스)와 COFIN(모든 공유한 집합)의 인덱스 집합은 Σ3 레벨에 있으며, COMP(모든 튜링 완전 집합의 클래스)의 인덱스 집합은 Σ4 레벨에 있다. 이러한 위계 레벨은 귀납적으로 정의되며, Σ''n''+1은 Σ''n''에 상대적으로 계산 가능한 열거 가능한 모든 집합을 포함한다. Σ1은 계산 가능한 열거 가능한 집합을 포함한다. 여기에 주어진 인덱스 집합은 해당 레벨에 대해 완전하며, 즉 이러한 레벨의 모든 집합은 주어진 인덱스 집합으로 다대일 환원될 수 있다.

각 계산 모형별로 인식(계산) 가능한 언어는 다음과 같다.

3. 1. 유한 상태 기계의 계산 능력

컴퓨터 과학에서 유한 상태 기계(FSM)는 유한한 개수의 상태를 가지며, 입력에 따라 한 상태에서 다른 상태로 전환하며 정해진 출력을 생성하는 계산 모델이다. 유한 상태 기계가 인식할 수 있는 언어를 정규 언어라고 한다.

예를 들어, 'a'와 'b'가 같은 개수만큼 포함된 문자열의 집합은 정규 언어가 아니다. 이를 증명하기 위해, 그러한 언어를 인식하는 유한 상태 기계 M이 존재한다고 가정한다. M은 유한한 상태 수 n을 가진다. 이제 a가 (n+1)개, b가 (n+1)개인 문자열 x를 생각해보자.

M이 x를 읽을 때, 비둘기집 원리에 의해 'a'를 읽는 동안 적어도 한 상태 S를 두 번 거치게 된다. S에서 처음 S로 돌아올 때까지 읽은 'a'의 개수를 d라고 하면, M은 (n+1)개의 'a'를 읽었을 때와 (n+d+1)개의 'a'를 읽었을 때 같은 상태가 된다. 즉, M은 x뿐만 아니라 (n+d+1)개의 'a'와 (n+1)개의 'b'로 구성된 문자열도 받아들이게 된다. 이는 M이 'a'와 'b'의 개수가 같은 문자열만 받아들인다는 가정에 모순된다.

따라서 'a'와 'b'가 같은 개수만큼 포함된 문자열의 집합은 유한 상태 기계로 표현할 수 없으며, 정규 언어가 아니다. 정규 언어의 반복 보조정리를 사용하면 더 많은 언어가 유한 상태 기계로 표현 불가능함을 보일 수 있다.

일반적으로 컴퓨터 프로그램으로 이러한 언어를 인식하는 것은 어렵지 않다. 하지만, 데스크톱 PC와 같은 현대 컴퓨터는 메모리 용량과 같은 제한이 있는 유한 상태 기계이다. 매우 긴 문자열을 처리할 때 메모리 용량이 부족해져 오버플로우가 발생할 수 있다. 즉, 인식할 수 없는 문자열이 항상 존재한다.

3. 2. 푸시다운 자동 기계의 계산 능력

컴퓨터 과학자들은 내리누름 오토마타로 받아들일 수 있는 언어를 문맥 자유 언어라 정의한다. 이 언어는 문맥 자유 문법으로도 표현할 수 있다. 'a'와 'b'가 같은 개수만큼 있는 언어는 정규 언어가 아니지만, 내리누름 오토마타로는 표현할 수 있다. 일반적으로 내리누름 오토마타는 유한 상태 기계처럼 동작할 수 있으므로 정규 언어를 받아들인다. 그러므로 이 계산 모형은 유한 상태 기계보다 더 강력하다.

하지만 내리누름 오토마타로도 표현할 수 없는 언어가 있다. 정규 언어에서와 비슷하게 찾을 수 있는데, 예로는 소수의 집합이 있다. (상세히 설명하지는 않겠다.) 정규 언어와 비슷하게, 문맥 자유 언어에 대한 펌핑 렘마도 있다.

3. 3. 튜링 기계의 계산 능력

튜링 기계는 모든 문맥 자유 언어를 판별할 수 있을 뿐만 아니라, 푸시다운 오토마타로는 판별할 수 없는 언어(예: 소수로 이루어진 언어)도 판별할 수 있다. 따라서 튜링 기계는 더 강력한 계산 모형이다.

튜링 기계는 입력 테이프에 내용을 저장하는 기능("백업")이 있기 때문에, 다른 계산 모형으로는 불가능한 방식으로 작동할 수 있다. 어떤 입력에 대해서는 영원히 멈추지 않는 튜링 기계를 만들 수도 있다. 모든 입력에 대해 멈춰서 결과를 출력하는 튜링 기계가 판별하는 언어를 '''순환 언어'''라고 한다. 어떤 언어에 포함된 문자열에 대해서는 항상 멈추고 결과를 출력하지만, 그 언어에 포함되지 않는 문자열에 대해서는 멈추지 않을 수도 있는 튜링 기계가 판별하는 언어를 '''순환 열거 언어'''라고 한다.

튜링 기계는 매우 강력한 계산 모형이다. 튜링 기계의 정의를 수정하여 더 강력한 모형을 만들려는 시도는 실패했다. 예를 들어, 테이프를 2차원이나 3차원으로 확장하거나, 여러 개의 테이프를 가진 튜링 기계를 만들 수 있지만, 모두 1차원 테이프 하나를 가진 튜링 기계로 시뮬레이션할 수 있다. 즉, 이 모형들의 능력은 일반적인 튜링 기계와 같다. 사실상 튜링 기계 이상의 합리적인 계산 모형은 없다는 처치-튜링 명제가 제기되었다. 튜링 기계보다 강력하다고 주장하는 계산 모형들이 제안되었지만, 대체로 비현실적이거나 비합리적이다.

4. 계산 불가능성

컴퓨터 과학의 주요 목표는 컴퓨터를 사용하여 문제를 해결할 때 연산 장치의 한계를 파악하는 것이다. 현대의 연산 장치는 매우 강력해 보이지만, 충분한 시간과 자원이 주어져도 컴퓨터의 계산 능력에는 한계가 있으며, 이는 증명 가능하다.

컴퓨터 과학자들은 컴퓨터가 특정 형식 언어에 속하는 문자열을 판별할 수 있는지 연구한다. 예를 들어, 소수 길이의 문자열 집합이나 회문 집합과 같은 문제를 다룬다.

계산 가능성 이론은 특정 문제가 컴퓨터로 해결하기 얼마나 어려운지를 정의하고 정형화한다. 컴퓨터 과학에서 중요한 문제 중 하나는 정지 문제인데, 이는 주어진 튜링 기계와 입력에 대해 튜링 기계가 유한 시간 안에 계산을 끝내고 멈출지, 아니면 영원히 멈추지 않을지를 판별하는 문제이다.

정지 문제와 라이스의 정리는 계산 불가능성, 즉 결정 불가능성을 보여주는 대표적인 예시이다.

계산 가능성 이론은 1930년대 쿠르트 괴델, 앨런 튜링, 스티븐 클레이니, 에밀 포스트의 연구로 시작되었다. 이들은 튜링 계산 가능성을 효과적인 계산이라는 개념의 올바른 형식화로 확립했다. 1952년, 클레이니는 "처치의 명제"와 "튜링의 명제"를 만들었고, 이는 오늘날 처치-튜링 명제로 알려져 있다. 이 명제는 알고리즘으로 계산 가능한 모든 함수는 계산 가능한 함수임을 명시한다.

1936년, 처치와 튜링은 결정 문제가 효과적으로 결정될 수 없다는 것을 독립적으로 증명했다. 이는 임의의 수학적 명제가 참인지 거짓인지 결정하는 알고리즘 절차가 없음을 보여준다. 이후 많은 수학 문제가 결정 불가능한 것으로 나타났다. 1947년, 마르코프와 포스트는 반군에 대한 단어 문제가 효과적으로 결정될 수 없음을 보였다. 1950년대에 표트르 노비코프와 윌리엄 분은 군에 대한 단어 문제가 효과적으로 해결될 수 없음을 보였다. 1970년, 유리 마티야세비치는 마티야세비치의 정리를 증명하여 힐베르트의 열 번째 문제가 효과적인 해를 갖지 않음을 보였다.

각 계산 단계가 이전 단계의 절반 시간만 걸리는 기계를 통해 정지 문제를 판정할 수 있다.

4. 1. 정지 문제

튜링 기계와 입력이 주어졌을 때, 튜링 기계가 이 입력에 대해 유한시간 내에 계산을 끝내고 멈출 것인지 아니면 영원히 멈추지 않을 것인지를 판별하는 문제이다. 이는 평소에 컴퓨터가 어떻게 다루어지는가와, 계산 가능성 이론에 대한 핵심적인 부분을 다루고 있다.

정지 문제는 회문이나 소수 판별과 같은 단순한 문제와는 달리, 튜링 기계가 다른 튜링 기계에 대한 물음에 답해야 한다. 이러한 동작을 하는 튜링 기계를 설계하는 것은 불가능하다.

주어진 프로그램이 어떤 입력에 대해 정지하는지 알아내는 일반적인 방법은 단순히 작동시켜보고 멈추는지 확인하는 것뿐이다. 멈춘다면 그 기계가 멈춘다는 것을 알 수 있지만, 멈추지 않는다면 이 기계가 언젠가 멈출지 아닐지는 알 수 없다. 튜링 기계와 그 기계를 멈추는 입력의 모든 순서쌍 집합인 정지 언어는 순환 언어가 아니다. 따라서 정지 문제는 '''계산 불가능''' 또는 '''결정 불가능'''하다.

정지 문제를 확장한 라이스의 정리에 따르면, 어떤 튜링 기계가 수락하는 언어가 자명하지 않은 성질을 가지는지 아닌지는 결정 불가능하다.

4. 2. 순환 언어를 넘어서

정지 문제에 대응되는 언어는 순환 열거 언어이다. 튜링 기계를 작동시켰을 때 그 입력에 대해 멈춘다면 기계가 멈춘다는 사실을 그 시점에서 알 수 있기 때문이다. 그러나 순환 열거 언어조차 아닌 언어도 존재한다.

순환 열거 언어가 아닌 언어로는 정지 언어의 여집합(튜링 기계와 그 기계를 멈추지 않는 입력의 모든 순서쌍 집합)이 있다. 이 언어가 순환 열거 언어가 아니라는 것을 보이기 위해, 멈추는 튜링 기계를 입력으로 받으면 영원히 멈추지 않고 나머지 경우에는 항상 멈추는 튜링 기계 M이 있다고 가정한다. 그러면 시분할 기법을 이용하여 튜링 기계를 입력으로 하여 M을 동작시키면서 동시에 입력으로 받은 기계를 동작시키는 기계 M'을 만들 수 있다. 만약 입력된 튜링 기계가 멈추지 않는다면 M이 멈추고, 만일 입력된 튜링 기계가 멈춘다면 M'에서 입력으로 받은 기계를 동작시키는 부분이 멈출 것이다. 즉, M'의 두 스레드 중 적어도 하나는 멈춘다. 따라서 M'은 정지 문제를 판정할 수 있는 기계이며, 이것은 정지 문제가 결정 불가능하다는 데서 모순이다. 따라서 정지 언어의 여집합은 순환 열거 언어가 아니다.

5. 가상의 계산 모형

처치-튜링 명제에 따르면, 튜링 기계보다 강력하면서 논리적인 모형은 없다고 추측된다. 그러나 비논리적인 모형은 생각할 수 있는데, 컴퓨터 과학자들은 여러 종류의 초계산기(hypercomputer영어)를 고안해냈다. 재귀 이론은 수리논리학의 한 갈래로 이런 계산 모형들을 엄밀하게 다룬다.

계산 가능성 이론의 이 분과는 0 < ''m'' < ''n''인 고정된 ''m''과 ''n''에 대해, 서로 다른 ''n''개의 입력 ''x''1, ''x''2, ..., ''xn''에 대해 최소한 ''m''개의 방정식 ''A''(''xk'') = ''yk''가 참이 되도록 하는 ''n''개의 숫자 튜플 ''y1, y2, ..., yn''을 계산할 수 있는 함수 ''A''가 무엇인지 분석한다. 이러한 집합은 (''m'', ''n'')-재귀적 집합으로 알려져 있다. 이 분야의 초기 주요 결과는 2''m'' > ''n''인 일부 ''m'', ''n''에 대해 집합이 (''m'', ''n'')-재귀적이면 계산 가능하다는 Trakhtenbrot의 결과이다. 반면에 Jockusch의 준재귀적 집합은 2''m'' < ''n'' + 1인 경우에만 (''m'', ''n'')-재귀적인 집합의 예이다. 이러한 집합은 셀 수 없이 많으며, 계산 가능하지만 계산 불가능한 집합도 있다. Degtev는 (1, ''n'' + 1)-재귀적이지만 (1, ''n'')-재귀적이지 않은 계산 가능 열거 집합의 계층을 확립했다. 이후 Beigel의 제한된 쿼리에 대한 논문을 통해 주파수 계산을 위에서 언급한 제한된 환원 가능성과 기타 관련 개념과 연결하면서 다시 주목받게 되었다. Kummer의 기수 이론은 집합 ''A''가 계산 가능하기 위한 필요충분조건은 어떤 알고리즘이 ''A''와 교차하는 ''n''개의 숫자의 집합의 기수에 대해 최대 ''n''개의 가능한 선택 사항을 각기 다른 ''n''개의 숫자 튜플에 대해 열거하는 ''n''이 존재한다는 것이다. 이러한 선택 사항에는 참인 기수가 포함되어야 하지만 적어도 하나의 거짓 기수는 제외해야 한다.

5. 1. 무한 실행

처치-튜링 명제에 따르면, 튜링 기계보다 강력하면서 논리적인 모형은 없다고 추측된다. 그러나 비논리적인 모형은 생각해 볼 수 있다. 어떤 기계가 한 단계를 수행하는 데 걸리는 시간이 이전 단계의 절반이라고 가정해 보자. 만약 첫 단계 실행 시간을 1이라고 하면, 총 실행 시간은 다음과 같다.

:1 + {1 \over 2} + {1 \over 4} + \cdots

이 무한급수는 2로 수렴하므로, 이 튜링 기계는 2라는 실행 시간 안에 무한히 실행할 수 있다. 이러한 방식으로 '무한히' 실행해 보면 정지 문제를 판정할 수 있다.

5. 2. 신탁 기계

신탁 기계는 결정 불가능한 문제를 풀어내는 특정한 '신탁'에 접속할 수 있는 튜링 기계이다. 예를 들어 '정지 신탁'을 가진 튜링 기계는 임의의 튜링 기계와 입력에 대해 정지 문제를 바로 판정할 수 있다.

5. 3. 초월 계산의 한계

처치-튜링 명제에 따르면 튜링 기계보다 강력한 계산 모델은 존재하지 않는다고 추측된다. 그러나 컴퓨터 과학자들은 슈퍼컴퓨터보다 더 고성능이라는 의미가 아닌, 다양한 "하이퍼컴퓨터"를 상상해왔다.

이러한 기계에도 한계는 존재한다. 어떤 튜링 머신의 정지 문제를 풀 수 있더라도, 그러한 기계 자체의 정지 문제는 풀 수 없다. 즉, 오라클 머신은 어떤 오라클 머신이 정지할지 여부에 답할 수 없다.

6. 계산 가능성 이론의 역사와 발전

계산 가능성 이론은 1930년대 쿠르트 괴델, 앨런 튜링, 스티븐 클레이니, 에밀 포스트 등의 연구로 시작되었다. 이들은 튜링 계산 가능성이 효과적인 계산이라는 개념을 올바르게 형식화한 것임을 보였다. 1952년, 클레이니는 이를 "처치의 명제"와 "튜링의 명제"라고 명명했다. 오늘날에는 이 두 명제를 합쳐 처치-튜링 명제라고 부르며, 알고리즘으로 계산 가능한 모든 함수는 계산 가능한 함수라는 내용을 담고 있다. 1946년, 괴델은 이 명제를 지지하며, 이 개념이 특정 형식주의에 의존하지 않는 절대적인 개념이라는 점을 강조했다.

1936년, 알론조 처치와 앨런 튜링은 쿠르트 괴델의 불완전성 정리 증명 기법에서 영감을 받아 결정 문제가 효과적으로 결정될 수 없다는 것을 독립적으로 증명했다. 이는 임의의 수학적 명제가 참인지 거짓인지 판별하는 알고리즘적 절차가 없음을 보여준다.

이론 전산학의 주요 과제 중 하나는 컴퓨터로 풀 수 있는 문제의 범위를 이해하여 컴퓨터의 한계를 파악하는 것이다. 흔히 컴퓨터는 무한한 계산 능력을 가진 것처럼 보이지만, 앨런 튜링이 제시한 튜링 기계의 정지 문제에 대한 부정적인 해결책은 그렇지 않음을 보여준다.

계산 가능성 이론에서는 "주어진 형식 언어와 문자열이 있을 때, 그 문자열이 해당 언어에 포함되는가?"라는 질문에 답함으로써 컴퓨터의 능력을 밝힌다. 예를 들어, 소수만을 포함하는 언어가 있을 때, 입력된 문자열이 소수인지 판별하는 문제가 이에 해당한다.

이러한 문제의 난이도를 정형화하고 정의하는 것이 계산 가능성 이론의 목표이다. 이를 위해 "컴퓨터"를 형식적으로 정의해야 하는데, 대표적인 계산 모델은 다음과 같다.


  • 결정적 유한 상태 기계: 간단한 계산 모델로, 현재 사용되는 컴퓨터를 모델화할 수 있다.
  • 푸시다운 오토마톤: 스택을 사용할 수 있다는 점이 유한 상태 기계와 다르다.
  • 튜링 기계: 입력이 "테이프" 형태로 주어지며, 읽고 쓰기가 가능하고 테이프를 이동할 수 있다. 자원 제약 없는 계산을 시뮬레이션하는 중요한 모델이다.


앨런조 처치와 스티븐 콜 클리니가 개발한 람다 계산법은 계산 가능성 이론 정립에 중요한 역할을 했다. 앨런 튜링은 튜링 기계를 제안하고 정지 문제를 해결하는 등 현대 전산학의 기초를 다졌다.

6. 1. 상대적 계산 가능성과 튜링 차수

계산 가능성 이론의 연구 분야는 튜링 환산 외의 다른 환산 관계를 연구한다. 포스트는 진리표 환산을 암시하는 여러 "강한 환산"을 도입했는데, 강한 환산을 구현하는 튜링 기계는 어떤 오라클이 주어지든 전체 함수를 계산한다. 반면 "약한 환산"은 모든 오라클에 대해 환산 과정이 종료되지 않을 수 있는 경우를 말하며, 튜링 환산이 그 예이다.

강한 환산에는 다음이 포함된다.

환산 종류설명
일대일 환산각 n이 A에 있고, 그 때와 그 때만 f(n)이 B에 있는, 전체 계산 가능한 단사 함수 f가 존재하면 A는 B로 일대일 환산(또는 1-환산)된다.
다대일 환산f가 단사 함수여야 한다는 제약이 없는 일대일 환산과 본질적으로 같다. 각 n이 A에 있고, 그 때와 그 때만 f(n)이 B에 있는, 전체 계산 가능한 함수 f가 존재하면 A는 B로 다대일 환산(또는 m-환산)된다.
진리표 환산A는 주어진 오라클에 관계없이 전체 함수를 계산하는 오라클 튜링 기계를 통해 A가 B로 튜링 환산 가능하면 B로 진리표 환산 가능하다. 칸토어 공간의 컴팩트성으로 인해, 이는 환산이 오라클에 단일 질문 목록(입력에만 의존)을 동시에 제시한 다음, 응답을 보고 초기 질의에 대한 오라클의 응답에 관계없이 추가 질문을 하지 않고 출력을 생성할 수 있다고 말하는 것과 동일하다.



환산 (계산 가능성 이론) 기사에서는 긍정적, 선언적, 연언적, 선형 및 약한 버전과 경계 버전 등 다양한 환산들을 다룬다.

강한 환산에 대한 주요 연구는 모든 계산 가능한 열거 가능 집합의 클래스와 자연수의 모든 부분 집합의 클래스 모두에 대해 그들의 이론을 비교하는 것이었다. 또한 환산 간의 관계도 연구되었는데, 예를 들어 모든 튜링 차수는 진리표 차수이거나 무한히 많은 진리표 차수의 합이라는 것이 알려져 있다.

튜링 환산보다 약한 환산(즉, 튜링 환산에 의해 암시되는 환산)도 연구되었는데, 가장 잘 알려진 것은 산술적 환산과 초산술적 환산이다. 이러한 환산은 산술 표준 모델에 대한 정의 가능성과 밀접하게 관련되어 있다.

로저스는 계산 가능성 이론의 핵심 속성은 그 결과와 구조가 자연수에 대한 계산 가능한 전단사에 불변해야 한다는 점을 제시했다. 이는 계산 가능한 전단사가 집합 내의 구조를 나타내는 것이 아니라 집합 내의 숫자의 이름을 바꾸는 것일 뿐이라는 아이디어에 기반한다.

6. 2. 라이스 정리와 산술적 계층

극대 집합(앞 문단에서 정의됨)은 극대 집합이 아닌 집합과 자기 동형일 수 없다는 속성을 갖는다. 즉, 위에서 언급한 구조 하에서 계산 가능 열거 집합의 자기 동형 사상이 존재한다면, 모든 극대 집합은 다른 극대 집합으로 매핑된다. 1974년, 소어(Soare)는 그 역도 성립한다는 것을 보였다. 즉, 모든 두 극대 집합은 자기 동형이다. 따라서 극대 집합은 궤도를 형성하며, 모든 자기 동형 사상은 극대성을 보존하고, 임의의 두 극대 집합은 어떤 자기 동형 사상에 의해 서로 변환된다. 해링턴(Harrington)은 자기 동형 속성의 또 다른 예로 창의적 집합, 즉 정지 문제에 다대일 동치인 집합을 제시했다.

6. 3. 우선순위 방법 (The priority method)

우선순위 방법(The priority method영어)은 특정 속성을 가진 계산 가능 열거 집합을 구성하는 방법으로, Post의 문제 해결에 사용된다.

6. 4. 콜모고로프 복잡도 (Kolmogorov complexity)

콜모고로프 복잡도와 알고리즘적 무작위성 분야는 1960년대와 1970년대에 차이틴(Chaitin), 콜모고로프(Kolmogorov), 레빈(Levin), 마틴-뢰프(Martin-Löf), 솔로모노프(Solomonoff)에 의해 발전했다(이름은 알파벳순으로 나열되었으며, 연구의 상당 부분은 독립적으로 이루어졌고, 당시에는 무작위성 개념의 통일성이 이해되지 않았다). 주요 아이디어는 보편 튜링 기계 ''U''를 고려하고 숫자(또는 문자열) ''x''의 복잡성을 ''U''(''p'')가 ''x''를 출력하는 가장 짧은 입력 ''p''의 길이로 측정하는 것이다. 이러한 접근 방식은 유한 객체에 대한 무작위성의 개념을 적용하여 무한 시퀀스(동등하게, 자연수 부분 집합의 특성 함수)가 무작위인지 여부를 결정하는 이전 방식을 혁신했다. 콜모고로프 복잡도는 독립적인 연구 대상이 되었을 뿐만 아니라 증명을 얻기 위한 도구로서 다른 주제에도 적용된다. 이 분야에는 여전히 많은 미해결 문제가 있다.

6. 5. 빈도 계산 (Frequency computation)

계산 가능성 이론의 이 분과는 0 < ''m'' < ''n''인 고정된 ''m''과 ''n''에 대해, 서로 다른 ''n''개의 입력 ''x''1, ''x''2, ..., ''xn''에 대해 최소한 ''m''개의 방정식 ''A''(''xk'') = ''yk''가 참이 되도록 하는 ''n''개의 숫자 튜플 ''y1, ''y''2, ..., ''yn''을 계산할 수 있는 함수 ''A''가 무엇인지 분석한다. 이러한 집합은 (''m'', ''n'')-재귀적 집합으로 알려져 있다. 이 분과에서 나온 첫 번째 주요 결과는 2''m'' > ''n''인 일부 ''m'', ''n''에 대해 집합이 (''m'', ''n'')-재귀적이면 계산 가능하다는 Trakhtenbrot의 결과이다. 반면에 준재귀적 집합(1968년 Jockusch가 소개하기 전 비공식적으로 알려짐)은 2''m'' < ''n'' + 1인 경우에만 (''m'', ''n'')-재귀적인 집합의 예이다. 이러한 집합은 셀 수 없이 많으며, 계산 가능하지만 계산 불가능한 집합도 있다. Degtev는 (1, ''n'' + 1)-재귀적이지만 (1, ''n'')-재귀적이지 않은 계산 가능 열거 집합의 계층을 확립했다. 러시아 과학자들의 오랜 연구 후, 이 주제는 Beigel의 제한된 쿼리에 대한 논문을 통해 서구에서 다시 인기를 얻었는데, 이는 주파수 계산을 제한된 환원 가능성 및 기타 관련 개념과 연결했다. 주요 결과 중 하나는 Kummer의 기수 이론으로, 집합 ''A''가 계산 가능하기 위한 필요충분조건은 어떤 알고리즘이 ''A''와 교차하는 ''n''개의 숫자의 집합의 기수에 대해 최대 ''n''개의 가능한 선택 사항을 각기 다른 ''n''개의 숫자 튜플에 대해 열거하는 ''n''이 존재한다는 것이다. 이러한 선택 사항에는 참인 기수가 포함되어야 하지만 적어도 하나의 거짓 기수는 제외해야 한다.

6. 6. 귀납적 추론 (Inductive inference)

E. 마크 골드가 1967년에 제시한 한계 학습 모델을 기반으로 하는, 학습 이론의 계산 가능성 이론 분야이다. 이후 더욱 다양한 학습 모델로 발전해 왔다.

일반적인 시나리오는 다음과 같다. 계산 가능한 함수 클래스 ''S''가 주어졌을 때, (''f''(0), ''f''(1), ..., ''f''(''n'')) 형태의 모든 입력을 받아서 가설을 출력하는 학습자(계산 가능한 함수)가 존재하는가? 학습자 ''M''은 거의 모든 가설이 미리 합의된 모든 계산 가능한 함수의 허용 가능한 번호 매김에 따라 함수 ''f''의 동일한 인덱스 ''e''인 경우 함수 ''f''를 학습한다. ''M''은 ''S''에 있는 모든 ''f''를 학습하면 ''S''를 학습한다.

기본적인 결과는 함수들의 모든 계산 가능한 열거 가능한 클래스는 학습 가능하지만, 모든 계산 가능한 함수들의 클래스 REC는 학습 불가능하다는 것이다. 많은 관련 모델들이 고려되었으며, 1967년 골드의 선구적인 논문 이후로 양의 데이터로부터 계산 가능한 열거 가능한 집합들의 클래스를 학습하는 것 또한 연구 주제이다.

6. 7. 튜링 계산 가능성의 일반화 (Generalizations of Turing computability)

환산 (계산 가능성 이론)에서는 튜링 환산 외에 다양한 환산 관계를 다룬다. 포스트는 진리표 환산을 포함하는 여러 "강한 환산"을 제시했는데, 이는 강한 환산을 구현하는 튜링 기계가 어떤 오라클이 주어지든 전체 함수를 계산하기 때문이다. 반면 "약한 환산"은 모든 오라클에 대해 환산 과정이 종료되지 않을 수 있으며, 튜링 환산이 그 예이다.

강한 환산에는 다음이 포함된다.

  • 일대일 환산: 각 ''n''이 ''A''에 속하는 경우에만 ''f''(''n'')이 ''B''에 속하는 전체 계산 가능한 단사 함수 ''f''가 존재하면, ''A''는 ''B''로 일대일 환산(또는 1-환산)된다.
  • 다대일 환산: ''f''가 단사 함수일 필요가 없는 일대일 환산과 유사하다. 각 ''n''이 ''A''에 속하는 경우에만 ''f''(''n'')이 ''B''에 속하는 전체 계산 가능한 함수 ''f''가 존재하면, ''A''는 ''B''로 다대일 환산(또는 m-환산)된다.
  • 진리표 환산: ''A''가 주어진 오라클에 관계없이 전체 함수를 계산하는 오라클 튜링 기계를 통해 ''A''가 ''B''로 튜링 환산 가능하면, ''B''로 진리표 환산 가능하다. 칸토어 공간의 컴팩트성으로 인해, 이는 환산이 오라클에 단일 질문 목록(입력에만 의존)을 동시에 제시하고, 응답을 확인한 후 추가 질문 없이 출력을 생성하는 것과 같다.


환산 (계산 가능성 이론) 문서에서는 긍정적, 선언적, 연언적, 선형 및 약한 버전과 경계 버전 등 추가적인 환산 개념을 다룬다.

강한 환산에 대한 주요 연구는 모든 계산 가능한 열거 가능 집합과 자연수의 모든 부분 집합의 클래스에 대한 이론을 비교하고, 환산 간의 관계를 조사하는 것이다. 예를 들어, 모든 튜링 차수는 진리표 차수이거나 무한히 많은 진리표 차수의 합으로 나타낼 수 있다.

튜링 환산보다 약한 환산, 즉 튜링 환산으로 유도되는 환산도 연구되었다. 대표적인 예로 산술적 환산과 초산술적 환산이 있으며, 이들은 산술 표준 모델에 대한 정의 가능성과 밀접하게 관련되어 있다.

계산 가능성 이론은 1990년 삭스가 설명한 산술적 환원 가능성, 초산술적 환원 가능성, α-재귀 이론과 같은 일반화된 개념도 연구한다. 이러한 개념은 튜링 기계로 실행할 수는 없지만 튜링 환원 가능성의 자연스러운 일반화인 환원 가능성을 포함한다. 또한, 자연수의 집합에 대한 정량화를 허용하여 산술적 계층과 해석적 계층을 조사하고, 정렬 순서 및 트리 이론과의 관련성을 탐구한다. 예를 들어, 무한 가지가 없는 계산 가능한 (이진이 아닌) 모든 트리의 인덱스 집합은 해석적 계층의 \Pi^1_1 레벨에서 완전하다. 튜링 환원 가능성과 초산술적 환원 가능성은 유효 기술 집합론에서 중요하며, 구성 가능성 정도와 같은 더 일반적인 개념은 집합론에서 연구된다.

6. 8. 연속 계산 가능성 이론 (Continuous computability theory)

아날로그 계산에 대한 계산 가능성 이론은 디지털 계산에 비해 덜 발전되어 있다. 아날로그 계산은 아날로그 컴퓨터, 아날로그 신호 처리, 아날로그 전자공학, 인공 신경망 및 미분 방정식과 연속 동적 시스템으로 모델링되는 연속 시간 제어 이론에서 발생한다. Blum–Shub–Smale machine 모델과 같은 계산 모델은 실수에 대한 계산을 형식화했다.

7. 전문 조직

계산 가능성 이론과 관련된 주요 전문 단체로는 매년 여러 연구 컨퍼런스를 개최하는 기호 논리학회가 있다. 학제간 연구 단체인 유럽 계산 가능성 학회(Computability in Europe, CiE) 또한 매년 컨퍼런스 시리즈를 개최한다.


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com