인공지능기술로 강화된 오늘날의 컴퓨터는 그들의 기술력에 대한 몇 가지 예를 들자면 사람들과 설득력 있는 대화에 참여하고, 노래를 작곡하고, 그림을 그리고, 체스와 바둑을 두며, 질병을 진단할 수 있다.

이러한 성공은 계산에 한계가 없음을 나타내는 것으로 간주될 수 있다. 이것이 사실인지 확인하려면 무엇이 컴퓨터를 강력하게 만드는지 이해하는 것이 중요하다.

컴퓨터의 성능에는 두 가지 측면이 있다. 하드웨어가 초당 실행할 수 있는 작업 수와 실행되는 알고리즘의 효율성이다. 하드웨어 속도는 물리 법칙에 의해 제한된다. 기본적으로 명령 집합인 알고리즘은 사람이 작성하고 컴퓨터 하드웨어가 실행할 수 있는 일련의 작업으로 변환된다. 컴퓨터의 속도가 물리적 한계에 도달하더라도 알고리즘의 한계로 인해 계산상의 장애물이 남아 있다.

이러한 장애물에는 컴퓨터가 해결할 수 없는 문제와 이론적으로는 해결할 수 있지만 실제로는 오늘날 상상할 수 있는 가장 강력한 버전의 컴퓨터로도 해결할 수 없는 문제가 포함된다. 수학자 및 컴퓨터 과학자는 가상의 기계에서 문제를 시도하여 문제를 해결할 수 있는지 여부를 확인하려고 시도한다.

가상 컴퓨팅 머신

튜링 기계로 알려진 알고리즘의 현대적 개념은 1936년 영국 수학자 앨런 튜링에 의해 공식화되었다. 종이에 연필로 산술 계산을 하는 방식을 모방한 가상의 장치이다. 튜링 머신은 오늘날 모든 컴퓨터의 기반이 되는 템플릿이다.

수동으로 수행할 경우 더 많은 종이가 필요한 계산을 수용하기 위해 튜링 기계의 가상 종이 공급은 무제한이라고 가정한다. 이것은 각각 공백이거나 하나의 기호를 포함하는 사각형의 무한한 리본 또는 "테이프"와 같다.

기계는 한정된 규칙 집합에 의해 제어되며 테이프의 초기 기호 시퀀스에서 시작된다. 기계가 수행할 수 있는 작업은 이웃 사각형으로 이동하고, 기호를 지우고, 빈 사각형에 기호를 쓰는 것이다. 기계는 이러한 일련의 작업을 수행하여 계산한다. 기계가 완료되거나 "정지"되면 테이프에 남아 있는 기호가 출력 또는 결과이다.

컴퓨팅은 종종 예 또는 아니오 대답이 있는 결정에 관한 것이다. 비유하자면 의료 검사(문제 유형)는 환자의 표본(문제 사례)에 특정 질병 지표(예 또는 아니오 대답)가 있는지 확인한다. 튜링 기계에 디지털 형식으로 표시되는 인스턴스는 기호의 초기 시퀀스이다.

튜링 기계가 긍정적이든 부정적이든 모든 인스턴스에 대해 정지하고 인스턴스가 산출하는 답을 올바르게 결정하도록 설계할 수 있는 경우 문제는 "해결 가능한" 것으로 간주된다.

모든 문제를 해결할 수 있는 것은 아니다.

많은 문제는 튜링 기계를 사용하여 해결할 수 있으므로 컴퓨터에서 해결할 수 있지만 다른 많은 문제는 그렇지 않다. 예를 들어, 중국계 미국인 수학자 Hao Wang이 1961년에 공식화한 타일링 문제의 변형인 도미노 문제는 풀 수 없다.

작업은 도미노 세트를 사용하여 전체 그리드를 덮고 대부분의 도미노 게임 규칙에 따라 인접한 도미노 끝에 있는 핍 수를 맞추는 것이다. 도미노 세트로 시작하여 세트가 그리드를 완전히 덮을지 여부를 결정할 수 있는 알고리즘이 없다는 것이 밝혀졌다.

합리적인 유지

