题目描述

图灵机是由数学家艾伦·麦席森·图灵（1912～1954）提出的一种抽象计算模型，即将人们使用纸笔进行数学运算的过程进行抽象，由一个虚拟的机器替代人们进行数学运算一个抽象模型。

实验背景

它由四部分「硬件」组成：一条无限长的纸带、一个读写头、有限长度的状态转移表（有限多个状态）、一个状态寄存器。纸带可以划分成一个个连续的格子，每一个格子上有且只有一个字符。

在此系列实验中，我们要通过设计状态转移表来让图灵机实现特定的功能。

在本题目中，我们对图灵机有如下约定：

• 图灵机的状态应是一个长度不超过 $100$ 的仅包含可见字符的字符串，初始状态为 q0。
• 读写头初始位置在纸带的第 $0$ 格，纸带向正负两个方向无限延伸。纸带每一个有且只有一个 ASCII 可见字符，初始字符为 B。
• 图灵机的输入从纸带的第 $0$ 格开始，向正向延伸。
• 每一时刻，图灵机将按照状态转移表的规则，根据当前状态和当前读写头位置读取的字符，对纸带进行写操作，控制读写头的移动并且在状态之间跳转。当图灵机的状态跳转至 qa 时，认为其停止。
• 由于难以判断图灵机能否停机，测试中图灵机最多模拟 $10000$ 步。若步骤超过 $10000$ 步，则认为图灵机不停机。
• 状态转移表中的一条规则是一个五元组，分别为当前状态、当前字符、写入字符、读写头移动方向、下一状态。当前状态、下一状态是长度不超过 $100$ 的仅包含可见字符的字符串；当前字符和写入字符是ASCII可见字符；读写头移动方向为 L、R、N 三个字符中的一个，分别表示读写头向左、向右移动和不移动。
• 每一条状态转移规则占一行，各部分之间用逗号格开。如，q0,1,#,R,q1。

题目

第二个实验要求设计一个可以完成四位二进制加法的图灵机。在此题目中，输入的两个二进制数，严格的是四位，不足四位的二进制数用 $0$ 补齐。输出的一个二进制数严格为五位，不足的用 $0$ 补足。

输入格式

图灵机的输入格式如下：

(四位01串)+(四位01串)=

输入可能包含前导$0$。

输出格式

图灵机的输出格式如下：

…###(五位 01 串)B###...

其中，五位 01 串的位置必须从输入中的 = 号右侧开始，以 B 结尾。# 为任一 ASCII 可见字符。输出可能包含前导 $0$。

样例 1

1100+1100=

1100+1100=11000B…

0000+0000=

FBc01wexdd00000BcWW…

0001+0000=

0001+0000=00001B…

1111+1111=

1111+1111=11110B…

0011+1010=

####+####=01101B…

数据范围与提示

数据保证有大量的图灵机可以在 $10000$ 步中完成计算。

由于平台限制，我们使用一个伪交互题的方式提交状态转移表。请将写好状态转移表用程序通过标准输出输出，在最前和最后分别添加一行 --- 和 ===。

程序输出的状态转移表示例：

---
q0, 1, #, R, q1
q1, #, #, R, q0
===

当然，你也可以写一个程序，帮你自动生成状态转移表。

对于不知道如何使用程序输出状态转移表的同学，请按下面的示例，用 Python 3 语言提交状态转移表。

print("""---
q0, 1, #, R, q1
q1, #, #, R, q0
===""")

本题源于中国科学院大学（UCAS）计算机科学导论课实验一。