▲

GN⁺: 다섯 번째 Busy Beaver로 연구자들, 계산 한계에 접근

 (quantamagazine.org)
1P by neo 3달전 | favorite | 댓글 1개

  • 도입부

    • 40년 전, 독일 도르트문트에서 컴퓨터 과학자들이 모여 다섯 번째 바쁜 비버를 찾기 위해 경쟁했음
    • 바쁜 비버는 간단한 컴퓨터 프로그램으로, 실행 시간이 매우 길어짐
    • 이 프로그램들은 수학의 유명한 미해결 문제들과 관련이 있으며, 컴퓨터 과학의 오래된 문제에서 비롯됨
    • 2년 전, 대학원생 Tristan Stérin이 바쁜 비버 챌린지를 시작했으며, 전 세계에서 20명 이상의 기여자가 참여함
    • 오늘날, 팀은 BB(5)의 값을 47,176,870으로 확인했음

  • 멈출 것인가, 멈추지 않을 것인가

    • 바쁜 비버 프로그램은 튜링 기계라는 이론적 컴퓨터를 위한 명령어로 작성됨
    • 튜링 기계는 무한 테이프에 0과 1을 읽고 쓰며 계산을 수행함
    • 튜링 기계가 멈출지 영원히 실행될지 예측하는 문제를 멈춤 문제라고 함
    • 멈춤 문제는 일반적인 해결책이 없으며, 이는 바쁜 비버 사냥을 더욱 매력적으로 만듦

  • 비버의 등장

    • 수학자 Tibor Radó는 1962년에 바쁜 비버 게임을 발명함
    • 각 규칙 그룹에서 가장 오래 실행되는 튜링 기계를 바쁜 비버라고 부름
    • BB(n)은 n개의 규칙을 가진 바쁜 비버 기계가 멈추기 전까지 걸리는 단계 수를 나타냄

  • 브래디의 비버 무리

    • Allen Brady는 1960년대에 바쁜 비버 사냥 기술을 개발했으며, 1974년에 네 번째 바쁜 비버 값을 결정함
    • BB(4)는 107단계 후에 멈추는 기계로 확인됨

  • 다섯 번째 비버

    • 1984년 도르트문트 대회에서 다섯 번째 바쁜 비버를 찾기 위한 첫 번째 큰 사냥이 시작됨
    • 1989년, Heiner Marxen은 47,176,870단계 후에 멈추는 기계를 발견함
    • 2003년, Georgi Georgiev는 43개의 해결되지 않은 튜링 기계를 남기고 BB(5) 사냥을 중단함

  • 모든 사냥꾼을 호출

    • Tristan Stérin은 2022년에 바쁜 비버 챌린지를 시작했으며, 전 세계의 기여자들이 참여함
    • Shawn Ligocki는 2022년에 팀에 합류하여 중요한 기여를 함
    • Justin Blanchard는 팀의 가장 강력한 기술 중 하나인 폐쇄 테이프 언어 방법을 개발함

  • 괴물의 접근

    • Skelet #1과 #17은 특히 어려운 기계로, 팀은 이를 해결하기 위해 다양한 아이디어를 결합함
    • 2023년 5월, mxdys라는 익명의 기여자가 Coq 증명을 완료함

  • 비버가 돌아다니는 곳

    • 팀은 공식적인 학술 논문을 작성 중이며, 일부는 다음 비버를 찾기 위해 노력 중임
    • BB(6)는 Collatz 추측과 유사한 문제로 인해 해결이 어려울 것으로 보임

GN⁺의 의견

  • 이 기사는 컴퓨터 과학의 한계를 탐구하는 흥미로운 사례를 제공함
  • 바쁜 비버 챌린지는 협력적 연구의 중요성을 보여줌
  • BB(5)의 해결은 컴퓨터 과학 및 수학 커뮤니티에 큰 의미를 가짐
  • 유사한 기능을 가진 프로젝트로는 Collatz 추측 연구가 있음
  • 새로운 기술이나 오픈 소스를 채택할 때는 협력과 재현 가능성이 중요함
▲
neo 3달전  [-]
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단계 지수의 탑)임
답변달기