1P by neo 2023-10-19 | favorite | 댓글 1개
  • 본문은 Collatz와 유사한 문제를 해결하지 않고서는 중지 여부를 증명할 수 없는 3 상태, 3 심볼 튜링 기계에 대해 논의하며, 이로 인해 BB(3,3) 문제는 이 Collatz와 유사한 문제를 해결하는 것만큼 어렵다고 말하고 있다.
  • 저자는 "quasihalt" 여부를 증명하기 위해 Collatz와 유사한 문제의 효율적인 시뮬레이션 또는 완전한 해결을 요구하는 튜링 기계(TMs)의 가족을 언급한다.
  • 저자는 일반적인 Busy Beaver 게임에서 예시를 찾아왔으며, Busy Beaver 게임에 결과를 제공하는 많은 TMs를 발견했다.
  • 저자는 "Bigfoot"라는 TM을 소개하는데, 이는 남아 있는 160개의 비공식 BB(3,3) 저항군 중 하나이다.
  • Bigfoot의 행동은 b와 c에 대한 Collatz와 유사한 함수를 반복하면서 a가 누적 합계를 유지하는 것으로 설명된다.
  • 저자는 마르코프 체인 이론을 사용하여 Bigfoot의 행동을 설명하고, Bigfoot가 "probviously" 결코 중지되지 않는다고 결론 내린다.
  • 저자는 우리가 두 가지 세계 중 하나에 살고 있다고 제안하며, Bigfoot가 중지되거나 영원히 실행되는 세계이며, 우리는 두 번째 세계에 살고 있다고 믿는다.
  • 저자는 이러한 종류의 기계를 "Cryptids"라고 부르는 것을 제안하며, 이는 Loch Ness Monster나 Chupacabra와 같은 전설적인 생물에 대한 비유를 그린다.
  • 저자는 이 문제를 공격하는 방법에 대한 아이디어를 초대하며, BB(3,3) 증명이 여전히 가능하다는 희망을 표현한다.
  • 저자는 결론적으로 그의 경험에서, Collatz와 유사한 문제에 대해 물어볼 수 있는 질문은 상대적으로 증명하기 쉬운 것과 수학자도 증명하는 방법을 모르는 것 두 가지 유형만 있다고 말한다.
Hacker News 의견
  • BB(3, 3)의 복잡성에 대한 논의, Collatz 유형의 문제로 알려져 있지만, 편향된 행동과 단일 궤적만을 고려해야 한다는 점 때문에 반드시 어렵지 않을 수 있다는 주장.
  • 748 상태의 튜링 기계에 대한 논의, ZFC(Zermelo-Fraenkel 집합 이론과 선택 공리)가 일관성이 없다면 중단되는 기계. BB(748) 단계에서 이 기계를 실행하는 것의 함의와 Gödel의 두 번째 불완전성 정리와의 잠재적 모순에 대한 혼란 표현.
  • 저자의 글쓰기 스타일이 명료하고 간결하여 독자들이 장황하지 않게 주제를 이해하는 데 도움이 된다는 칭찬.
  • BB (Busy Beaver)가 계산 불가능하다는 의미와 BB가 성장함에 따라 모든 것을 증명해야 하는지에 대한 질문 제기.
  • 모든 BB(x, y) 문제들이 Collatz와 같은 문제로 축소될 수 있으며, 따라서 x와 y의 어떤 값에 대한 BB(x, y)를 찾는 것도 Collatz와 같은 문제로 축소될 수 있다는 제안.
  • Beeping Busy Beavers (BBB)가 왜 훨씬 더 오래 실행되기 전에 준-중단할 수 있는지에 대한 질문, 중단 상태를 사용할 필요가 없기 때문일 수 있다는 제안.
  • 중단 문제가 실제 세계의 귀납에 미치는 영향에 대한 의문, 주어진 튜링 기계가 출력 테이프에 다른 것을 출력할 것인지 결정할 수 있는 오라클이 포함된 가상 시나리오.
  • 이러한 주제를 이해하는 데 필요한 사전 지식에 대한 질문, 좋은 기초를 제공할 특정 주제나 과목에 대한 요청.
  • 특정 문자열, 1RB2RA1LC_2LC1RB2RB_---2LA1LA를 어떻게 읽어야 하는지에 대한 질문.