Phantom Bird

外观

磁带 / FFMP 20250915

约 696 字大约 2 分钟

2025-9-15

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

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

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

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

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

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

答案

（1）

由异或的自逆性可得

f(x)⊕g(x)=⨁it(x+Xi)f(x) \oplus g(x) = \bigoplus_{i} t(x+X_i)

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

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

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

（2）

以下为一个可行的构造。

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

Input:g(x)=1S, 目标支持集为有限集 S⊂ZInitialize:f(x)=1{0},Xi=[ ]（操作列表）// Step 1: 将唯一的 1 移到值域左端s←min⁡S,x0←0while x0≥s−padding:operate at x0,x0−1,x0−2,x0x0←x0−3// Step 2: 生成足够多的 1for i=x0 to x0−∣S∣:operate at i// Step 3: 从右向左写入 S 的每个元素并消除影响for i∈reverse(S):x1←max⁡{x<i∣f(x)=1}for j=x1 to i−1:append j to Xiwhile ∃x∈[s,i) with f(x)=f(x−1)=1:x1←max⁡{x∣f(x)=f(x−1)=1∧x<i}append x1−1 to Xi// Step 4: 将多余的 1 移向负无穷while ∃x<s with f(x)=1:c←max⁡{x∣f(x)=1∧x∉S}if f(c−1)=1:append c−1 to Xielse if f(c−1)=0:append c to Xiappend c−1 to Xiappend c to Xi其中Function operate-at⁡(x):append x to Xifor u∈{x−1,x,x+1}:f(u)←f(u)⊕1\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}

该构造的正确性证明略。

版权归属：Phantom-Bird

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)