계산 가능성 이론 및 복잡성 소개
게시 됨: 2022-03-11궁금한 적이 있습니까? 이 기사를 읽고 있는 장치가 정확히 무엇입니까? 컴퓨터 란 무엇입니까?
계산 과학은 이러한 현대 컴퓨팅 장치가 상상조차 하기 훨씬 이전의 시간으로 거슬러 올라갑니다. 더 자주 묻는 질문이 프로그래밍 언어, 프레임워크 및 라이브러리와 관련된 산업에서 우리는 종종 컴퓨터를 움직이는 기본 개념을 당연하게 여겼습니다.
하지만 무한한 가능성을 지닌 것처럼 보이는 이 컴퓨터에도 한계가 있을까요? 컴퓨터로 해결할 수 없는 문제가 있습니까?
이 기사에서 우리는 프로그래밍 언어와 컴퓨터 아키텍처의 세부 사항에서 벗어나 이러한 질문을 다룰 것입니다. 컴퓨터와 알고리즘의 힘과 한계를 이해함으로써 우리는 사고 방식을 개선하고 다양한 전략에 대해 더 나은 추론을 할 수 있습니다.
컴퓨팅에 대한 추상적 관점은 1970년대에 처음 개발되었을 때와 마찬가지로 오늘날에도 우리에게 가치 있는 시간의 테스트를 견뎌낸 결과를 생성합니다.
계산 가능성
컴퓨터란? 문제란 무엇입니까?
학교에서 우리는 종종 다음과 같은 문제와 기능의 정신적 모델을 배웁니다.
함수는 출력 f(x)를 찾기 위해 입력 x에 적용하는 절차입니다.
수학적 정의가 다릅니다.
함수는 각 쌍의 첫 번째 요소가 집합 X(도메인이라고 함)에서, 각 쌍의 두 번째 요소가 집합 Y(공동 도메인 또는 범위라고 함)에서, 그리고 각 쌍의 각 요소가 순서쌍의 집합입니다. 도메인은 범위의 정확히 하나의 요소와 쌍을 이룹니다.
정말 입이 떡 벌어졌습니다. 그러나 정확히 무엇을 의미합니까?
이 정의는 컴퓨터가 기능을 계산하는 기계임을 알려줍니다.
왜요?
컴퓨터는 임의의 입력을 일부 출력으로 변환하기 때문입니다. 즉, 그들은 문제를 해결합니다. 함수에 대한 두 가지 정의, 우리에게 너무나 익숙한 것과 형식적인 것은 많은 실제적인 목적에서 일치합니다.
그러나 수학적 정의를 통해 계산할 수 없는 함수(즉, 해결할 수 없는 문제)의 존재와 같은 흥미로운 결론에 도달할 수 있습니다.
모든 기능을 알고리즘으로 설명할 수는 없기 때문입니다.
게임의 규칙
논증을 돕기 위해 컴퓨터가 입력을 받고 일련의 작업을 수행하고 일정 시간이 지나면 출력을 제공하는 기계라고 상상해 보겠습니다.
입력을 기계의 알파벳이라고 부를 것입니다. 즉, 일부 유한 집합의 문자 문자열 집합입니다. 예를 들어, 기계의 알파벳은 이진법(0과 1)이거나 ASCII 문자 집합일 수 있습니다. 모든 유한한 문자 시퀀스는 문자열입니다(예: "0110").
더욱이, 우리는 기계의 출력을 바이너리 승인-거부 결정으로 나타낼 것이며, 기계가 계산을 마치면 전달될 것입니다. 이 추상화는 이전의 함수에 대한 수학적 정의와 잘 맞습니다.
이러한 매개변수가 주어지면 문자열 모음이라는 또 하나의 유형을 특성화하는 것이 중요합니다. 우리는 어떤 기계가 받아들이는 문자열 집합에 관심이 있을 수도 있고, 특정 집합의 문자열만 받아들이고 다른 것은 받아들이지 않는 기계를 만들고 있을 수도 있습니다. 아니면 어떤 기계의 모든 것을 받아들이는 기계를 설계하는 것이 가능한지 묻고 있을 수도 있습니다. 특정 세트 및 기타 없음.
이러한 모든 경우에 문자열 집합을 언어라고 합니다. 예를 들어 짝수를 나타내는 모든 이진 문자열 집합 또는 짝수 문자가 있는 문자열 집합입니다. 숫자와 같은 언어는 연결, 합집합, 교집합 등과 같은 연산자로 조작될 수 있음이 밝혀졌습니다.
한 가지 중요한 연산자는 정규식과 함께 사용되는 Kleene 별 연산자입니다. 이것은 가능한 모든 언어 능력의 결합으로 생각할 수 있습니다. 예를 들어, 우리 언어 A 가 문자열 { '01', '1' }의 집합이면 A* 의 한 구성원은 문자열 '0101111'입니다.
가산성
모든 함수가 계산 가능하지 않다는 주장을 증명하기 전에 퍼즐의 마지막 조각은 가산성의 개념입니다. 직관적으로 우리의 증거는 더 많은 언어가 있음을 보여줄 것입니다. 즉, 문제를 해결할 수 있는 프로그램보다 더 많은 문제가 있습니다. 이것은 문자열이 언어(예/아니오)에 속하는지 여부에 대한 질문 자체가 문제이기 때문에 작동합니다.
더 정확하게 말하면, 우리의 증명은 가능한 프로그램의 집합은 셀 수 있는 무한한 반면 알파벳에 대한 언어의 집합은 셀 수 없을 정도로 무한하다고 주장합니다.
이 시점에서 "무한대 자체가 충분히 이상한 아이디어입니다. 이제 나는 그들 중 두 명을 처리해야합니다!"
글쎄요, 그렇게 나쁘지는 않습니다. 셀 수 있는 무한 집합은 열거할 수 있는 집합입니다. 이것이 첫 번째 요소이고, 이것이 두 번째 요소이고, 이런 식으로 결국 집합의 모든 요소에 숫자를 할당한다고 말할 수 있습니다. 예를 들어, 짝수 집합을 가져옵니다. 우리는 2가 첫 번째, 4가 두 번째, 6이 세 번째 등이라고 말할 수 있습니다. 그러한 집합은 셀 수 있는 무한하거나 셀 수 있습니다.
하지만 일부 집합의 경우 실수와 마찬가지로 당신이 얼마나 똑똑한지는 중요하지 않습니다. 단순히 열거가 없습니다. 이 집합은 셀 수 없을 정도로 무한하거나 셀 수 없습니다.
셀 수 없이 많은 프로그램
첫째, 우리는 컴퓨터 프로그램의 집합이 셀 수 있음을 보여주고 싶습니다. 우리의 목적을 위해 유한 알파벳에 대한 모든 문자열의 집합이 셀 수 있음을 관찰하여 이를 수행합니다. 이것은 컴퓨터 프로그램 자체가 유한 문자열이기 때문에 작동합니다.
증명은 간단하며 여기에서 세부 사항을 다루지 않습니다. 핵심은 자연수만큼 많은 컴퓨터 프로그램이 있다는 것입니다.
반복하자면:
모든 알파벳 위의 모든 문자열 집합(예: 모든 컴퓨터 프로그램 집합)은 셀 수 있습니다.
셀 수 없이 많은 언어
이러한 결론이 주어지면 이러한 문자열의 하위 집합은 어떻습니까? 다른 방식으로 물으면 모든 언어 집합은 어떻습니까? 이 집합은 셀 수 없는 것으로 밝혀졌습니다.
모든 알파벳의 모든 언어 집합은 셀 수 없습니다.
다시 한 번, 우리는 여기서 증거를 다루지 않습니다.
결과
그것들이 즉각적으로 명백하지 않을 수도 있지만, 언어의 셀 수 없는 것과 모든 컴퓨터 프로그램 세트의 셀 수 있는 것의 결과는 심오합니다.
왜요?
A 가 ASCII 문자 집합이라고 가정합니다. ASCII 문자는 컴퓨터 프로그램을 구성하는 데 필요한 문자일 뿐입니다. JavaScript 프로그램을 나타내는 문자열 집합이 A* 의 하위 집합임을 알 수 있습니다(여기서 *는 Kleene 별 연산자). JavaScript의 선택은 임의적입니다. 이 프로그램 세트는 셀 수 있는 세트의 하위 집합이므로 JavaScript 프로그램 세트는 셀 수 있습니다.
또한 모든 언어 L 에 대해 일부 문자열 x 가 L 에 있으면 1로 평가되고 그렇지 않으면 0으로 평가되는 일부 함수 f 를 정의할 수 있다고 가정해 보겠습니다. 이러한 기능은 모두 다릅니다. 모든 언어의 집합과 1:1 대응이 있고 모든 언어의 집합이 셀 수 없기 때문에 이러한 모든 기능의 집합은 셀 수 없습니다.
심오한 점은 다음과 같습니다.
모든 유효한 프로그램 집합은 셀 수 있지만 함수 집합은 셀 수 없으므로 단순히 프로그램을 작성할 수 없는 일부 함수가 있어야 합니다.
우리는 이러한 기능이나 문제가 어떻게 생겼는지 아직 모르지만 그것이 존재한다는 것을 알고 있습니다. 해결책이 없는 몇 가지 문제가 있기 때문에 이것은 겸허한 깨달음입니다. 우리는 컴퓨터를 매우 강력하고 유능하다고 생각하지만 일부는 손이 닿지 않는 곳에 있습니다.
이제 질문은 "이러한 문제는 어떻게 생겼습니까?"가 됩니다. 이러한 문제를 계속 설명하기 전에 먼저 일반화된 방식으로 계산을 모델링해야 합니다.
튜링 머신
컴퓨터의 최초의 수학적 모델 중 하나는 Alan Turing에 의해 개발되었습니다. 튜링 머신이라고 하는 이 모델은 계산 가능성에 대한 우리의 개념을 완전히 포착하는 매우 간단한 장치입니다.
기계에 대한 입력은 입력이 기록된 테이프입니다. 읽기/쓰기 헤드를 사용하여 기계는 일련의 단계를 통해 입력을 출력으로 바꿉니다. 각 단계에서 테이프에 쓸지 여부와 내용, 테이프를 오른쪽 또는 왼쪽으로 이동할지 여부가 결정됩니다. 이 결정은 정확히 두 가지를 기반으로 합니다.
머리 아래의 현재 기호 및
기호가 쓰여질 때 업데이트되는 기계의 내부 상태
그게 다야
보편성
1926년에 Alan Turing은 Turing 기계를 개발했을 뿐만 아니라 그의 유명한 논문인 "On Computable Numbers"를 썼을 때 계산의 본질에 대한 다른 많은 주요 통찰력을 얻었습니다. 그는 컴퓨터 프로그램 자체가 컴퓨터에 대한 입력으로 간주될 수 있다는 것을 깨달았습니다. 이러한 관점에서 그는 Turing 기계가 입력을 시뮬레이션하거나 실행할 수 있다는 아름다운 아이디어를 가지고 있었습니다.
오늘날 우리는 이러한 아이디어를 당연하게 여겼지만 튜링 시대로 돌아가 보면 그러한 보편적인 기계의 아이디어는 Turing이 해결할 수 없는 문제를 개발할 수 있게 한 주요 돌파구였습니다.
처치-튜링 테제
계속하기 전에 중요한 점을 살펴보겠습니다. 튜링 기계가 계산 모델이라는 것을 알고 있지만 충분히 일반적입니까? 이 질문에 답하기 위해 우리는 다음 진술에 신빙성을 부여하는 Church-Turing Thesis를 살펴봅니다.
계산 가능한 모든 것은 튜링 기계로 계산할 수 있습니다.
튜링이 튜링 기계를 계산 모델로 개발한 동안 Alonzo Church는 람다 미적분학으로 알려진 계산 모델도 개발했습니다. 이 모델은 강력합니다. 왜냐하면 그것들은 계산을 설명하고 오늘날의 어떤 컴퓨터나 그 문제에 있어서는 어떤 컴퓨터와도 같은 방식으로 그렇게 하기 때문입니다. 이것은 우리의 발견이 과거, 현재, 그리고 그 이후의 모든 가능한 컴퓨터에 적용될 것이라는 것을 알고 우리가 추구하는 해결할 수 없는 문제를 설명하기 위해 튜링 기계를 사용할 수 있음을 의미합니다.
인식 가능성 및 결정 가능성
우리는 해결할 수 없는 문제, 즉 언어 인식기와 언어 결정기의 개념을 구체적으로 설명하기 전에 배경을 조금 더 다루어야 합니다.
언어를 인식하는 튜링 기계가 있으면 언어를 인식할 수 있습니다.
그리고
언어를 결정하는 튜링 기계가 있으면 언어가 결정될 수 있습니다.
언어의 인식자가 되려면 튜링 기계는 해당 언어의 모든 문자열을 수락해야 하며 해당 언어가 아닌 모든 문자열을 수락해서는 안 됩니다. 그러한 문자열을 거부하거나 반복할 수 있습니다. 결정자가 되려면 튜링 기계는 수용하거나 거부함으로써 항상 입력을 중단해야 합니다.
여기에서 입력 중단이라는 아이디어가 중요합니다. 사실, 우리는 결정자가 인식자보다 더 강력하다는 것을 알 수 있습니다. 또한 문제는 해결할 수 있습니다. 즉, 함수가 설명하는 언어를 결정하는 튜링 기계가 있어야만 함수가 결정될 수 있습니다.
결정 불가능
컴퓨터 프로그램을 작성한 적이 있다면 프로그램이 실행될 때 컴퓨터가 바퀴를 돌고 있는 것을 보는 것만으로도 그 자리에 앉아 있는 느낌을 분명히 알고 있을 것입니다. 프로그램에 시간이 오래 걸리는지 아니면 무한 루프를 일으키는 코드에 오류가 있는지 알 수 없습니다. 컴파일러가 실행될 때 코드가 중지되거나 영원히 반복되는지 확인하기 위해 코드를 확인하지 않는 이유가 궁금할 수도 있습니다.
컴파일러에는 단순히 수행할 수 없기 때문에 이러한 검사가 없습니다. 컴파일러 엔지니어가 충분히 똑똑하지 않거나 리소스가 부족한 것은 아닙니다. 임의의 컴퓨터 프로그램이 중지되었는지 여부를 확인하는 것은 불가능합니다.
튜링 기계를 사용하여 이를 증명할 수 있습니다. 튜링 기계는 문자열로 설명할 수 있으므로 셀 수 있는 수가 있습니다. M 1 , M 2 등이 모든 튜링 기계의 집합을 구성한다고 가정합니다. 다음 함수를 정의합시다.
여기서 <M>은 "M의 문자열 인코딩"에 대한 구문이며, 이 함수는 M j 를 입력으로 받아 중단하면 1을 출력하고 그렇지 않으면 0을 출력하는 문제를 나타 냅니다 . M i 는 중단되어야 한다는 점에 유의하십시오(즉, 결정자여야 함). 이것은 결정 불가능한 기능(즉, 해결할 수 없는 문제)을 기술하기를 원하기 때문에 필요합니다.
이제 자체 설명을 허용하지 않는 튜링 머신의 문자열 인코딩으로 구성된 언어 L 도 정의해 보겠습니다.
예를 들어, 어떤 기계 M 1 은 입력 <M 1 >에 0을 출력할 수 있고 다른 기계 M 2 는 입력 <M 2 >에 1을 출력할 수 있습니다. 이 언어가 결정 불가능하다는 것을 증명하기 위해 우리는 언어 L을 결정하는 기계인 M L 이 입력으로 자신의 설명 < ML >이 주어졌을 때 무엇을 하는지 묻습니다. 두 가지 가능성이 있습니다.
M L 허용 < ML >
또는
M L 거부 < ML >
M L 이 자체 인코딩을 허용하면 < ML >이 언어 L에 있지 않음을 의미합니다. 그러나 그런 경우라면 M L 은 처음부터 인코딩을 수락하지 말았어야 했습니다. 반면에 M L 이 자체 인코딩을 허용하지 않는 경우 < ML >은 언어 L이므로 M L 은 문자열 인코딩을 수락해야 합니다.
두 경우 모두, 언어 L이 결정 불가능함을 증명하는 역설 또는 수학 용어로 모순이 있습니다. 따라서 우리는 첫 번째 해결할 수 없는 문제를 설명했습니다.
정지 문제
우리가 방금 설명한 문제는 관련이 없어 보일 수 있지만, 실질적으로 중요한 추가 풀 수 없는 문제, 특히 정지 문제로 축소될 수 있습니다.
빈 문자열에서 멈추는 튜링 기계의 인코딩 언어.
정지 문제는 컴파일러가 이전의 무한 루프를 감지할 수 없는 이유에 대한 질문에 적용됩니다. 프로그램이 빈 문자열에서 종료되는지 여부를 결정할 수 없다면 실행으로 인해 무한 루프가 발생하는지 어떻게 결정할 수 있습니까?
이 시점에서 우리는 간단한 결론에 도달하기 위해 손을 흔드는 것처럼 보일 수 있습니다. 그러나 우리는 실제로 어떤 튜링 기계도 컴퓨터 프로그램이 중단되거나 루프에 영원히 남을지 여부를 말할 수 없다는 것을 깨달았습니다. 이것은 실제 응용에서 중요한 문제이며 튜링 기계나 다른 종류의 컴퓨터에서는 풀 수 없습니다. iPhone은 이 문제를 해결할 수 없습니다. 코어가 많은 데스크탑은 이 문제를 해결할 수 없습니다. 클라우드는 이 문제를 해결할 수 없습니다. 누군가가 양자 컴퓨터를 발명하더라도 정지 문제를 해결할 수는 없습니다.
요약
계산 가능성 이론을 검토하면서 우리는 계산 논증으로 단어의 일반적인 의미에서 계산할 수 없는 함수가 얼마나 많은지 보았습니다. 우리는 튜링 기계를 공식화하기 위해 펜과 종이에 대한 자신의 경험에서 영감을 얻은 튜링까지 거슬러 올라가 계산이 의미하는 바를 정확하게 정의했습니다. 우리는 이 모델이 현재의 컴퓨터나 미래의 컴퓨터가 할 수 있는 모든 것을 계산할 수 있는 방법을 보았고 전혀 계산할 수 없는 문제의 부류를 깨달았습니다.
그러나 계산 가능성에는 단점이 있습니다. 문제를 해결할 수 있다고 해서 빨리 해결할 수 있는 것은 아닙니다. 결국, 수천만 년 후 태양이 우리를 덮치기 전에 컴퓨터의 계산이 끝나지 않는다면 컴퓨터가 무슨 소용이 있겠습니까?
계산 가능한 기능과 언어를 뒤로하고 이제 계산 복잡성, 효율적인 계산 및 유명한 P 대 NP 문제 조사에 대해 논의합니다.
복잡성
느린 대 빠른
컴퓨터 과학자들은 다양한 종류의 문제를 인식하며, 우리가 관심을 갖고 있는 두 가지 종류에는 컴퓨터가 신속하거나 효율적으로 해결할 수 있는 문제( P )와 해법을 빠르게 확인할 수 있지만 빨리 얻을 수 없는 문제( NP )가 있습니다.
예를 들어, 당신이 온라인 데이트 서비스를 위한 알고리즘 개발을 담당하고 있는데 누군가 “모두 데이트를 할 수 있나요?”라는 질문을 던진다고 가정해 보겠습니다. 대답은 모든 사람이 페어링되도록 호환 가능한 개인을 페어링하는 것으로 요약됩니다. 이 문제를 해결하기 위한 효율적인 알고리즘이 있음이 밝혀졌습니다. 이 문제는 집합 P 에 있습니다.
사용자 중 가장 큰 파벌을 식별하려면 어떻게 해야 할까요? 파벌이란 서로 호환되는 가장 큰 개인 네트워크를 의미합니다. 사용자 수가 적으면 이 문제를 빠르게 해결할 수 있습니다. 사용자가 3명인 파벌을 쉽게 식별할 수 있습니다. 그러나 더 큰 파벌을 찾기 시작하면서 문제는 점점 더 해결하기 어려워집니다. 이 문제는 집합 NP 에 있습니다.
형식적 정의
P 는 다항식 시간에 풀 수 있는 문제의 집합입니다. 즉, 계산 단계의 수는 문제 크기에 대한 다항식 함수에 의해 제한됩니다. 우리는 "모두가 데이트를 할 수 있습니까?"라는 것을 알고 있습니다. 이분법 일치 문제라고도 하는 질문은 P 에 있습니다.
NP 는 다항식 시간에 확인할 수 있는 문제 집합입니다. 물론 여기에는 P의 모든 문제가 포함됩니다. 그러나 이 격리가 엄격한지 여부는 알 수 없습니다. 우리는 효율적으로 검증할 수 있지만 효율적으로 해결할 수 없는 문제를 알고 있지만 그 문제가 진정으로 다루기 힘든 것인지는 모릅니다. 파벌 문제가 그러한 문제 중 하나입니다. 우리는 솔루션을 효율적으로 검증할 수 있다는 것을 알고 있지만 문제를 효율적으로 해결할 수 있는지 확신할 수 없습니다.
마지막으로 NP-complete 는 NP 에서 가장 어려운 문제들의 집합입니다. NP 의 어떤 문제라도 효율적으로 NPC 로 변환할 수 있기 때문에 가장 어렵다고 합니다. 결과적으로 누군가가 NPC 에서 문제에 대한 효율적인 솔루션을 식별하면 전체 NP 클래스가 P 에 흡수됩니다. 도당 문제는 NPC 에도 있습니다.
따라서 우리는 P 대 NP 문제에 도달합니다. 많은 컴퓨터 과학자와 수학자들은 P 와 NP 가 같지 않다고 굳게 믿습니다. 만약 그렇다면, 그 의미는 심오하지 않을 것입니다. 오늘날의 디지털 인프라의 대부분은 P 에 없는 문제가 NP 에 있다는 사실에 의존합니다. 그렇지 않은 경우, 예를 들어 암호화 방법은 하룻밤 사이에 붕괴되어 NPC 문제에 대한 효율적인 솔루션을 보유한 사람이 가장 엄격한 보안 프로토콜도 전복시킬 수 있습니다.
다루기 쉬운 미묘함
컴퓨터 과학 초심자에게는 매칭 문제와 파벌 문제의 차이가 별 것 아닌 것처럼 보일 수 있습니다. 사실, P 의 문제와 NP 의 문제 사이의 차이는 매우 미묘할 수 있습니다. 차이를 구별할 수 있다는 것은 실제 세계에서 알고리즘을 설계하는 모든 사람에게 중요합니다.
최단 경로 문제를 고려하십시오. 두 위치가 주어졌을 때 목표는 그들 사이의 최단 경로를 식별하는 것입니다. iPhone은 이것을 밀리초 단위로 계산합니다. 이것은 계산적으로 다루기 쉬운 문제입니다.
다른 한편, 목표가 가능한 가장 짧은 거리를 여행하면서 출발지에서 끝나는 가능한 목적지의 하위 집합을 방문하는 것인 여행하는 세일즈맨 문제를 고려하십시오. 이 문제는 최단 경로 문제와 유사하지만 NP 완전합니다. 또한 공급망 물류가 10억 달러 규모의 산업인 이유를 설명합니다.
우리는 실제로 더 미묘할 수 있습니다. 최단 경로(P)를 요청하는 대신 주기가 없는 가장 긴 경로를 요청할 수 있습니다. 가장 긴 경로 문제도 NP-완전한 것으로 밝혀졌습니다.
이 미묘한 차이의 더 많은 예가 있습니다. 예를 들어 이분법 대 일반 그래프의 정점 덮개 식별 또는 절당 2개 대 3개의 리터럴이 있는 부울 공식의 만족을 포함합니다. 요점은 문제가 P 또는 NP에 있는지 여부가 즉시 명확하지 않으며 이것이 실행 시간 분석이 중요한 기술인 이유입니다. 설계해야 하는 알고리즘이 P의 문제에 대한 것이라면 효율적인 솔루션이 있다는 것을 알고 있습니다. 반면에 문제가 NP에 있는 경우 일반적으로 알고리즘이 문제를 해결하는 데 너무 오래 걸리기 때문에 솔루션 추구에 반대하는 강력한 사례가 있습니다.
요약
복잡성에 대한 이 조사에서 우리는 문제 P와 NP의 클래스를 정의했습니다. P는 비공식적으로 컴퓨터로 효율적으로 해결할 수 있는 문제를 나타내고 NP는 효율적으로 확인할 수 있는 문제를 나타냅니다.
아무도 P가 NP와 같지 않다는 것을 증명할 수 없었습니다. 이 두 종류의 문제가 동등한지 여부는 P 대 NP 문제로 알려져 있으며, 모든 수학은 아니지만 오늘날 이론적 컴퓨터 과학에서 가장 중요한 공개 문제입니다. 실제로, 2000년에 Clay Math Institute는 P 대 NP 문제를 수학에서 가장 중요한 7가지 공개 질문 중 하나로 지정했으며 이 문제의 해결책을 결정하는 증명에 대해 백만 달러의 현상금을 제공했습니다.
결론
이 기사에서 우리는 "컴퓨터란 무엇인가?"와 같은 큰 질문에 답하면서 계산 가능성과 복잡성의 영역을 탐구했습니다. 세부 사항이 압도적일 수 있지만 기억할 가치가 있는 몇 가지 중요한 내용이 있습니다.
정지 문제와 같이 단순히 계산할 수 없는 것이 있습니다.
NPC의 문제처럼 효율적으로 계산할 수 없는 것들이 있습니다.
세부 사항보다 더 중요한 것은 계산 및 계산 문제에 대해 생각하는 방식입니다. 직장 생활과 일상 생활에서 우리는 전에 본 적 없는 문제에 직면할 수 있으며, 검증된 진정한 도구와 기술을 사용하여 최선의 행동 방침을 결정할 수 있습니다.
Toptal 엔지니어링 블로그에 대한 추가 정보:
- 처음부터 통역사 작성에 접근하는 방법