튜링의 원리를 다시 살펴보고 모순을 통한 증명의 힘을 느껴보세요

알고리즘은 어디에나 존재하며, 정확한 수학적 용어로 표현될 수 있는 모든 문제에는 그에 상응하는 알고리즘이 있는 것 같습니다. 그러나 실제로는 단순해 보이는 일부 문제는 결코 알고리즘으로 해결될 수 없습니다. 컴퓨터 과학자의 선구자인 앨런 튜링(Alan Turing)은 거의 100년 전에 한 논문에서 이 문제를 "계산할 수 없음"으로 증명했습니다. 현대 컴퓨터 과학을 시작한 계산 수학 모델.

Turing은 반직관적인 전략을 사용하여 이 획기적인 결과를 보여주었습니다. 그는 문제를 해결하려는 모든 시도를 거부하는 문제를 정의했습니다. MIT 대학원생 라훌 일랑고(Rahul Ilango)는 "예를 들어 내가 당신에게 무엇을 하고 있는지 묻는다면 당신의 대답이 무엇이든 '내가 할 일은 당신이 말한 것과 다르다'고 답할 것"이라고 말했다. 이론적인 컴퓨터 과학. 재작성된 콘텐츠: 튜링은 반직관적인 전략으로 이 획기적인 결과를 보여주었습니다. 그는 문제를 해결하려는 모든 시도에 저항하는 문제를 정의했습니다. "예를 들어, 당신이 무엇을 하고 있는지 묻는다면, 당신의 대답이 무엇이든, 나는 '내가 할 일은 당신이 말한 것과 다르다'라고 말할 것입니다."라고 이론 컴퓨터를 전공하는 대학원생 Rahul Ilango는 말했습니다. science at MIT

Turing의 전략은 "대각선 증명"으로 알려진 오랜 수학적 방법을 기반으로 합니다. 다음은 그의 증명 뒤에 있는 논리에 대한 간단한 설명입니다.

Strings

대각선 증명은 각 비트가 0 또는 1의 값을 가질 수 있는 문자열 문제를 해결하기 위한 영리한 트릭에서 비롯됩니다. 문제에 대한 설명은 다음과 같습니다. 문자열 목록이 주어지면 목록에 있는 모든 문자열의 길이가 같습니다. 목록에 없는 새 문자열을 어떻게 생성할 수 있습니까?

재작성된 콘텐츠: 가장 간단한 전략 중 하나는 가능한 모든 문자열을 순서대로 고려하는 것입니다. 각각 5비트를 갖는 5개의 문자열이 있다고 가정합니다. 먼저 반복하여 목록에 00000이 있는지 확인하십시오. 존재하지 않으면 문제가 해결된 것입니다. 존재한다면 00001로 이동하여 프로세스를 반복하십시오. 이 접근 방식은 간단하지만 긴 문자열로 인해 긴 목록의 경우 속도가 느립니다.

대각선은 존재하지 않는 문자열을 점진적으로 구축하는 데 실행 가능한 대안으로 밝혀졌습니다. 목록에 있는 첫 번째 문자열의 첫 번째 비트부터 시작하여 이를 반대로 하면 이것이 새 문자열의 첫 번째 비트가 됩니다. 그런 다음 두 번째 문자열의 두 번째 비트를 뒤집어 새 문자열의 두 번째 비트로 사용하고 목록 끝에 도달할 때까지 이를 반복합니다. 비트 연산을 반대로 하면 새 문자열이 원래 목록의 모든 문자열과 최소한 한 위치씩 다른지 확인할 수 있습니다. (또한 문자열 목록에서 대각선을 형성하므로 대각선 증명이라는 이름이 붙습니다.)

대각선 증명은 목록의 각 문자열에서 한 비트만 차례로 확인하면 되므로 일반적으로 다른 방법보다 훨씬 빠르지만 그것의 진정한 힘은 무한히 긴 문자열 문제를 얼마나 잘 처리하는지에 있습니다.

