该项目为一个简单的图灵机模拟器，输入图灵机程序和纸带的初始字符串然后模拟一个多纸带图灵机的工作。 项目的所有代码都在turing-project目录下。
本框架依赖于cmake进行编译，需安装3.13.0以上版本的cmake方可使用。
该项目使用cmake编译，编译方式如下：
- 在含有
CMakeLists.txt的文件夹下，使用指令cmake -B build； - 在含有
CMakeLists.txt的文件夹下，使用指令cd ./build; make。
编译之后，在bin目录下会生成一个名为turing的可执行文件，该可执行文件就是一个多纸带图灵机模拟器。
该模拟器是一个命令行工具，使用如下格式的命令运行：
truing [-v|--verbose] [-h|--help] <图灵机程序文件>.tm <纸带的初始符号串>其中-v|--verbose可以令图灵机模拟器打印每一步运行时的状态，包括图灵机的状态、所有纸带的内容、已经经过的步数和是否接受输入纸带上的字符串。
-h|--help可以打印帮助信息。
图灵机程序文件为一个文本文件，名称应以.tm结尾，语法如下所示。
众所周知，一个图灵机可以形式化的定义为一个多元组${Q, \Sigma, \Gamma, \delta, q_0 ,B ,F}$：
-
$\Sigma$ ：磁带上的符号 -
$\Gamma$ ：接受的符号，包含$\Sigma$ - B：在$\Gamma - \Sigma$中，默认写在磁带的空格子上，表示空。
-
$\delta$ ：输入状态和写在当前所在格子上的字符，输出状态，要往磁带上写的符号和操纵磁带移动的方向 - q0初始状态
- Q：状态集
- F：终止状态集
我们的图灵机程序语法为：
-
分号
';'后边的字符串会被认为是注释而不会被模拟器解析，空行会被忽略。 -
状态集 Q:以 #Q 开头。占据 (且仅占据) 图灵机程序的一行(即不包括回车换行); '#' 为该行的第 一个字符 (以下2-7同);各状态之间以英文逗号 ',' 分隔。状态用一个或多个非空白字符 (字母、数字 0-9 和下划线 _ ) 表示，称为该状态的标签，如 "10" 、 "a" 、 等。语法 格式为 。 两边各有一个空格 (以下2-7同)。
示例：
#Q = {0,cp,cmp,mh,accept,accept2,accept3,accept4,halt_accept,reject,reject2,reject3,reject4,reject5,halt_reject} -
输入符号集 S:以 #S 开头。各符号之间以英文逗号 ',' 分隔。输入符号的可取值范围为除
' '(space) 、','、';'、'{'、'}'、'*'、'_'外的所有ASCII 可显示字符(定义参见维基百科)。语法格式为#S = {s1,s2,...,sj}。示例:
#S = {0,1} -
纸带符号集 G:以 #G 开头。各符号之间以英文逗号 ',' 分隔。纸带符号的可取值范围为除
' '(space)、','、';'、'{'、'}'、 '*' 外的所有 ASCII 可显示字符，规定用'_'表示空格符号。语法格式为#G = {s1,s2,...,sk}。示例:
#G = {0,1,_,t,r,u,e,f,a,l,s} -
初始状态 q0:以
#q0开头。语法格式为#q0 = q。示例:
#q0 = 0 -
空格符号 B:以 #B 开头。语法格式为
#B = _。在本项目中，空格符号规定为'_'。示例:
#B = _ -
终结状态集 F:以 #F 开头。各状态之间以英文逗号
','分隔。语法格式为#F = {f1,f2,...,fn}示例：
#F = {halt_accept} -
纸带数 N:以 #N 开头。语法格式为
#N = n。示例：
#N = n -
转移函数 delta:每个转移函数占用 (且仅占用) 图灵机程序的一行，行内容为一个五元组。五元组格式为:
"<旧状态> <旧符号组> <新符号组> <方向组> <新状态>"，元组各部分之间以一个空格分隔。-
新旧状态集/符号组中的符号为上面提到的状态集/符号集中的元素
-
旧符号组中的字符若为
'*'则代表除了空字符之外的任何字符都可以被匹配；新符号组中的字符若为'*'则不改变纸带该位置的内容 -
方向组 由 n 个以下三个符号之一组成的字符串表示:
'l'、'r'或者'*'，分别表示向左 移动、向右移动和不移动。
示例：
;如下转移函数是给一个拥有两个纸带的图灵机设计的 cmp 01 __ rl reject ;当前处于状态 cmp，两个带头下符号分别为 '0' 和 '1'，向两个纸带的当前位置写入空字符，下一步第一个带头向右移动，第二个带头向左移动，下一个状态为 reject idle ** ** ** idle ;当前处于状态idle，只要两条纸带的当前位置不是空字符就不改变当前位置内容也不移动两条纸带，且不改变状态 copy 0* 00 ll copy ;当前处于状态copy，第一条纸带的带头下符号为 '0' ，第二条纸带的带头下符号为'0'或 '1' 中的任意一个，将要写入的新符号为 '0' 和 '0'，下一步两个带头均向左移动，下一个状态为copy -
如果存在语法错误，程序会输出syntax error，你也可以查阅TMreader.cpp并给语法错误添加更详细的报错。
我提供了两个样例图灵机程序以供参考 :
- case1.tm的功能为：在第一条纸带上输入m个'a'和n个'b'，停机时会在第一条纸带上输出m*n个'c'，其余输入会被认为是不合法的。
- case2.tm的功能为：判断纸带上的输入字符串是否是一个 被'c'分隔，'c'前后两个子串只由'a', 'b'构成且'c'前后两个子串相同 的字符串。