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"를 참 또는 거짓으로 명확히 정의해야 함