컴퓨터가 해결할 수 없는 문제가 있습니까? 그리고 예를 들어, "우리 모두가 같은 색을 보나요?", "하늘이 정말 파랗습니까?"등과 같은 깊은 철학적 질문에 도전했습니다. 그리고 GPT-3는 자신이 알고 있는 인간을 설득력 있게 속일 수 있을지도 모릅니다. 답변, 정말 그렇지 않습니다. 불행히도, 당신은 매우 모호하고 정의가 잘못된 문제에 직면해 있습니다. 컴퓨터가 이러한 문제를 해결할 수 있는지 여부는 문제가 너무 잘못 정의되어 수학적으로 모델링할 수 없고 "해결됨"을 명확하게 정의할 수 없기 때문입니다.

그럼 문제의 다른 부류를 살펴보겠습니다. 생각해 보면 "이 데이터 비트를 JSON에서 데이터베이스로 이동", "이 모든 숫자를 함께 추가"등과 같이 매우 잘 정의된 문제를 컴퓨터에 지시합니다. 그래서, 이런 종류의 질문은 컴퓨터가 답을 낼 수 없는 잘 정의된 질문이 있습니까?

글쎄, 우리는 컴퓨터가 사소하게 해결할 수 있다는 것을 알고 있는 한 부류의 문제가 있습니다. 컴퓨터가 풀 수 없는 100% 확신으로 우리가 알고 있는 잘 정의된 문제의 예를 살펴보겠습니다.

정지 문제

내가 당신의 제품 관리자이고 당신은 프로그램을 디버그하는 도구를 만드는 회사에서 일하고 있다고 상상해 보십시오. 주어진 코드 조각이 결국 실행을 멈출지 알려주는 프로그램을 만들어 주시겠습니까? 또한 이 사용 사례에서는 I/O를 수행하는 프로그램을 무시한다고 가정합니다. I/O의 세계는 지저분하고 우리는 주로 계산 버그에 관심이 있습니다. "중단"을 종료하는 프로그램을 호출합니다.

음, 직관적으로 몇 가지 단위 테스트로 시작할 수 있습니다.

def test_halts?
  expect(halts?("1+1")).to be true
  expect(halts?("while true; end")).to be false
end

1과 1을 더하는 프로그램은 실제로 거의 즉시 실행을 분명히 중지합니다. 영원히 반복되는 프로그램은 분명히 그렇지 않습니다. 이 문제는 잘 정의되어 있습니다. 프로그램을 사용하고 중지되는지 확인하십시오. 이것은 매우 명확한 날에 이것을 컴퓨터에 표현할 수 있다는 점에서 JSON 파싱의 경우와 유사합니다. 이것을 해결할 수 없는 이유를 살펴보겠습니다.

이제 위의 두 입력에 대해 작동하는 halts? 구현을 간단하게 녹아웃할 수 있습니다. 그러나 더 복잡한 경우는 어떻습니까? 배열에 대한 매핑은 어떻습니까? 루프를 포함하는 조건문은 어떻습니까? 꼬인 재귀 논리가 있는 복잡한 중첩 while 루프는 어떻습니까? "이 문제에 대한 솔루션을 사례별로 두드리고 결국에는 모든 것을 다룰 수 있을 것입니다."라고 생각할 수도 있습니다. 확실히 이렇게 하면 일부 프로그램을 다룰 수 있지만 친애하는 독자 여러분, 일반적인 경우에서 빌드halts?는 매우 불가능하다는 것이 밝혀졌습니다.

당신은 이 문제를 해결할 수 없습니다

이 문제는 상당히 해결할 수 없는 것으로 나타났습니다. 이에 대한 형식적 증명은 매우 복잡하지만 직관적인 증명은 몇 줄의 코드로 표시할 수 있습니다. 이미 halts? 함수를 작성했다고 가정해 봅시다. 그와 함께 다음 경우를 고려하십시오.

def do_the_opposite
  # here we are passing this function, “do_the_opposite”
  # to halts?, effectively asking it halts? whether or not
  # do_the_opposite ever finishes executing.
  if halts?(“do_the_opposite”)
    while true
    end
  else
    exit
  end  
end

우리가 말하는 것은:

halts?가 do_the_opposite 멈춘다고 생각하면 do_the_opposite가 영원히 반복됩니다

.

halts?가 do_the_opposite가 영원히 실행된다고 생각하면 do_the_opposite가 즉시 종료됩니다.

이것은 모순에서 halts? 함수를 잡습니다. 그것은 틀림이 틀림없습니다. 즉, 모든 프로그램이 실행을 마치면 정확하게 알려주는 함수를 정의할 수 없습니다. 이것은 모순에 의한 증명의 정의입니다. halts? 함수의 존재는 논리적으로 불가능한 우주가 존재한다는 것을 의미합니다.

이것이 왜 흥미로운가요? 글쎄, 그것은 우리에게 현대 프로그래밍 언어, 강력한 유형 시스템 등의 모든 힘에도 불구하고 여전히 해결할 수 없는 몇 가지 문제가 있음을 더 광범위하게 알려줍니다. 또한 우리가 해결할 수 없는 많은 문제가 우리가 자체적으로 작업하는 코드와 관련되어 있음을 알려줍니다. 정지 문제가 말하는 내용에 대해 더 자세히 알고 싶다면 church-turing thesis