계산 가능성

Computability

계산가능성은 문제를 효과적인 방법으로 해결하는 능력이다.그것은 수학 논리학 내에서의 계산 가능성 이론 분야와 컴퓨터 과학 내에서의 계산 이론의 핵심 주제이다.문제의 계산 가능성은 문제를 해결하기 위한 알고리즘의 존재와 밀접하게 관련되어 있습니다.

계산가능성의 가장 널리 연구된 모델은 튜링-계산가능함수μ-재귀함수람다 미적분이며, 이 모든 것은 계산적으로 동등한 힘을 가지고 있다.튜링 기계보다 약한 계산가능성 개념은 오토마타 이론에서 연구되는 반면 튜링 기계보다 강한 계산가능성 개념은 하이퍼컴퓨팅 분야에서 연구된다.

문제

계산가능성의 중심 아이디어는 계산가능성을 탐구할 수 있는 작업인 (계산) 문제에 대한 것입니다.

다음 두 가지 주요 유형의 문제가 있습니다.

  • 판정 문제로 인해 세트S가 수정됩니다.세트S는 문자열, 자연수 또는 보다 큰 세트 U에서 가져온 기타 오브젝트일 수 있습니다.문제의 특정 예는 U의 요소 u가 S에 있는지 여부를 판별하는 것입니다.예를 들어, U를 자연수의 집합으로 하고 S를 소수의 집합으로 합니다.대응하는 판정 문제는 프라이머리 테스트에 대응합니다.
  • 함수 문제는 집합 U에서 집합 V로의 함수 f로 구성된다.문제의 한 예는 U의 요소 u가 주어진 경우 V의 해당 요소 f(u)를 계산하는 것입니다.예를 들어 U와 V는 모든 유한 2진수 문자열의 집합이며 f는 문자열을 취하여 입력의 숫자를 반대로 하여 얻은 문자열을 반환할 수 있습니다(따라서 f(0101) = 1010).

다른 유형의 문제로는 검색 문제 및 최적화 문제가 있습니다.

계산가능성 이론의 한 가지 목표는 계산의 각 모델에서 어떤 문제, 혹은 어떤 종류의 문제를 해결할 수 있는지를 결정하는 것이다.

형식적인 계산 모델

계산 모델은 특정 유형의 계산 프로세스에 대한 형식적인 설명입니다.설명은 종종 당면한 작업을 수행하기 위한 추상적인 기계의 형태를 취합니다.튜링 기계와 동등한 일반적인 계산 모델(처치-튜링 논문 참조):

