컴퓨테이션

컴퓨테이션(computation)은 잘 정의된 모든 유형의 산술 또는 비산술 계산이다. 컴퓨테이션의 일반적인 예로는 수학 방정식과 컴퓨터 알고리즘이 있다.

컴퓨테이션을 수행하는 기계 또는 전자 장치(또는 역사적으로 사람)를 컴퓨터라고 한다. 컴퓨테이션에 대한 연구는 컴퓨테이션 가능성 분야이며, 그 자체가 컴퓨터 과학 및 수리 논리학의 하위 분야이다.

서론

수학적 진술은 '정의되어야 한다'는 개념은 적어도 1600년대부터 수학자들에 의해 논의되어 왔지만,^[1] 적절한 정의에 대한 합의는 찾기 어려웠다.^[2] 후보 정의는 1930년대에 여러 수학자들에 의해 독립적으로 제안되었다.^[3] 가장 잘 알려진 변형은 수학자 앨런 튜링에 의해 공식화되었는데, 그는 잘 정의된 진술 또는 계산을 튜링 기계의 초기화 매개변수로 표현될 수 있는 모든 진술로 정의했다.^[4] 다른 (수학적으로 동등한) 정의로는 알론조 처치의 람다-정의 가능성, 헤르브란트-괴델-클레이니의 일반 재귀성 및 에밀 포스트의 1-정의 가능성이 있다.^[3]

오늘날, 이러한 잘 정의된 특성을 나타내는 모든 형식적인 진술 또는 계산을 계산 가능하다고 부르며, 그 진술 또는 계산 자체를 컴퓨테이션이라고 한다.

튜링의 정의는 모든 잘 구성된 대수적 진술과 현대 프로그래밍 언어로 작성된 모든 진술을 포함하는 매우 광범위한 수학적 진술에 "잘 정의됨"을 부여했다.^[5]

이러한 정의가 널리 채택되었음에도 불구하고, 이 정의에 따라 잘 정의된 특성을 갖지 않는 몇몇 수학적 개념들이 있다. 여기에는 정지 문제와 바쁜 비버 게임이 포함된다. 계산 가능한 진술과 '계산 불가능한' 진술을 모두 포착할 수 있는 '잘 정의된' 것에 대한 더 강력한 정의가 존재하는지는 아직 미해결 문제로 남아있다.^{[note 1][6]}

계산 가능한 수학적 진술의 몇 가지 예는 다음과 같다.

• C++, 파이썬, 자바를 포함한 현대 프로그래밍 언어에서 특징지어지는 모든 진술.^[5]
• 전자 컴퓨터, 계산기 또는 주판에 의해 수행되는 모든 계산.
• 해석기관에서 수행되는 모든 계산.
• 튜링 기계에서 수행되는 모든 계산.
• 수학 교과서에 나와 있는 대부분의 수학적 진술 및 계산.

계산 불가능한 수학적 진술의 몇 가지 예는 다음과 같다.

• 모호하게 튜링 기계로 인코딩될 수 없도록 잘 정의되지 않은 계산 또는 진술: ("폴은 조보다 나를 두 배 더 사랑해").
• 잘 정의된 것처럼 보이지만, (예를 들어 정지 문제와 같이) 이를 해결할 튜링 기계가 존재하지 않음을 증명할 수 있는 문제 진술.

컴퓨테이션은 컴퓨터라고 불리는 닫힌 물리계 내에서 발생하는 순수한 물리적 과정으로 볼 수 있다. 튜링의 1937년 증명인 계산 가능한 수에 대하여와 결정 문제에의 응용은 계산 가능한 진술과 일반적으로 컴퓨터라고 불리는 특정 물리적 시스템 사이에 형식적 동등성이 있음을 입증했다. 이러한 물리적 시스템의 예로는 튜링 기계, 엄격한 규칙을 따르는 인간 수학자, 디지털 컴퓨터, 기계식 컴퓨터, 아날로그 컴퓨터 등이 있다.