MIT의 이론 컴퓨터 과학자 Ryan Williams는 "문자열과 목록은 무한할 수 있지만 대각화 방법은 여전히 ​​효과적입니다."라고 말했습니다.

이를 최초로 활용한 George Cantor는 이 분야의 창시자였습니다. 집합이론 수학의 1873년에 그는 대각선을 사용하여 일부 무한한 값이 다른 값보다 크다는 것을 보여주었습니다. 60년 후, 튜링은 이 버전의 대각선 증명을 계산 이론에 적용했습니다

알고리즘의 한계

어떤 알고리즘으로도 풀 수 없는 수학적 문제가 있음을 증명하기 위해 튜링은 이론을 제안했습니다. 이 유형의 문제에는 잘 정의된 입력과 출력이 있지만 입력을 출력으로 변환하는 정의된 프로세스가 없습니다. 튜링은 주로 의사결정 문제에 초점을 맞추고 이 모호한 작업을 더 구체화하려고 노력했습니다. 결정 문제에서 입력은 0과 1로 구성된 문자열이 될 수 있고 출력은 0 또는 1이 될 수 있습니다.

숫자가 소수인지(1과 그 자체로만 나눌 수 있음) 결정하는 것은 결정 문제의 예입니다. - 숫자를 나타내는 입력 문자열이 주어지면 숫자가 소수이면 올바른 출력은 1이고 소수가 아니면 0입니다. 또 다른 예는 컴퓨터 프로그램에서 구문 오류를 확인하는 것입니다. 입력 문자열은 다양한 프로그램의 코드를 나타냅니다. 모든 프로그램은 컴퓨터에 저장되고 실행되는 방식이므로 모든 프로그램을 이런 방식으로 표현할 수 있습니다. 규칙은 코드에 구문 오류가 있으면 1을 출력하고 그렇지 않으면 1을 출력합니다. 0을 출력합니다.

알고리즘이 가능한 모든 입력에 대해 올바른 출력을 생성하는 경우에만 문제를 해결한다고 할 수 있습니다. 한 번이라도 실패하면 문제를 해결하기 위한 일반적인 알고리즘이 아닙니다. 일반적으로 해결하려는 문제를 지정한 다음 이를 해결하기 위한 알고리즘을 찾으려고 합니다. 튜링은 풀 수 없는 문제를 찾을 때 이 논리를 뒤집어 놓았습니다. 그는 가능한 모든 알고리즘의 무한한 목록을 상상했고 대각선화를 사용하여 목록에 있는 모든 알고리즘에 반대되는 퍼즐을 만들었습니다.

20개의 질문으로 구성된 새로운 질문을 상상해 보세요. 특정 개념에서 시작하는 대신, 답변자는 각 질문에 대해 불만의 예를 차례로 제시합니다. 게임이 끝나면 답변자는 질문의 반대들로 완전히 구성된 명제를 설명했습니다

Turing의 대각선 증명 과정은 무한히 긴 알고리즘 목록에서 각 알고리즘에 대해 생각하는 것입니다. "이것은 알고리즘이 문제를 해결할 수 있습니까? 계산 불가능하다는 것을 증명하고 싶나요?" 그것은 마치 게임 경쟁과 같습니다. 윌리엄스는 "이 방법은 원래 문제를 '무한 문제'로 변환한다"고 말했다.

게임에서 이기려면 튜링이 각 알고리즘에서 제시하는 답이 부정이 되는 질문을 설계해야 한다. 이는 첫 번째 알고리즘이 잘못된 답을 출력하게 만든 특정 입력, 두 번째 알고리즘이 실패하도록 만든 또 다른 입력 등을 찾는 것을 의미합니다. 그는 이러한 특별한 입력이 얼마 전 Kurt Gödel이 "이 명제는 증명 가능하지 않습니다"와 같은 자기 참조 주장이 수학 기술의 기초에 문제를 일으킬 수 있음을 보여 주었을 때 사용한 것과 유사한 방법을 사용한다는 것을 발견했습니다.

