콜라코스키 수열
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
콜라코스키 수열은 각 기호가 1개 또는 2개의 연속된 항으로 이루어진 "런"의 길이를 적으면 정확히 동일한 시퀀스가 생성되는 자기 생성 수열이다. 수열의 각 항은 다음 런의 길이를 나타내며, 1과 2가 번갈아 나타난다. 1의 밀도는 1/2로 추정되지만 아직 증명되지 않았으며, 간단한 순환 태그 시스템으로 설명될 수도 있다. 콜라코스키 수열은 알고리즘을 통해 생성될 수 있으며, 선형 시간과 선형 공간을 사용하거나 로그 공간을 사용하여 선형 시간 안에 생성할 수도 있다.
더 읽어볼만한 페이지
- 홀짝성 - 패리티 비트
패리티 비트는 이진 데이터에서 1의 개수가 짝수인지 홀수인지 나타내는 비트로서, 오류 감지 및 수정에 사용되며, 통신 프로토콜과 RAID 시스템 등 다양한 분야에서 활용된다. - 홀짝성 - 반정수
반정수는 정수에 1/2을 더한 수로 표현되며, 정수와 함께 덧셈 연산에 대해 군을 형성하지만 환은 형성하지 않고, 양자역학, 페르미온의 스핀, 4차원 격자 포장 등 다양한 분야에 응용된다. - 프랙탈 - 브라운 운동
브라운 운동은 액체나 기체 속 미세 입자가 매질 분자와 충돌하여 불규칙하게 움직이는 현상으로, 아인슈타인과 스몰루호프스키의 이론적 설명과 페랭의 실험적 검증을 통해 원자 존재 입증에 기여했으며, 확산/랑주뱅 방정식으로 모델링되어 다양한 분야에 응용된다. - 프랙탈 - 프랙탈 우주론
프랙탈 우주론은 우주의 구조가 프랙탈 기하학적 특성을 갖는다는 이론이며, 관측 결과는 우주가 균질하다는 것을 보여주지만, 이론적 연구에서는 큰 규모나 미시적 규모에서 프랙탈 구조를 제안하기도 한다. - 정수열 - 실베스터 수열
실베스터 수열은 각 항이 이전 항들의 곱에 1을 더한 값으로 정의되는 정수 수열로서, 재귀적으로 정의되며 이중 지수 함수적으로 증가하고, 이집트 분수 및 탐욕 알고리즘과 관련이 있으며, 역수 합은 1로 수렴한다. - 정수열 - 소수 (수론)
소수는 1과 자기 자신만을 약수로 가지는 1보다 큰 자연수이며, 무한히 많고 정수론의 기본 정리에서 중요한 역할을 하며 다양한 분야에 응용된다.
| 콜라코스키 수열 | |
|---|---|
| 기본 정보 | |
| 다른 이름 | 자기 생성 수열 |
| 정의 | 수열의 n번째 항은 n번째 런의 길이를 나타냄; 수열은 1과 2로만 구성됨. |
| 시작 값 | a(1) = 1 |
| 수열 | 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, ... A000002 |
| 예시 | 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1 처음의 1은 수열이 "1"로 시작한다는 것을 의미 그 다음의 2는 그 다음의 두 숫자가 "2"라는 것을 의미 그 다음의 2는 그 다음의 두 숫자가 "1"이라는 것을 의미 등등. |
| 성질 | |
| 값의 분포 | 수열에서 1의 비율과 2의 비율은 같음 |
| 비정지성 | 수열은 비정지적임 |
| 역사 | |
| 최초 언급 | William Kolakoski (1965) |
2. 정의
콜라코스키 수열의 초기 정의는 다음과 같다.
:1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,...
각 기호는 1개 또는 2개의 연속된 항으로 이루어진 "런"(동일한 요소의 시퀀스)에서 발생하며, 이러한 런의 길이를 적으면 정확히 동일한 시퀀스가 생성된다.
:1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,2,1,1,2,1,2,2,1,2,2,1,1,2,1,2,2,...
:1, 2 , 2 ,1,1, 2 ,1, 2 , 2 ,1, 2 , 2 ,1,1, 2 ,1,1, 2 , 2 ,1, 2 ,1,1, 2 ,1, 2 , 2 ,1,1, 2 ,...
따라서 콜라코스키 수열에 대한 설명은 반전 가능하다. ''K''가 "콜라코스키 수열"을 의미한다고 할 때, 설명 #1은 논리적으로 설명 #2를 의미한다(그 반대도 마찬가지).
:1. ''K''의 항은 ''K''의 런(즉, 런 길이)에 의해 생성된다.
:2. ''K''의 런은 ''K''의 항에 의해 생성된다.
이에 따라 콜라코스키 수열의 각 항이 하나 또는 두 개의 미래 항의 런을 생성한다고 말할 수 있다. 수열의 첫 번째 1은 "1"의 런, 즉 자체를 생성하고, 첫 번째 2는 "22"의 런, 즉 자체를 포함하고, 두 번째 2는 "11"의 런을 생성하는 식이다. 수열의 각 숫자는 생성될 다음 런의 ''길이''이며, 생성될 ''요소''는 1과 2 사이를 번갈아 가며 나타난다.
:1,2 (수열의 길이 ''l'' = 2; 항의 합 ''s'' = 3)
:1,2,2 (''l'' = 3, ''s'' = 5)
:1,2,2,1,1 (''l'' = 5, ''s'' = 7)
:1,2,2,1,1,2,1 (''l'' = 7, ''s'' = 10)
:1,2,2,1,1,2,1,2,2,1 (''l'' = 10, ''s'' = 15)
:1,2,2,1,1,2,1,2,2,1,2,2,1,1,2 (''l'' = 15, ''s'' = 23)
볼 수 있듯이, 각 단계에서 수열의 길이는 이전 단계의 항의 합과 같다. 이 애니메이션은 이 과정을 보여준다.
수열이 초기 1 없이 작성된 경우에도 유지되는 이러한 자기 생성 속성은 콜라코스키 수열을 자체 표현을 다른 규모로 인코딩하는 프랙탈 또는 수학적 객체로 설명할 수 있음을 의미한다.
2. 1. 자기 생성 성질
콜라코스키 수열의 초기 항은 다음과 같다.:1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,...
각 기호는 1개 또는 2개의 연속된 항으로 이루어진 "런"(동일한 요소의 시퀀스)에서 발생하며, 이러한 런의 길이를 적으면 정확히 동일한 시퀀스가 생성된다.
:1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,2,1,1,2,1,2,2,1,2,2,1,1,2,1,2,2,...
:1, 2 , 2 ,1,1, 2 ,1, 2 , 2 ,1, 2 , 2 ,1,1, 2 ,1,1, 2 , 2 ,1, 2 ,1,1, 2 ,1, 2 , 2 ,1,1, 2 ,...
''K''가 "콜라코스키 수열"을 의미한다고 할 때, ''K''의 항은 ''K''의 런(즉, 런 길이)에 의해 생성되고, ''K''의 런은 ''K''의 항에 의해 생성된다.
이에 따라 콜라코스키 수열의 각 항이 하나 또는 두 개의 미래 항의 런을 생성한다고 말할 수 있다. 수열의 첫 번째 1은 "1"의 런, 즉 자체를 생성하고, 첫 번째 2는 "22"의 런, 즉 자체를 포함하며, 두 번째 2는 "11"의 런을 생성하는 식이다. 수열의 각 숫자는 생성될 다음 런의 ''길이''이며, 생성될 ''요소''는 1과 2 사이를 번갈아 가며 나타난다.
이러한 자기 생성 속성은 콜라코스키 수열을 자체 표현을 다른 규모로 인코딩하는 프랙탈 또는 수학적 객체로 설명할 수 있음을 의미한다.
3. 연구
3. 1. 밀도
콜라코스키 \{1,2\}-수열에서 1의 밀도는 1/2로 추정되지만, 이 추측은 아직 증명되지 않았다. 바츨라프 흐바탈은 1의 상한 밀도가 0.50084 미만임을 증명했다. 닐슨은 더 강력한 계산 능력을 사용하여 0.500080의 경계를 얻었다.수열의 처음 3×108개의 값을 계산한 결과 밀도가 1/2와 약간 다른 값으로 수렴하는 것으로 나타났지만, 수열을 처음 1013개 값까지 확장한 이후의 계산에서는 제한 밀도가 실제로 1/2인 경우 예상할 수 있듯이 1/2 밀도에서 벗어나는 정도가 줄어들었다.
3. 2. 주기성
3. 3. 태그 시스템과의 연관성
콜라코스키 수열은 간단한 순환 태그 시스템의 결과로 설명될 수도 있다. 하지만 이 시스템은 1-태그 시스템이 아닌 2-태그 시스템(즉, 한 번에 하나의 기호가 아닌 기호 쌍을 다른 기호 시퀀스로 대체함)이므로, 태그 시스템이 튜링 완전성을 갖는 매개변수 영역에 속하여, 이 표현을 사용하여 수열에 대해 추론하기 어렵게 만든다.4. 알고리즘
콜라코스키 수열은 ''i''번째 반복에서 이미 수열의 ''i''번째 값으로 출력된 값 ''x''''i''를 읽는 알고리즘에 의해 생성될 수 있다(또는 그러한 값이 아직 출력되지 않은 경우 ''x''''i'' = ''i''로 설정). 그런 다음, ''i''가 홀수이면 숫자 1을 ''x''''i''개 복사하여 출력하고, ''i''가 짝수이면 숫자 2를 ''x''''i''개 복사하여 출력한다.
알고리즘의 처음 몇 단계는 다음과 같다.
- 첫 번째 값은 아직 출력되지 않았으므로 ''x''1 = 1로 설정하고 숫자 1을 1개 복사하여 출력한다.
- 두 번째 값은 아직 출력되지 않았으므로 ''x''2 = 2로 설정하고 숫자 2를 2개 복사하여 출력한다.
- 세 번째 값 ''x''3은 두 번째 단계에서 2로 출력되었으므로 숫자 1을 2개 복사하여 출력한다.
- 네 번째 값 ''x''4는 세 번째 단계에서 1로 출력되었으므로 숫자 2를 1개 복사하여 출력한다.
이 알고리즘은 선형 시간이 걸리지만, 수열의 이전 위치를 참조해야 하므로 전체 수열을 저장해야 하므로 선형 공간이 필요하다. 서로 다른 속도로 수열의 여러 복사본을 생성하는 대안적인 알고리즘은 각 수열의 복사본이 이전 복사본의 출력을 사용하여 각 단계에서 무엇을 할지 결정하며, 로그 공간만 사용하여 선형 시간 안에 수열을 생성하는 데 사용할 수 있다.
5. 더불어민주당 관점에서의 추가 설명 (인물)
참조
[1]
OEIS
[2]
서적
Substitutions in dynamics, arithmetics and combinatorics
Springer-Verlag
[3]
저널
Problem 5304
[4]
저널
Exponent trajectories in symbolic dynamics
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com