람다 미적분
계산은 초기 람다 식(또는 함수와 해당 입력을 분리하려는 경우 두 개)과 각각 베타 감소를 한 번 적용하여 이전 항에서 추론한 유한 수열의 람다 항으로 구성됩니다.
조합논리
-calculus와 유사점을 가지지만 중요한 차이점도 존재한다(예를 들어 고정점 콤비네이터 Y는【\} -calculus】는 아니다).조합 논리는 큰 야망을 가지고 개발되었다: 역설의 본질을 이해하고, 수학의 기초를 더 경제적으로 만들고, 변수의 개념을 없앤다.
μ입자 함수
연산은 μ-재귀 함수, 즉 정의 시퀀스, 임의의 입력 값 및 입력 및 출력과 함께 정의 시퀀스에 나타나는 일련의 재귀 함수로 구성된다.따라서, 재귀 함수 f(x)의 정의 수열에서 함수 g(x)와 h(x,y)가 나타나면, g(5) = 7 또는 h(3,2) = 10 형식의 항이 나타날 수 있다.이 시퀀스의 각 엔트리는 기본 함수를 적용하거나 구성, 원시 재귀 또는 μ 재귀를 사용하여 의 엔트리를 따라야 합니다.를 들어, f(x) = h(x,g(x)), f(5) = 3나타나려면 g(5) = 6 및 h(5,6) = 3과 같은 항이 위에서 발생해야 한다.최종 항이 입력에 적용되는 재귀 함수의 값을 제공하는 경우에만 계산이 종료됩니다.
스트링 리라이트 시스템
문법유사한 규칙을 사용하여 기호 문자열에 대해 작동하는 마르코프 알고리즘을 포함합니다. 또한 포스트 표준 시스템도 포함합니다.
등록기
컴퓨터의 이론적인 이상화.몇 가지 종류가 있습니다.대부분의 경우, 각 레지스터는 자연수(무제한 크기)를 보유할 수 있으며, 명령은 간단하며(및 수가 적음), 예를 들어 감소(조건부 점프와 결합) 및 증가(및 정지)만 존재한다.(튜링 기계에서 볼 수 있는) 무한(또는 동적으로 성장하는) 외부 저장소의 부족은 그 역할을 괴델 번호 매기기 기술로 대체함으로써 이해할 수 있다: 각 레지스터가 자연수를 보유하고 있다는 사실은 복잡한 것(예를 들어 시퀀스 또는 매트릭스 등)을 적절한 거대한 자연수로 나타낼 수 있는 가능성을 가능하게 한다.표현과 해석의 모호성은 이러한 기법의 숫자 이론적인 기초에 의해 확립될 수 있다.
튜링 기계
또한 입력이 실행 "테이프"에 제공된다는 점을 제외하면 유한 상태 기계와 유사하며, 튜링 기계는 읽기/쓰기 "헤드"를 읽고 쓰거나 앞뒤로 이동할 수 있습니다.테이프는 임의의 크기로 확장할 수 있습니다.튜링 기계는 임의의 지속시간을 가질 수 있는 복잡한 계산을 수행할 수 있다.이 모델은 사전 정의된 자원 한계 없이 계산을 시뮬레이션하기 때문에 컴퓨터 과학에서 가장 중요한 계산 모델일 수 있습니다.
멀티테이프 튜링 머신
여기에서는 여러 개의 테이프가 있을 수 있습니다.게다가 테이프당 여러 개의 헤드가 있을 수 있습니다.놀랍게도, 비록 튜링 기계가 더 느리거나 테이프의 더 큰 전체 영역을 필요로 하지만, 이러한 종류의 기계에 의해 수행될 수 있는 어떤 계산도 일반 튜링 기계에 의해 수행될 수 있다.
P′′
튜링 기계와 마찬가지로, P′는 무한대의 기호 테이프(랜덤 액세스 없음)와 다소 미니멀리즘적인 명령 집합을 사용합니다.그러나 이러한 명령어는 매우 다르므로 튜링 기계와 달리 P′ does는 모든 "메모리" 기능이 테이프에 의해서만 제공될 수 있기 때문에 구별된 상태를 유지할 필요가 없습니다.현재 기호를 다시 쓰는 대신 이 기호를 모듈식 산술 증분 방식으로 수행할 수 있습니다.P has has 에는 공백 기호를 검사하는 사이클에 대한 지침 쌍도 있습니다.미니멀리즘의 특성에도 불구하고, 그것은 Brainfuck이라는 구현된 (엔터테인먼트를 위해) 사용되는 프로그래밍 언어의 부모 공식 언어가 되었다.

일반적인 계산 모델 외에도 일부 단순한 계산 모델은 특수하고 제한된 애플리케이션에 유용합니다.를 들어 정규 표현은 사무실 생산성 소프트웨어에서 프로그래밍 언어까지 많은 컨텍스트에서 문자열 패턴을 지정합니다.수학적으로 정규식과 동등한 또 다른 형식주의인 유한 오토마타는 회로 설계 및 문제 해결에서 사용됩니다.문맥이 없는 문법은 프로그래밍 언어 구문을 지정합니다.비결정론적 푸시다운 오토마타는 문맥이 없는 문법과 동등한 또 다른 형식주의이다.

다른 계산 모델에는 다른 작업을 수행할 수 있는 기능이 있습니다.계산 모델의 힘을 측정하는 한 가지 방법은 모델이 생성할 수 있는 공식 언어의 클래스를 연구하는 것입니다. 이러한 방법으로 언어의 촘스키 계층 구조를 얻는 것입니다.

기타 제한된 계산 모델은 다음과 같습니다.

결정론적 유한 오토마톤(DFA)
유한 상태 기계라고도 합니다.오늘날 존재하는 모든 실제 컴퓨팅 디바이스는 유한한 자원으로 동작하기 때문에 유한한 상태의 기계로 모델링할 수 있습니다.이러한 기계에는 일련의 상태와 입력 스트림의 영향을 받는 일련의 상태 천이가 있습니다.특정 상태는 수용 상태로 정의됩니다.입력 스트림을 한 번에 1글자씩 기계에 공급하고 현재 상태의 상태 천이를 입력 스트림과 비교하여 일치하는 천이가 있으면 기계는 새로운 상태로 진입해도 된다.입력 스트림의 마지막에 기계가 수용 상태에 있는 경우 입력 스트림 전체가 수용됩니다.
비결정론적 유한 오토마톤(NFA)
처리 시퀀스는 고유하게 결정되지 않지만 또 다른 간단한 계산 모델입니다.한정된 수의 상태를 통해 동시에 여러 개의 연산 경로를 취하는 것으로 해석할 수 있습니다.단, NFA가 동등한 DFA로 환원된다는 것을 증명할 수 있습니다.
푸시다운 오토마톤
임의의 크기로 확장할 수 있는 실행 스택을 사용할 수 있다는 점을 제외하면 유한 상태 시스템과 유사합니다.상태 전환에서는 스택에 기호를 추가할지 또는 스택에서 기호를 제거할지도 추가로 지정합니다.스택의 상위 요소만 언제든지 액세스할 수 있지만 메모리 스택이 무한하기 때문에 DFA보다 강력합니다.

