2
주어진 n-state가 busy beaver game 인 경우 busy beaver function이 고유하거나 동일한 최대 점수를 갖는 여러 함수가있을 수 있습니까? 아마도 어느 쪽이든 입증되지 않았습니까?바쁜 비버 기능은 n-state 바쁜 비버 게임에 고유합니까?
A
답변
2
@PengOne이 지적한대로이 함수는 실제로 고유합니다. 이것은 완전히 정의 된 N -> N 이산 함수입니다.
그러나 공식 ("또는 최대 점수가 동일한 여러 기능이있을 수 있습니다")에서 동일한 최대 값을 제공하는 여러 개의 비자가 있는지 여부를 알고 싶다는 것도 이해할 수 있습니다. 그렇다면, 네, 적어도 2 개의 busy-beavers가 N이고, 하나는 단순히 교대를 뒤집어서 다른 하나로부터 구성됩니다.
+0
그렇다면 왜 함수가 고유하지 않습니까? – Daniel
+0
신경 쓰지 마세요. 이해 했어. 매핑이 동일하기 때문에 중간 단계 만 다릅니다. 고맙습니다. – Daniel
+0
@ 대니얼, 나는 비표준 용어를 사용하고 있다고 생각합니다. 표준 용어 (예 : 링크 된 Wikipedia 기사에서 사용되는)는 비버 비버 기능이 모든 n-state 튜링 기계의 최대 점수를 알려주는 함수라는 것입니다. 하나의 기능 만 있습니다. 그러나이 최대치를 달성하는 여러 튜링 기계가 있습니다 (Luchian Grigore 언급). 이 기계들은 Turing 기계 언어의 프로그램으로 생각할 수 있습니다. 당신은 여기에 혼란을 일으킨 기능을 호출하는 것처럼 보입니다. – sligocki
3
예, 그렇습니다.
바쁜 비버
함수는 그것이 수행 (라도 이것을 증명)하는 있으면\Sigma(n) = max { \sigma(M) | M is a halting n-state 2-symbol Turing machine}
있는 최대 고유 수 있도록 정의된다. 이것은 단지 숫자입니다.
따라서 \ Sigma (n)도 고유하므로 이산 함수 \ Sigma : N -> N도 고유합니다. \ Sigma를 연속 함수로 확장하는 방법은 여러 가지가있을 수 있지만, 왜 누군가가 이것을하고 싶은지는 저 밖에 있습니다.
\ Sigma의 작은 값을 계산할 수 있습니다. 알려진 가장 큰 값인 OEIS entry을 확인하십시오.
1
이 오래 전에 요청했지만, 나는이 흥미로운 발견 또한 http://www.win.tue.nl/~wijers/shallit.pdf
을, 나는 짐승이 3 상태 바쁜 비버 문제를 강제하는 알고리즘을 코딩하고, 나에게 약 22 비를했다 대칭 구성은 6 개의 기호를 생성합니다 (연속적이든 아니든). 즉, 상태 1과 상태 2를 바꿀 수 있고 첫 번째 전환을 역으로 수행 할 수 있다고 생각하면 아마 60 가지 구성이있을 수 있습니다.
그러나 이것은 '가장 긴 실행'이 아닌 생성 된 기호의 양에만 해당됩니다.
매우 흥미로운 질문이지만 http://cstheory.stackexchange.com/에 더 적합할까요? –