컴퓨테이션의 대안적 설명

매핑 설명

컴퓨테이션에 대한 대안적인 설명은 힐러리 퍼트넘 등의 저작에서 발견된다. 피터 고드프리-스미스는 이를 "단순 매핑 설명"이라고 불렀다.^[7] 괄티에로 피치니니가 요약한 이 설명에 따르면, 시스템의 상태와 컴퓨테이션 사이에 매핑이 존재하여 "[시스템의] 미시 물리적 상태가 계산 상태 간의 상태 전환을 반영할 때" 물리적 시스템이 특정 컴퓨테이션을 수행한다고 말할 수 있다.^[8]

의미론적 설명

제리 포더와 같은 철학자들은^[9] 의미론적 내용이 컴퓨테이션의 필수 조건이어야 한다는 제한을 두어 다양한 컴퓨테이션 설명을 제시했다 (즉, 임의의 물리적 시스템과 컴퓨팅 시스템을 구별하는 것은 컴퓨테이션의 피연산자가 어떤 것을 나타낸다는 점이다). 이러한 개념은 범계산주의의 매핑 설명에 대한 논리적 추상화를 방지하려는 시도이다. 범계산주의는 모든 것이 모든 것을 컴퓨테이션한다고 말할 수 있다는 아이디어이다.

기계론적 설명

괄티에로 피치니니는 기계론에 기반한 컴퓨테이션 설명을 제안한다. 이는 물리적 컴퓨팅 시스템이 설계상 물리적 컴퓨테이션, 즉 규칙에 따라 "매체 독립적" 운반체의 조작(기능 메커니즘에 의한)을 수행하는 메커니즘의 한 유형이라고 명시한다. "매체 독립성"은 해당 속성이 여러 실현기와 여러 메커니즘에 의해 인스턴스화될 수 있어야 하며, 메커니즘의 입력과 출력도 다중 실현 가능해야 한다는 것을 요구한다. 간단히 말해, 매체 독립성은 (일반적인 디지털 컴퓨터에서처럼) 전압 이외의 속성을 가진 물리 변수의 사용을 허용한다. 이는 뇌나 양자 컴퓨터에서 발생하는 것과 같은 다른 유형의 컴퓨테이션을 고려할 때 필수적이다. 이러한 의미에서 규칙은 물리적 컴퓨팅 시스템의 입력, 출력 및 내부 상태 간의 매핑을 제공한다.^[10]

수학적 모델

 이 부분의 본문은 계산 모델입니다.

계산 이론에서는 다양한 수학적 계산 모델이 개발되었다. 전형적인 수학적 컴퓨터 모델은 다음과 같다:

• 튜링 기계, 푸시다운 자동 기계, 유한 상태 기계, PRAM을 포함한 상태 모델
• 람다 대수를 포함한 함수형 모델
• 논리형 프로그래밍을 포함한 논리 모델
• 행위자 모델 및 프로세스 계산을 포함한 동시성 모델

주티는 계산 이론에서 연구되는 모델을 계산 시스템이라고 부르며, 이들 모두가 이산 시간과 이산 상태 공간을 가진 수학적 동역학계라고 주장한다.^[11]:ch.1 그는 계산 시스템이 세 부분으로 구성된 복잡한 객체라고 주장한다. 첫째, 이산 시간과 이산 상태 공간을 가진 수학적 동역학계 ${\displaystyle DS}$; 둘째, 이론적 부분 ${\displaystyle F}$와 실제 부분 ${\displaystyle B_{F}}$로 구성된 계산 설정 ${\displaystyle H=\left(F,B_{F}\right)}$; 셋째, 동역학계 ${\displaystyle DS}$를 설정 ${\displaystyle H}$와 연결하는 해석 ${\displaystyle I_{DS,H}}$이다.^{[12]:pp.179–80}

같이 보기

• 계산 가능성 이론
• 하이퍼 계산
• 계산주의 마음 이론