▲

GN⁺: 이론 컴퓨터 과학의 좀비 오해

 (scottaaronson.blog)
1P by neo 2달전 | favorite | 댓글 1개

이론 컴퓨터 과학의 좀비 오해

서론

  • Michael Sipser의 "Introduction to the Theory of Computation" 교과서에는 완벽한 과제가 있음
  • 과제: "f:{0,1}*→{0,1} 함수가 신의 존재 여부에 따라 1 또는 0을 반환할 때, f는 계산 가능한가?"
  • 답: "예, f는 계산 가능함" (상수 함수는 계산 가능하기 때문)

계산 가능성의 개념

  • 계산 가능성은 함수나 무한 시퀀스에 적용됨
  • 개별 예/아니오 질문이나 개별 정수에는 적용되지 않음
  • 프로그램 작성의 난이도는 계산 가능성과 무관함

P 대 NP 문제

  • P 대 NP 문제는 개별 예/아니오 질문임
  • NP-난해성은 함수나 언어에 적용됨
  • P 대 NP 문제는 계산 불가능하거나 NP-난해할 수 없음

Busy Beaver 함수

  • Busy Beaver 함수는 계산 불가능함
  • BB(6) 같은 개별 정수는 계산 가능함
  • BB 함수 전체가 계산 불가능함

이론 컴퓨터 과학의 좀비 오해

  • 무한 시퀀스와 함수에 적용되는 개념을 개별 정수와 열린 문제에 잘못 적용하는 것
  • 할팅 문제의 계산 불가능성과 괴델 불완전성을 혼동하는 것

독자에게 질문

  • 이 좀비 오해를 어떻게 막을 수 있을지 독자에게 질문

GN⁺의 정리

  • 이 글은 이론 컴퓨터 과학에서 자주 발생하는 오해를 다룸
  • 계산 가능성은 함수나 무한 시퀀스에 적용되며, 개별 정수나 예/아니오 질문에는 적용되지 않음
  • P 대 NP 문제는 개별 질문으로, NP-난해성 개념과는 무관함
  • Busy Beaver 함수는 계산 불가능하지만, 개별 값은 계산 가능함
  • 이 글은 이론 컴퓨터 과학의 기본 개념을 명확히 이해하는 데 도움이 될 것임
▲
neo 2달전  [-]
Hacker News 의견

  • Kolmogorov 복잡성을 계산하는 알고리즘의 존재 여부는 무한성과 관련이 있음

    • 임의의 길이를 가진 문자열의 Kolmogorov 복잡성을 계산하는 알고리즘은 존재하지 않음
    • 하지만 길이가 n보다 작은 문자열의 Kolmogorov 복잡성을 계산하는 알고리즘은 존재함
    • 이는 모든 가능한 문자열에 대한 거대한 조회 테이블을 만드는 방식으로 가능함
    • 유한한 문제는 항상 프로그램으로 해결할 수 있지만, 무한한 문제는 그렇지 않음

  • 구성적 수학이 사람들의 직관과 더 잘 맞는다는 의견

    • P=NP 문제에 대한 프로그램이 존재한다는 증거는 아직 없음
    • Mark Braverman은 모든 (이차) Julia 집합이 계산 가능하다고 증명했지만, 이는 균일하게 계산 가능하지 않음
    • 구성적 수학에서는 복소 평면을 여러 영역으로 나누어 각 영역 내의 Julia 집합이 컴팩트함을 증명함

  • 정지 문제의 결정 불가능성을 이해하기 어려운 이유

    • "return true"와 "return false" 프로그램 중 하나는 항상 올바른 답을 제공함
    • 결정 가능성은 무한한 기계/입력 조합으로 확장될 때만 결정 불가능해짐

  • 모달 논리가 필요한 문제의 표현

    • "f가 계산 가능한가?"라는 질문은 모달적으로 잘못된 질문임
    • "f가 계산 가능할까?"라는 질문이 더 정확함
    • 이는 컴파일러 지시문이나 pragma와 유사함

  • 함수 f의 혼란스러운 표현

    • 함수 f는 "God exists"의 값에 따라 분기하지 않음
    • f가 0이든 1이든 계산 가능함
    • 혼란은 자유 변수를 분기 조건으로 밀어넣는 것에서 발생함

  • 결정 가능성, 계산 가능성, 존재 등의 의미 차이

    • 학문적 맥락과 일상적 맥락에서 의미가 다름
    • 큰 숫자는 학문적으로 존재하고 계산 가능하지만, 실제로는 우주에 맞지 않음

  • "God exists"와 관련된 질문의 문제점

    • "God exists"가 참인지 거짓인지 명확하지 않음
    • 이는 자연 언어와 수학을 혼합할 때 발생하는 문제임

  • 이론 컴퓨터 과학과 복잡도 이론이 CS 학부생에게 어려운 이유

    • NP-hard와 같은 용어는 대중적 비유와 상상으로 대체됨

  • 블로그의 텍스트 강조 방식에 대한 불만

    • 선택된 텍스트의 배경색이 변경되지 않아 직관적이지 않음

  • "God exists"를 다른 수학적 명제로 대체하는 제안

    • "God exists"를 참 또는 거짓으로 명확히 정의해야 함
답변달기