Hacker News 의견

• Scott Aaronson의 블로그 포스트에 대한 의견이 공유됨

  • 관련된 이전 스레드 링크가 제공됨

• Busy Beaver 문제의 다양한 변형이 존재함

  • 람다 계산법을 사용한 변형이 있음
  • Kolmogorov 복잡성으로 표현되는 변형이 있음

• 한 엔지니어가 Busy Beaver 문제를 연구하기 위해 직장을 그만둔 이야기가 공유됨

  • 이 엔지니어가 mxdys인지 궁금해함

• Coq 증명에 대한 언급이 있음

  • 처음부터 정리된 증명이 아닌, 처음으로 정리된 증명일 가능성을 제기함

• Tibor Radó의 원래 Busy Beaver 논문이 읽기 쉽고 재미있다는 의견이 있음

  • 현대 버전의 논문 링크가 제공됨

• 5-상태 2-색 Turing 기계 프로그램의 정지 문제가 해결되었음

  • 2-상태 4-색 경우에 대한 적용 가능성을 제기함

• 인간이 정지 문제를 직관적으로 해결할 수 있다는 잘못된 생각에 대한 언급이 있음

• 개인 프로젝트에서 Cutting Stock 문제를 해결하기 위한 프로그램을 작성한 경험이 공유됨

  • Brady의 프로그램과 유사한 최적화 방법을 사용함

• 5-상태 Turing 기계 프로그램의 정지 여부를 증명할 수 있었던 것은 운이 좋았다는 의견이 있음

• Scott Aaronson의 블로그 포스트에 따르면 16,679,880,978,201개의 5-상태 Turing 기계가 존재함

  • 이 중 몇 퍼센트가 정지하는지 궁금해함

• Busy Beaver 함수의 값이 공유됨

  • BB(5)가 47,176,870으로 증명됨
  • BB(6)는 최소 10^10^...^10 (15단계 지수의 탑)임