오토마타의 파워

이러한 계산 모델을 사용하면 한계가 어느 정도인지 판단할 수 있습니다.즉, 어떤 종류의 언어를 받아들일 수 있는가?

유한 상태 기계의 힘

컴퓨터 과학자들은 유한 상태 기계에 의해 받아들여질 수 있는 모든 언어를 정규 언어라고 부른다.유한 상태 기계에서 가능한 상태의 수가 유한하다는 제약 때문에, 우리는 규칙적이지 않은 언어를 찾기 위해서는 무한한 수의 상태를 필요로 하는 언어를 구축해야 한다는 것을 알 수 있습니다.

이러한 언어의 예로는 동일한 수의 문자 'a'와 'b'를 포함하는 문자 'a'와 'b'로 구성된 모든 문자열의 집합을 들 수 있다.이 언어가 유한 상태 머신에 의해 올바르게 인식되지 않는 이유를 확인하려면 먼저 그러한 머신 M이 존재한다고 가정합니다.M에는 몇 가지 상태 n이 있어야 합니다.여기서 문자열( + 1 (n+1 '(n + 1) (n1 'b'로 구성됩니다

x읽었듯이,(+ 11)}'as and only n's state가 피죤홀 원리에 따라 존재하기 때문에 기계에는 a의 첫 번째 시리즈와 같이 반복되는 상태가 존재해야 합니다.상태를 S라고 하고, 나아가 d를 S의 번째 발생부터 'a' 시퀀스의 몇 번째 발생까지 읽기 위해 기계가 읽은 'a'의 수라고 합니다.그러면 S가 번째로 발생할 때 d( 0 { style 0 } )의 a를 더하면 다시 S 상태가 된다는 것을 알 수 있습니다.즉, (+ + ){ 'a 문자열은 (+) {'a' 문자열과 같은 상태로 끝나야 합니다.즉, 기계가 x를 받아들이는 경우 (+ +1 ) 1)} 'a' 뒤에( ) {1)} 'b 문자열도 허용해야 합니다.이것은 'a'와 'b'의 동일한 수를 포함하는 문자열 언어가 아닙니다.즉, M은 같은 수의 'a'와 'b' 문자열과 ( + ){ } {a'n+ {} 'bs를 가진 문자열을 올바르게 구별할 수 없습니다.

따라서 이 언어는 어떤 유한 상태 기계에서도 올바르게 받아들여질 수 없기 때문에 정규 언어가 아니라는 것을 알고 있습니다.이 결과의 보다 일반적인 형태는 정규 언어에 대한 펌핑 보조어라고 불리며, 이는 다양한 종류의 언어가 유한 상태 기계에 의해 인식될 수 없다는 것을 보여주는 데 사용될 수 있습니다.

푸시다운 오토마타의 파워

컴퓨터 사이언티스트들은 푸시다운 오토마톤에 의해 받아들여질 수 있는 언어를 문맥이 없는 언어로 정의하며, 문맥이 없는 문법으로 지정할 수 있습니다.정규 언어가 아닌 것을 보여 준 a와 b의 수가 같은 문자열로 구성된 언어는 푸시다운 오토마톤에 의해 결정될 수 있습니다.또한 일반적으로 푸시다운 오토마톤은 유한 상태 기계와 같이 동작할 수 있기 때문에 규칙적인 언어를 결정할 수 있습니다.따라서 이 계산 모델은 유한 상태 기계보다 훨씬 강력합니다.

그러나 푸시다운 오토마톤으로 결정할 수 없는 언어도 있는 것으로 나타났습니다.결과는 정규 표현과 비슷하므로 여기서는 자세히 설명하지 않습니다.문맥이 없는 언어에 대한 펌핑 보조항목이 있습니다.그러한 언어의 예는 소수 집합이다.

튜링 기계의 힘

튜링 기계는 소수로 구성된 언어와 같이 푸시다운 자동화에 의해 결정될 수 없는 언어에 더하여 어떤 문맥이 없는 언어도 결정할 수 있다.그러므로 이것은 엄밀하게는 더 강력한 계산 모델이다.

튜링 기계는 입력 테이프에서 "백업"할 수 있는 능력을 가지고 있기 때문에, 앞서 설명한 다른 계산 모델에서는 불가능한 방식으로 튜링 기계가 장시간 실행되는 것이 가능하다.일부 입력에 대해 실행(정지)을 끝내지 않는 튜링 기계를 구성할 수 있습니다.우리는 튜링 기계가 결국 모든 입력에서 멈추고 답을 줄 경우 언어를 결정할 수 있다고 말한다.그렇게 결정될 수 있는 언어를 재귀 언어라고 합니다.우리는 튜링 머신을 더 자세히 설명할 수 있는데, 튜링 머신은 결국 언어의 어떤 입력에 대해서도 답을 주지만, 그 언어에 없는 입력 문자열에 대해서는 영원히 실행될 수 있다.그러한 튜링 기계는 우리에게 주어진 문자열이 언어 안에 있다는 것을 알려줄 수 있지만, 우리는 주어진 문자열이 언어 안에 없다는 것을 그것의 행동에 근거해서 결코 확신할 수 없을지도 모른다. 왜냐하면 그러한 경우 그것은 영원히 실행될 수 있기 때문이다.이러한 튜링 기계에 의해 받아들여지는 언어를 재귀 열거형 언어라고 한다.

튜링 기계는 오토마타의 매우 강력한 모델임이 밝혀졌습니다.보다 강력한 기계를 만들기 위해 튜링 기계의 정의를 수정하려는 시도는 놀랍게도 실패에 직면했다.예를 들어, 튜링 기계에 추가 테이프를 추가하여 작업할 2차원(또는 3차원 또는 임의의 차원) 무한 표면을 제공하는 것은 기본적인 1차원 테이프를 가진 튜링 기계에 의해 모두 시뮬레이션될 수 있습니다.따라서 이러한 모델은 더 강력하지 않습니다.사실 처치-튜링 논문의 결과는 튜링 기계에 의해 결정될 수 없는 언어를 결정할 수 있는 합리적인 계산 모델이 없다는 것이다.

그렇다면 질문은 재귀적으로 열거할 수 있지만 재귀적이지 않은 언어가 있는가 하는 것입니다.게다가, 반복적으로 열거되지 않는 언어도 있을까요?

정지 문제

정지 문제는 컴퓨터 과학에서 가장 유명한 문제 중 하나입니다. 왜냐하면 그것은 계산 가능성의 이론과 우리가 일상적으로 컴퓨터를 사용하는 방법에 깊은 영향을 미치기 때문입니다.이 문제는 다음과 같이 표현할 수 있습니다.

튜링 기계와 그 초기 입력에 대한 설명이 주어지면, 이 입력에 대해 실행될 때 프로그램이 정지(완료)되는지 여부를 판단한다.그 대안은 멈추지 않고 영원히 운행하는 것이다.

여기서 우리는 소수나 회문에 대한 단순한 질문을 하지 않고, 대신 상황을 뒤집고 다른 튜링 기계에 대한 질문에 답하도록 튜링 기계를 요구하고 있습니다.표시할 수 있습니다(메인 기사 참조:정지 문제)는 모든 경우에 이 질문에 답할 수 있는 튜링 기계를 구축하는 것이 불가능하다는 것이다.

즉, 모든 경우에 특정 입력에서 특정 프로그램이 정지하는지 여부를 확인하는 유일한 일반적인 방법은 단순히 프로그램을 실행하여 정지하는지 확인하는 것입니다.멈춘다면 멈춘다는 것을 알 수 있습니다.하지만 멈추지 않으면 결국 멈출지 알 수 없을지도 모릅니다.튜링 기계가 최종적으로 정지하는 모든 가능한 입력 스트림과 쌍을 이루는 모든 튜링 기계 설명으로 구성된 언어는 재귀적이지 않습니다.따라서 정지하는 문제를 계산 불가능 또는 결정 불가능이라고 합니다.

정지 문제의 연장은 라이스의 정리라고 불리며, 이것은 주어진 언어가 특정한 중요하지 않은 속성을 가지고 있는지 아닌지는 (일반적으로) 판단할 수 없다는 것이다.

재귀적으로 열거할 수 있는 언어를 넘어

그러나, 만약 우리가 그것을 결정하는 튜링 기계가 그 자체가 멈추지 않는 튜링 기계의 표현인 입력이 주어졌을 때 영원히 실행될 수 있도록 허용한다면, 정지 문제는 해결하기가 쉽다.따라서 정지하는 언어는 반복적으로 열거할 수 있다.그러나 재귀적으로 열거할 수 없는 언어를 구성할 수도 있습니다.

그러한 언어의 간단한 예는 정지된 언어의 보완이다; 그것은 튜링 기계가 입력에서 멈추지 않는 입력 문자열과 쌍을 이루는 모든 튜링 기계로 구성된 언어이다.이 언어가 재귀적으로 열거될 수 없다는 것을 알기 위해, 우리가 그러한 모든 튜링 기계에 대해 확실한 답을 줄 수 있는 튜링 기계 M을 구성한다고 가정해 보자. 그러나 그것은 결국 멈추는 튜링 기계에서 영원히 실행될 수 있다.그 후, 2개의 프로그램의 실행을 인터리빙 해, 이 기계의 동작을 시뮬레이트 해, 입력에 주어진 기계의 실행을 직접 시뮬레이트 하는 Turing M { M}을 구축할 수 있습니다.시뮬레이션 중인 프로그램이 정지하면 직접 시뮬레이션이 최종적으로 정지하고 입력 이 정지하지 않으면 M의 시뮬레이션이 최종적으로 정지되므로 M의 버전중 하나가 정지되는 을 알 수 있습니다 M \ M은 정지 문제의 결정자입니다.단, 정지 문제는 판별할 수 없다는 것은 앞에서 설명한 바 있습니다.우리는 모순을 가지고 있고, 따라서 우리는 M이 존재한다는 우리의 가정이 틀렸다는 것을 보여 주었다.따라서 정지하는 언어의 보완어는 재귀적으로 열거할 수 없다.

동시성 기반 모델

병렬 랜덤 액세스 머신과 페트리 네트워크를 포함한 동시성에 기초한 많은 계산 모델이 개발되었습니다.이러한 동시 계산 모델은 튜링 기계에 의해 구현될 수 없는 어떤 수학적 함수도 구현하지 않는다.

보다 강력한 계산 모델

처치-튜링 논문은 튜링 기계보다 더 많은 수학적 함수를 계산할 수 있는 효과적인 컴퓨팅 모델은 없다고 추측한다.컴퓨터 과학자들은 튜링 계산 능력을 뛰어넘는 많은 종류의 하이퍼컴퓨터를 상상해왔다.

무한 실행

계산의 각 단계가 이전 단계의 절반 시간(그리고 바라건대 이전 단계의 절반 에너지...)을 필요로 하는 기계를 상상해 보십시오.첫 번째 스텝에 필요한 시간의 1/2 단위(및 첫 번째 스텝에 필요한 에너지의 1/2 단위)로 정규화할 경우, 실행에는 다음이 필요합니다.

실행할 시간 단위(및 1 에너지 단위...)를 지정합니다.이 무한 직렬은 1로 수렴됩니다. 즉, 이 Zeno 기계는 1시간 단위로 셀 수 없을 만큼 많은 스텝을 실행할 수 있습니다(에너지 단위 1개 사용...).이 기계는 해당 기계의 실행을 직접 시뮬레이션하여 정지 문제를 결정할 수 있습니다.즉, 모든 수렴 무한 급수가 작동하게 됩니다(증명 가능한 무한 급수가 작동하게 됩니다.무한 급수가 n으로 수렴된다고 가정하면, Zeno 기계는 n개의 시간 단위로 셀 수 있는 무한 실행을 완료합니다.

오라클 머신

이른바 Oracle 머신은 특정 결정 불가능한 문제에 대한 해결책을 제공하는 다양한 "오라클"에 액세스할 수 있습니다.예를 들어, 튜링 기계는 주어진 튜링 기계가 주어진 입력에서 멈추는지 여부에 대해 즉시 응답하는 "해킹 오라클"을 가질 수 있다.이 기계들은 재귀 이론의 핵심 연구 주제이다.

하이퍼컴퓨팅의 한계

우리가 상상할 수 있는 오토마타의 한계를 나타내는 이 기계들조차도 그 자체의 한계에 부딪힙니다.그들 각각은 튜링 기계의 정지 문제를 풀 수 있지만, 정지 문제의 그들 자신의 버전을 풀 수는 없다.예를 들어 Oracle 머신은 특정 Oracle 머신이 정지할 수 있는지 여부에 대한 질문에 대답할 수 없습니다.

「 」를 참조해 주세요.

레퍼런스

  • Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. 2부: 계산 가능성 이론, 3장-6절, 페이지 123–222.
  • Christos Papadimitriou (1993). Computational Complexity (1st ed.). Addison Wesley. ISBN 0-201-53082-1. 3장: 계산 가능성, 페이지 57-70.
  • S. Barry Cooper (2004). Computability Theory (1st ed.). Chapman & Hall/CRC. ISBN 978-1-58488-237-4.