题目描述

图灵机是由数学家艾伦·麦席森·图灵（ $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$ 。

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

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

程序输出的状态转移表示例： $---$ $q0$ , $1$ ,#, $R$ , $q1$ $q1$ ,#,#, $R$ , $q0$ $===$

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

对于不知道如何使用程序输出状态转移表的同学，请按下面的示例，用 Python $3$ 语言提交状态转移表： $print("""---$ $q0$ , $1$ ,#, $R$ , $q1$ $q1$ ,#,#, $R$ , $q0$ $===""")$

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