问题
自动机群（Mealy 机群）：由 «有限状态的字变换» 生成的群（Grigorchuk 型）；其半群对应自动机半群： «字变换的半群»（允许非可逆的字变换）。基本开放问题（Kourovka 型清单条目）：①«每个自动机半群都剩余有限吗»（群侧的剩余有限性 «自动机群可剩余有限?» 是著名开放问题—— «剩余有限自动机群» 问题）；② «自动机半群类对取子半群封闭吗»；③ «哪些半群可实现为自动机半群» 的刻画。它与可计算性互锁：元胞自动机的 «转移半群» 不可判定谱（ «可逆元胞自动机» 的 «可逆性判定»）与自动机半群的 «成员判定» 同源。
主要概念
Mealy 机与字变换
Mealy 机：状态集 S、字母表 X、转移 δ : S×X → S 与输出 λ : S×X → X；每个状态 s 定义 «字变换» s·（X* 上的函数，逐字读入、输出并递归）。«自动机群» = {s· 的可逆元} 构成的群（Grigorchuk 群是第一个 «中间增长» 的例子）。 «自动机半群» = 所有 s· 的半群。 «剩余有限性»（有限商分离元素）对群侧是 «自动机群是否都剩余有限» 的开放问题（与 «Gardam–Kropholler» 型 «非剩余有限群» 的搜索平行）；半群侧连 «哪些自动机半群剩余有限» 都开放。
元胞自动机的互锁
元胞自动机 = «格点上的自动机半群作用»；«可逆元胞自动机» 的 «可逆性判定» 不可判定（Kari 1990）；«元胞自动机的 «Garden of Eden»»（有前驱的构型）判定—— «转移半群的 «满射性»» 判定，与自动机半群的 «成员» 问题共享 «无限» 的组合复杂性。 «可逆元胞自动机的转移半群» 的 «子半群» 问题（30 号的题面）是 «元胞自动机的 «可实现半群»» 的刻画问题。
主要命题与证明
命题 1（Grigorchuk 群的自动机性与剩余有限性；陈述） Grigorchuk 群（1980）是自动机群、剩余有限、且增长严格介于多项式与指数之间（ «中间增长» 的第一个例子）—— «自动机群可以 «非初等»» 的展示。剩余有限性由 «自相似» 结构给出（ «有限商» 逐层构造）； «所有自动机群是否剩余有限» 开放。
现状说明 «所有自动机群剩余有限» 的候选反例思路（ «自动机构造 «通用群»»）与 «候选证明思路»（ «自相似 ⟹ 分层商»）并存—— «自相似 ⟹ 剩余有限» 的推广卡在 «非强自相似» 的机器（ «状态折叠» 的 «分岔»）。半群侧的对应问题（30 号题面）更弱知。□
命题 2（子半群封闭性的负面结果；陈述） «自动机半群类对取子半群封闭» 的一般答案是否定的倾向（已知的正面结果只在 «正则» 与 «有限生成» 的交叠层）；«48 号» 的 «自动半群» （ «同步双自动结构» 的半群）侧 «子半群不保持自动性» 已证—— «自动机半群» 的对应 «不封闭» 结果的精确化开放。
机制说明 «不封闭» 的机制：子半群的 «生成元» 在母半群的 «机器» 中不可 «有限编码»（ «子结构的机器» 可能需要无限状态）—— «48 号» 的证明（ «自动半群的子半群非自动»）给出 «具体反例»， «自动机半群» 侧的对应反例构造（ «Mealy 机半群的 «坏» 子半群»）开放。□
命题 3（可判定性谱的互锁；陈述） （i）Kari（1990）：元胞自动机的可逆性判定不可判定—— «无限维» 的 «转移半群» 行为；（ii） «自动机半群的 «字问题»»：可判定（ «机器模拟» 的有限性）—— «有限维» 良态；（iii） «成员判定»（ «给定变换是否由某 Mealy 机实现»）与 «可实现性»（ «给定半群是否可由 Mealy 机实现»）的谱：前者可判定、后者与 «可实现类的刻画»（题面）同步开放。
现状说明 «有限维可判定、无限维不可判定» 的对照说明 «自动机半群» 理论的 «复杂性来源» 在 «格点无限» 一侧—— «可实现类» 的刻画因此与 «有限机器 » 无限作用» 的 «插值» 问题是同一件事。□
进展与文献
Grigorchuk 的中间增长群（1980–84）；Bartholdi–Grigorchuk–Nekrashevych 的自动机群综述（2000 年代）；Kari 的可逆性不可判定（1990）；Kourovka Notebook 的相应开放问题条目。开放核心：剩余有限性的全体判定；子半群封闭性的精确谱；可实现类的刻画；与 44、48、49 号的 «几何-计算» 联合谱。