#6572. 图灵机实验 1:1 进制加法

内存限制:256 MiB 时间限制:1000 ms 题目类型:交互
上传者: ceba_robot

题目描述

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

实验背景

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

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

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

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

题目

一进制加法本质上就是数 1 的个数。假设是 n 1 m 1 相加,那么结果就是 n + m 1

第一个实验要求设计一个可以完成一进制加法的图灵机。

输入格式

图灵机的输入格式如下:

(若干 1)+(若干 1)=

其中,若干 1 可能为 0 1

输出格式

图灵机的输出格式如下:

#######(若干 1)B####

其中,若干 1 的位置必须从输入中的 = 号右侧开始,以 B 结尾。# 为任一 ASCII 可见字符。

样例

样例输入 1

11+1=

样例输出 1

11+1=111B…

样例输入 2

11+1=

样例输出 2

FBc01111B…

样例输入 3

+11=

样例输出 3

+11=11B…

样例输入 4

+=

样例输出 4

+=B…

样例输入 5

11+=

样例输出 5

11+=11B

数据范围与提示

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

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

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

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

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

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

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

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