여기서 핵심은 모든 알고리즘(또는 프로그램)이 0과 1의 문자열로 표현될 수 있다는 것입니다. 이는 오류 검사기 예제와 마찬가지로 알고리즘이 다른 알고리즘의 인코딩을 입력으로 사용할 수 있음을 의미합니다. 원칙적으로 알고리즘은 자체 인코딩을 입력으로 사용할 수도 있습니다.

이런 방식으로 우리는 Turing의 증명에서 언급된 문제와 마찬가지로 계산 불가능한 문제를 정의할 수 있습니다. 알고리즘은 0을 출력하고, 그렇지 않으면 0을 출력합니다. "이 문제를 해결하려고 시도하는 모든 알고리즘은 자체 코드에 해당하는 적어도 하나의 입력에서 잘못된 출력을 생성합니다. 즉, 이 변칙적인 문제는 어떤 알고리즘으로도 해결할 수 없습니다.

증명할 수 없는 것은 모순에 의한 증명입니다

컴퓨터 과학자의 대각선 증명 사용은 여기서 끝나지 않습니다. 1965년에 Juris Hartmanis와 Richard Stearns는 모든 계산 가능한 문제가 동일하지는 않으며 어떤 문제는 본질적으로 다른 문제보다 더 어렵다는 것을 보여주기 위해 Turing의 주장을 적용했습니다. 이 결과는 계산 문제의 어려움을 연구하는 계산 복잡성 이론 분야를 시작했습니다.

복잡성 이론의 발전은 튜링의 대각선 증명의 한계를 드러냅니다. 1975년에 Baker, Gill, Solovy는 복잡성 이론에서 해결되지 않은 많은 문제가 대각화만으로는 해결될 수 없음을 입증했습니다. 그 중 가장 중요한 것은 유명한 P/NP 문제로, 단순히 해의 정확성을 다항식 시간에 검증할 수 있는지, 다항식 시간에 풀 수 있는지에 대한 질문입니다

대각선 증명의 한계는 A입니다. 이를 매우 강력하게 만드는 높은 수준의 추상화의 직접적인 결과입니다. 튜링의 증명은 실제로 발생할 수 있는 계산 불가능한 문제를 포함하지 않았습니다. 대신 문제는 추상적인 경향이 있습니다. 다른 대각선은 실제 세계에서 똑같이 멀리 떨어져 있으므로 실제 문제를 해결할 수 없습니다.

Williams는 "글러브 박스로 실험을 하는 것처럼 대각선 증명은 문제 자체에 직접적으로 영향을 미치지 않습니다."라고 말했습니다.

대각선 증명의 감소 추세는 P/NP 문제를 해결하는 데 오랜 시간이 걸릴 것임을 보여줍니다. 여행. 한계에도 불구하고 대각선 증명은 복잡성 이론가의 핵심 도구 중 하나로 남아 있습니다. 2011년에 Williams는 이를 다양한 기술과 결합하여 제한된 계산 모델로는 엄청나게 어려운 문제를 해결할 수 없음을 입증했습니다. 그 결과 25년 동안 연구자들을 괴롭혔던 문제가 해결되었습니다. 이것이 P/NP 문제를 해결하는 것과는 거리가 멀지만 여전히 상당한 진전을 의미합니다.

무언가 불가능하다는 것을 증명하고 싶다면 부정의 힘을 과소평가하지 마세요

원본 링크:

다시 작성해야 할 내용은 다음과 같습니다: https://www.Quantamagazine.org/alan- 튜링과 부정적인 사고의 힘-20230905/

위 내용은 튜링의 원리를 다시 살펴보고 모순을 통한 증명의 힘을 느껴보세요의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!