투에-모스 수열

이 그래픽은 투에 모스 수열의 반복적이고 상보적인 생성을 나타낸다. 수학에서 **투에-모스 수열**(Thue-Morse sequence), 또는 **프로헷-투에-모스 수열**(Prouhet-Thue-Morse sequence)은 0에서 시작해서 앞의 수열의 불 보수를 덧붙여서 얻어지는 이진 수열 (0과 1의 무한수열)이다. 처음 몇 단계를 거치면 투에-모스 수열의 앞부분인 수열의 첫 단계는 0, 그 다음 단계는 01, 0110, 01101001, 0110100110010110,…을 얻을 수 있다. 전체 수열은 다음과 같이 시작한다. :01101001100101101001011001101001.... id=A010060
# 정의
투에-모스 수열을 정의하는 여러 동등한 방법들이 있다.
## 직접 정의
*n*번째 원소 *tn*을 계산하려면 *n*을 이진수로 써야 한다. 이 이진 표현에서 1의 개수가 홀수라면 *tn* = 1이고, 짝수면 *tn* = 0이다.p=15 따라서 존 호턴 콘웨이 *외*는 *tn* = 1을 만족하는 수 *n*을 *불쾌한* 수(*odious* number, 홀수를 뜻하는 *odd*에서 나왔다)라고 부르고 *tn* = 0일 때는 *악한* 수(*evil* number, 짝수 *even*때문)라고 불렀다. 다시 말해, *n*이 악한 수일 때는 tn = 0이고 *n*이 불쾌한 수일 경우에는 tn = 1이다. 이 방법은 투에-모스 수열을 계산하는 빠른 방법이다. 먼저 *t0* = 0에서 시작하고, 각각의 *n*에 대해 *n*의 이진 표기에서 *n* − 1의 이진 표기와 다른 최상위 비트를 찾는다. (이 비트는 *x*를 *n*과 *n* − 1의 비트 단위 XOR이라 두고, *x*를 오른쪽으로 한 비트 옮기고 *x*와 옮긴 값의 비트 단위 XOR을 취함으로 남길 수 있다.) 이 비트가 짝수 인덱스에 있다면, *tn*은 *t**'n* − 1과 다르고, 아니면 *t**'n* − 1과 같다. 따라서 이 알고리즘은 각 수열의 요소를 생성하는데 상수 시간이 걸리며 메모리의 로그 개수의 비트 (상수 개수의 단어)만을 사용한다.2011
## 점화식
투에-모스 수열은 모든 음이 아닌 정수 *n*에 대하여 다음 점화식을 만족시키는 수열 *tn*이다. :{| | *t*0 || = 0, |- | *t*2*n* || = *tn*, 그리고 |- | *t*2*n*+1|| = 1 − *tn*. |}
## L-시스템
투에-모스 수열은 morphic word이다.p=11 즉, 투에-모스 수열은 다음의 린덴마이어 시스템의 출력이다: {| class="wikitable" |- ! 변수 0, 1 |- ! 상수 | 없음 |- ! 시작 | 0 |- ! 규칙 | (0 → 01), (1 → 10) |}
## 비트 단위 NOT을 사용한 특성화
위에서 비트의 수열로 주어진 형태의 투에-모스 수열은 비트 단위 NOT을 사용하여 재귀적으로 정의할 수 있다. 첫 번째 원소는 0이다. 처음 2*n*개의 원소가 한번 결정되어 문자열 *s*를 형성하면, 다음 2*n*개의 원소는 *s*의 비트 단위 NOT으로 형성된다. 이제 처음 2*n*+1개의 원소를 정의했으므로 재귀한다. 처음 몇 단계를 자세하게 설명하면, * 0에서 시작한다. * 0 의 비트 단위 NOT을 취한 것은 1이다. * 연결시키면 처음 두 원소는 01이다. * 01 의 비트 단위 NOT을 취한 것은 10이다. * 연결시키면 처음 두 원소는 0110이다. * 0110 의 비트 단위 NOT을 취한 것은 1001이다. * 연결시키면 처음 두 원소는 01101001이다. * 계속한다. 따라서 * *T*0 = 0. * *T*1 = 01. * *T*2 = 0110. * *T*3 = 01101001. * *T*4 = 0110100110010110. * *T*5 = 01101001100101101001011001101001. * *T*6 = 0110100110010110100101100110100110010110011010010110100110010110. * 등등.
## 무한 곱
수열은 다음과 같이도 정의할 수 있다. : \prod_{i=0}^{\infty} (1 - x^{2^{i) = \sum_{j=0}^{\infty} (-1)^{t_j} x^{j} \mbox{,} \\! 이 때, *tj*는 *j* = 0에서 시작했을 때 *j*번째 원소이다.
# 일부 특성
투에-모스 수열의 새로운 부분이 처음 부분에 비트 단위 NOT을 취함으로 만들어졌고, 이것이 다음 블럭의 처음에도 반복되기 때문에, 투에-모스 수열은 *이중 반복*(*square*, 반복되는 연속적인 수열)으로 가득하다. 즉, *XX*의 예가 많이 있고, 이 때 *X*는 어떤 문자열을 의미한다. 당연히 X는 그런 문자열이다 if and only if X =A,\, \overline{A},\, A \overline{A}A,또는 \overline{A}A \overline{A} 여기서 A는 어떤 k\ge 0에 대해 A=T_{k}이고 \overline{A} 는 A의 비트 단위 NOT을 나타낸다 (0과 1을 맞바꾼다).1989 예를 들어 k=0일 때, \ A= T_{0}=0 이고 이중 반복 A \overline{A}AA \overline{A}A = 010010 는 T에서 16번째 비트부터 나타난다. (따라서, T에 있는 이중 반복의 길이는 2의 거듭제곱이거나 2의 거듭제곱의 3배이다.) 하지만, *삼중 반복*(*cubes*, *XXX*의 예)은 없다. 또한 *겹치는 이중 반복*(*overlapping squares*, 0*X*0*X*0이나 1*X*1*X*1의 예)도 없다.p=113p=103 임계 지수는 2이다.2006 모든 *n* > 1에 대해서 *T*2*n*이 회문이라는 것을 주목하자. 더 나아가, q*n*을 *T*2*n*에서 연속적인 0사이의 1을 세서 얻어지는 단어라고 하자. 예를 들면, *q*1 = 2이고 *q*2 = 2102012 등등. 단어 *Tn*은 *겹치는 반복*을 포함하지 않아 결과적으로 단어 *qn*은 회문 이중 반복 없는 단어이다. 투에-모스 열이 "이중 반복으로 가득하다"는 위의 문장은 더 정확하게 만들 수 있다: 이 수열은 *고른 재귀 단어*이고, 고른 재귀 단어는 어떤 유한한 문자열 *X*가 주어지면 결과적으로 길이가 *nX*인 모든 블럭에 *X*가 나타나느 어떤 길이 *nX*(종종 *X*의 길이보다 더 길다)가 있다는 것을 의미한다.p=302010 재귀 단어를 만드는 가장 간단한 방법은 완전히 주어진 수 *m*단계 다음에 완전히 반복되는 주기 수열을 만드는 것이다. 그러면 *nX*는 *X*의 길이의 두 배 보다 긴 *m*의 배수로 둘 수 있다. 하지만 투에-모스 수열은 고른 재귀 수열이지만 주기수열이 아니고 심지어 부분적 주기 수열(일부 비주기 초기치 이후 주기적이 되는것을 의미한다)도 아니다.p=31 **투에-모스 사상**(Thue–Morse morphism)은 이진 수열의 집합에서 수열에 있는 모든 0을 01로, 1을 10으로 바꾸어서 자기 자신에게로 가는 함수 *f*로 정의한다.p=70 그러면 *T*가 투에-모스 수열이라면 *f*(*T*)는 다시 *T*가 나온다. 즉, *T*는 *f*의 고정점이다. 함수 *f*는 자유 모노이드 {0,1}∗과 *T*를 고정점으로 가지는 연장 가능 사상이다. 당연히 *T*는 본직적으로 *f*의 *유일한* 고정점이다. 유일한 다른 고정점은 *T*에 비트 단위 NOT을 취한 것으로 간단히 (0,1)에서 시작하는 것이 아닌 (1,0)에서 시작하는 투에-모스 수열이다. 이 특성은 오토마타 수열의 개념으로 일반화 할 수 있다. 이진 체에서 *T*의 *생성 급수*는 다음 형식적 멱급수이다 :t(Z) = \sum_{n=0}^\infty T(n) Z^n \ . 이 멱급수는 다음의 등식을 만족하는 형식적 멱급수의 체에서 대수적이다p=80 :Z + (1+Z)^2 t + (1+Z)^3 t^2 = 0
## 조합론적 게임 이론에서
*악한 숫자* (t_n=0인 수 n)의 집합은 님 덧셈(비트 단위 배타적 논리합) 아레의 음이 아닌 정수들의 부분집합을 형성한다. Kayles 게임에서, 악한 님 값은 게임에서 매우 적은(유한하게) 상태에서 나타나고 나머지는 모두 다 추악한 님 값을 가진다.
## 프로헷-테리-에스콧 문제
프로헷-테리-에스콧 문제(Prouhet–Tarry–Escott problem)는 다음과 같이 정의할 수 있다. 양의 정수 *N*과 음이 아닌 정수 *k*가 주어졌을 때, 집합 *S* = { 0, 1, ..., *N*-1 }를 아래와 같이 k까지 거듭제곱의 합이 같은 두 서로소 부분집합 *S*0와 *S*1으로 분할하는 것이다. 이 때 *i*는 1에서 *k*까지의 모든 정수를 의미한다. : \sum_{x \in S_0} x^i = \sum_{x \in S_1} x^i 이 문제는 *N*이 2*k*+1의 배수일 때 다음과 같은 솔루션을 가진다. * *S*0은 *S*에서 *tn* = 0인 정수 *n*으로 이루어져 있다, * *S*1은 *S*에서 *tn* = 1인 정수 *n*으로 이루어져 있다. 예를 들어, *N* = 8이고 *k* = 2일 때, :1= 0 + 3 + 5 + 6 = 1 + 2 + 4 + 7, :1= 02 \+ 32 \+ 52 \+ 62 = 12 \+ 22 \+ 42 \+ 72. *N*이 2*k*+1의 배수여야 한다는 조건은 반드시 필요한 것은 아니다. 솔루션이 있는 다른 경우가 일부 존재하지만, 이 조건은 더 강한 특성을 보장한다. 조건을 만족한다면, 등차 수열의 수 *N*개의 *k*제곱을 한 집합은 합이 같은 두 집합으로 분할 할 수 있다. 이것은 등차 수열의 *n*번째 원소를 나타내는 이항에 적용된 이항 정리에 의해 주어진 확장에서 직접적으로 따른다. 투에-모스 수열의 일반화와 두 부분 이상으로 분할하는 프로헷-테리-에스콧 문제에 대해서는 Bolker, Offner, Richman 그리고 Zara의 "The Prouhet –Tarry –Escott problem and generalized Thue –Morse sequences"을 보라.pages=117–133
## 프랙탈과 거북이 그래픽
거북이 그래픽을 사용할 때, 오토마톤이 수열로 프로그래밍 되어있다면 곡선이 만들어진다. 투에-모스 수열의 요소는 프로그램 상태를 만들기 위해 사용된다: * *t*(*n*) = 0일 때, 한 단위 앞으로 이동한다, * *t*(*n*) = 1일 때, 반시계 방향으로 π/3 만큼 회전한다, 나타나는 곡선은 유한한 면적을 가지면서 곡선의 길이가 무한한 프랙탈 곡선인 코흐 눈송이로 수렴한다. 이것은 투메-모스 수열의 프랙탈 성질을 나타낸다.2005
# 역사
투에-모스 수열은 정수론에 적용시킨 외젠 프로헷(Eugène Prouhet)이 1851년에 처음으로 연구를 시작하였다. 하지만, 프로헷은 이 수열을 명시적으로 언급하지 않았다. 이것은 1906년에 악셀 투에에게로 넘겨졌고, 투에는 이 수열으로 단어의 조합론 연구를 시작했다. 이 수열은 1921년 마스턴 모스의 연구에서 모스가 이 수열을 미분기하학에 적용시켰을 때 세상의 주목을 받게 되었다. 이 수열은 수차례 독자적으로 발견되었으며, 수학자들의 전문 연구에서만 발견된 것은 아니다. 예를 들면, 1935년에서 1937년까지 체스 세계 챔피언이였고 수학 교사였던 체스 그랜드마스터인 막스 오이베는 1929년에 체스에서의 적용을 발견하였다. 오이베는 무한히 연장되는 게임을 반복되는 이동에 의해서 무승부를 선언함으로 막는 규칙을 이 수열의 삼중 반복이 없는 특성(위의 문단 참고)을 사용해서 어떻게 회피할 후 있는지를 보였다.