查看源代码：
FFMP-20250915.md

---
title: 磁带 / FFMP 20250915
createTime: 2025/9/15
---

对于一个函数 $f: \mathbb{Z} \to \{0, 1\}$，若存在一个有限集合 $S$ 使得 $\forall x \in \mathbb{Z}, x \in S \iff f(x)=1$，则称 $f$ 是（$S$ 对应的）磁带函数。

一个磁带函数列 $\{f_i(x)\}$ 对一个磁带函数 $t(x)$ 是美妙的，当且仅当对于任意 $i\in\mathbb{N}$，以下两个命题至少有一个成立：

1. $f_{i+1}(x)=f_i(x)$
2. $f_{i+1}(x) = f_i(x) \oplus t(x+X_i), f_i(X_i)=1$  
   其中 $a \oplus b = \begin{cases} 0, &a=b \\ 1, &a \ne b \end{cases}$

是否存在磁带函数 $t(x)$，对于任意的磁带函数 $g$，都有对 $t$ 美妙的函数列 $\{f_i(x)\}$ 满足 $f_0(x)$ 是 $\{0\}$ 的磁带函数，且

（1）$\exists N \in \mathbb{N}, \forall n>N, \forall x \in \mathbb{Z}, f_n(x)=g(x)$？

（2）$\forall x \in \mathbb{Z}, \exists N \in \mathbb{N}, \forall n>N, f_n(x)=g(x)$？

:::details 答案

（1）

由异或的自逆性可得

$$
f(x) \oplus g(x) = \bigoplus_{i} t(x+X_i)
$$

而它的取值范围为全体磁带函数。

将磁带函数映射到二进制数（因为有限，所以可以映射），  
设 $S_\oplus(t) = \{F \mid \exists \{a_i\}, F=\bigoplus_i 2^{a_i} t \}$，  
易证 $S_\oplus(t) \subseteq \{0\} \cup [t, +\infty)$，于是 $S_\oplus(t) = \mathbb{N} \iff t=1$。

对应的 $t(x)$ 只有一位为 $1$，显然不行。

（2）

以下为一个可行的构造。

$t(x)$ 为 $\{-1, 0, 1\}$ 对应的磁带函数，$\{X_i\}$ 依照以下伪代码给出：

$$
\begin{aligned}
&\textbf{Input:} \quad g(x) = 1_S, \text{ 目标支持集为有限集 } S \subset \mathbb{Z} \\
&\textbf{Initialize:} \quad f(x)=\mathbf{1}_{\{0\}}, X_i = [\,] \quad \text{（操作列表）} \\[6pt]

&\textbf{// Step 1: 将唯一的 1 移到值域左端} \\
&s \gets \min S,\quad x_0 \gets 0 \\
&\textbf{while } x_0 \ge s - \text{padding}: \\
&\quad \text{operate at } x_0, x_0-1, x_0-2, x_0 \\
&\quad x_0 \gets x_0 - 3 \\[6pt]

&\textbf{// Step 2: 生成足够多的 1} \\
&\textbf{for } i = x_0 \text{ to } x_0 - |S|: \\
&\quad \text{operate at }i \\[6pt]

&\textbf{// Step 3: 从右向左写入 S 的每个元素并消除影响} \\
&\textbf{for } i \in \text{reverse}(S): \\
&\quad x_1 \gets \max \{x < i \mid f(x) = 1\} \\
&\quad \textbf{for } j = x_1 \text{ to } i - 1: \\
&\qquad \text{append } j \text{ to } X_i \\
&\quad \textbf{while } \exists x \in [s, i) \text{ with } f(x) = f(x-1) = 1: \\
&\qquad x_1 \gets \max \{x \mid f(x) = f(x-1) = 1 \land x < i\} \\
&\qquad \text{append } x_1 - 1 \text{ to } X_i \\[6pt]

&\textbf{// Step 4: 将多余的 1 移向负无穷} \\
&\textbf{while } \exists x < s \text{ with } f(x) = 1: \\
&\quad c \gets \max \{x \mid f(x) = 1 \land x \notin S\} \\
&\quad \textbf{if } f(c - 1) = 1: \\
&\qquad \text{append } c - 1 \text{ to } X_i \\
&\quad \textbf{else if } f(c - 1) = 0: \\
&\qquad \text{append } c \text{ to } X_i \\
&\qquad \text{append } c - 1 \text{ to } X_i \\
&\qquad \text{append } c \text{ to } X_i \\[6pt]

&\text{其中} \\[6pt]

&\textbf{Function } \operatorname{operate-at}(x): \\
&\quad \text{append } x \text{ to } X_i \\
&\quad \textbf{for } u \in \{x-1, x, x+1\}: \\
&\qquad f(u) \gets f(u) \oplus 1 \quad \\
\end{aligned}
$$

该构造的正确性证明略。

:::