多带图灵机模型的编程原理
发布网友
共1个回答
热心网友
这个规定就是图灵机的程序，可以用列表的方法给出。开始时，机器处在一个特定的状态q0∈Q。原始数据是一个长度为n的符号串,放在输入带上，输入带头指向该串的最左符号，其余各带全为空白。然后机器严格按规定（程序）一步步动作下去，一直到没有定义而停机。这时输出带上的内容即被认为是计算的结果。对于长度为n的输入,机器从开始到停机的总步数称为串行时间；所用过的工作带上的方格数称为空间；从开始到停机各工作带头改变方向的总次数称为巡回。它们都是n的函数。
