6. Define an infinite 0,1 sequence as follows: starting from 0, repeatedly replace each 0 with 001 and each 1 with 0.
(a) Is this sequence periodic?
(b) What is the 1000th digit in this sequence?
(c) At which position does the 10000th 1 appear?
(d) Find the formula for the positions of the digit 1 (3, 6, 10, 13, ...) and the formula for the positions of the digit 0.
6. (a) First, find the pattern of the sequence: $W_{1}=0, W_{2}=001, W_{3}=W_{2} W_{2} W_{1}$. Using mathematical induction, we can prove that $W_{k+1}=W_{k} W_{k} W_{k-1}$. Let $a_{k}, b_{k}$ be the number of digits 0 and 1 in $W_{k}$. Then $a_{k+1}=2 a_{k}+a_{k-1}, b_{k}=a_{k-1}$, and let $t_{k}=\frac{a_{k}}{a_{k-1}}$, then $t_{k+1}=\frac{a_{k+1}}{a_{k}}=2+\frac{1}{t_{k}}$. Taking the limit as $n \rightarrow \infty$, we get $t=2+\frac{1}{t}$ or $t=\sqrt{2}+1$, indicating that $\frac{a_{k}}{b_{k}}$ tends to an irrational number. For this infinite 0,1 sequence, we have the following conclusions: $\frac{\text{number of 0s}}{\text{number of 1s}} \rightarrow \sqrt{2}+1, \frac{\text{number of 0s}}{\text{total digits}} \rightarrow \frac{\sqrt{2}+1}{2+\sqrt{2}}=\frac{1}{\sqrt{2}}$, $\frac{\text{number of 1s}}{\text{total digits}} \rightarrow \frac{1}{2+\sqrt{2}}$. Thus, every $2+\sqrt{2}$ digits, there is 1 occurrence of 1, i.e., the position of the $n$-th 1 is approximately $(2+\sqrt{2}) n$ digits, and the position of the $n$-th 0 is approximately $\sqrt{2} n$ digits.
To solve the next problem, we need the following table:
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline$n$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\
\hline$a_{n}$ & 1 & 2 & 5 & 12 & 29 & 70 & 169 & 408 & 985 & 2378 & 5741 & 13860 \\
\hline$b_{n}$ & 0 & 1 & 2 & 5 & 12 & 29 & 70 & 169 & 408 & 985 & 2378 & 5741 \\
\hline$a_{n}+b_{n}$ & 1 & 3 & 7 & 17 & 41 & 99 & 239 & 577 & 1393 & 3363 & 9119 & 19601 \\
\hline
\end{tabular}
(b) Using the table, we know that the 1000th digit is within the word $W_{9}$. However, $W_{9}=W_{8} W_{8} W_{7}$. The length of this word is $577+577+239$. Thus, the 1000th digit is within the word $W_{8} W_{8}$. Further expanding, we get $W_{8} W_{7} W_{7} W_{6}$. Removing the last $W_{6}$, and expanding the last $W_{7}$, we get $W_{8} W_{7} W_{6} W_{6} W_{5}$. Continuing to remove the last term and expanding the previous term, we finally get $W_{8} W_{7} W_{6} W_{5} W_{5} W_{2}$, which is a word of length 1000. Therefore, the 1000th digit is the last digit of $W_{2}$, which is 1.
(c) Similarly, we get the word $W_{12} W_{11} W_{9} W_{8} W_{8} W_{6} W_{3} W_{3}$, whose last digit 1 is the position of the 10000th 1 in the sequence. Adding the lengths of these 8 sub-words gives 34142, i.e., $[(10000(2+\sqrt{2})]$.
(d) It can be proven that the positions of the $n$-th 1 and the $n$-th 0 are $f(n)=[(2+\sqrt{2}) n]$ and $g(n)=[\sqrt{2} n]$, respectively.