技术问询：如何构建5状态以内图灵机，将连续≥2个1替换为0并正确停机

我来帮你搞定这个图灵机的问题——你已经有了5状态的雏形，但卡在标准位置停机上，那我们可以调整状态逻辑，用4个工作状态（加上停机状态总共在5个以内）实现需求，全程只向右移动，还能精准在标准位置停机。

核心定义 #

• 符号集合：0、1、□（□表示空白符号，磁带边界）
• 工作状态：
  • S0：初始状态，正常扫描磁带
  • S1：已识别1个孤立的1，等待确认是否连续
  • S2：进入连续1替换模式
  • S3：连续1替换完成后，恢复正常扫描
• 停机状态：H（标准停机状态，读写头停在磁带最后一个有效符号的右侧空白处）

状态转移规则（仅向右移动） #

所有转移的移动方向均为R（向右），完全符合“仅从左向右移动”的要求：

S0（初始/正常扫描状态） #

• 读0：写0，移动R，进入S0
• 读1：写1，移动R，进入S1
• 读□：写□，移动R，进入H（无内容可处理，直接标准停机）

S1（已标记单个1） #

• 读0：写0，移动R，进入S0（这个1是单个，无需替换，回到正常扫描）
• 读1：写0，移动R，进入S2（连续1出现，替换当前1为0，进入替换模式）
• 读□：写□，移动R，进入H（这个1是单个，保留，标准停机）

S2（连续1替换模式） #

• 读0：写0，移动R，进入S3（连续1结束，恢复正常扫描）
• 读1：写0，移动R，进入S2（继续替换下一个连续的1）
• 读□：写□，移动R，进入H（连续1替换完成，标准停机）

S3（替换后恢复扫描） #

• 读0：写0，移动R，进入S3
• 读1：写1，移动R，进入S1（遇到新的单个1，标记后等待确认）
• 读□：写□，移动R，进入H（扫描结束，标准停机）

逻辑说明与示例 #

核心逻辑 #

1. 连续1识别与替换：只有当连续遇到至少2个1时才会触发替换——第一个1被标记（进入S1），第二个1触发替换（进入S2），后续所有连续1都会被改成0，直到遇到0或空白。单个1会被完整保留。
2. 标准停机保障：任何状态下遇到空白符号□时，都会直接进入停机状态H，此时读写头停在磁带最后一个有效符号的右侧空白处，完全符合标准停机位置的要求。

示例验证 #

假设输入磁带为：0 1 1 0 1 1 1 □
处理流程最终得到的磁带为：0 1 0 0 1 0 0 □，读写头停在□位置，正确停机，连续1均被替换为0，单个1保留，完全符合需求。

内容的提问来源于stack exchange，提问作者user486635