합리적인 시간 내에 정지하는 알고리즘으로 많은 해결 가능한 문제를 해결할 수 있다. 이러한 "다항식 시간 알고리즘"은 효율적인 알고리즘이므로 컴퓨터를 사용하여 인스턴스를 해결하는 것이 실용적이다.

수천 개의 다른 해결 가능한 문제는 다항식 시간 알고리즘을 찾기 위한 지속적인 집중적인 노력에도 불구하고 이러한 알고리즘을 가지고 있는 것으로 알려져 있지 않다. 여기에는 여행하는 세일즈맨 문제가 포함된다.

순회 외판원 문제는 그래프라고 하는 일부 점이 직접 연결된 점 집합이 임의의 점에서 시작하여 다른 모든 점을 정확히 한 번 통과하고 원래 점으로 돌아오는 경로를 갖는지 여부를 묻는다. 한 세일즈맨이 이웃의 모든 가구를 정확히 한 번 지나 출발점으로 돌아가는 경로를 찾고자 한다고 상상해 보라.

NP-완전이라고 하는 이러한 문제는 1970년대 초 두 명의 컴퓨터 과학자인 캐나다계 미국인 Stephen Cook과 우크라이나계 미국인 Leonid Levin에 의해 독립적으로 공식화되고 존재하는 것으로 나타났다. 1위를 차지한 Cook은 이 공로로 1982년 컴퓨터 과학 분야 최고 권위의 튜링상을 수상했다.

정확히 아는 비용

NP-완전 문제에 대해 가장 잘 알려진 알고리즘은 본질적으로 가능한 모든 답에서 해결책을 찾는 것이다. 수백 점의 그래프에 대한 여행하는 세일즈맨 문제는 슈퍼컴퓨터에서 실행하는 데 몇 년이 걸릴 것이다. 이러한 알고리즘은 비효율적이므로 수학적 지름길이 없다.

실제 세계에서 이러한 문제를 해결하는 실용적인 알고리즘은 근사치가 개선되고 있지만 근사치만 제공할 수 있다. NP-완전 문제를 풀 수 있는 효율적인 다항식 시간 알고리즘이 있는지 여부는 21세기 초에 클레이수학연구소가 게시한 7개의 밀레니엄 공개 문제 중 하나이며 각각 백만 달러의 상금이 있다.

튜링 너머

튜링의 프레임워크를 넘어서는 새로운 형태의 계산이 있을 수 있을까? 1982년 노벨상 수상자인 미국의 물리학자 리처드 파인만은 양자역학에 기초한 계산 아이디어를 내놓았다.

1995년 미국 응용수학자 피터 쇼어(Peter Shor)는 다항식 시간에서 정수를 인수분해하는 양자 알고리즘을 제시했다. 수학자들은 이것이 튜링 프레임워크의 다항식 시간 알고리즘으로는 해결할 수 없다고 생각한다. 정수를 인수분해하는 것은 정수를 나눌 수 있는 것보다 더 작은 정수를 찾는 것을 의미한다. 예를 들어, 정수 688,826,081은 688,826,081 = 25,253 x 27,277이므로 더 작은 정수 25,253으로 나눌 수 있다.

네트워크 통신 보안에 널리 사용되는 RSA 알고리즘이라는 주요 알고리즘은 큰 정수를 인수분해하는 계산상의 어려움을 기반으로 한다. 쇼어의 결과는 양자 컴퓨팅이 현실이 된다면 사이버 보안의 지형을 바꿀 것임을 암시한다.

완전한 양자 컴퓨터를 구축하여 정수를 인수분해하고 다른 문제를 해결할 수 있을까? 일부 과학자들은 그럴 수 있다고 믿는다. 전 세계의 여러 과학자 그룹이 하나를 구축하기 위해 노력하고 있으며 일부는 이미 소규모 양자 컴퓨터를 구축했다.

그럼에도 불구하고 이전에 발명된 모든 새로운 기술과 마찬가지로 양자 계산과 관련된 문제는 새로운 한계를 부과할 것이 거의 확실하다.

이미지 제공: Laura Ockel / Unsplash