你对这个问题有什么看法吗？我不知道它问的是什么 .
我们可以假设单带确定性图灵机是预期的模型 . 还假设所有图灵机都在Q-start开始，磁带头指向最左边的非空白符号（或任何空白符号，如果磁带完全是空白的） .
在每个阶段，TM：
从磁带中读取符号 .
选择下一个要访问的州 .
选择要在磁带上写入的内容 .
选择是向左/向左/向右移动头部 .
我们有8个状态，4个磁带符号（读/写）和3个移动选项（注意：您的模型可能需要磁头向左或向右移动;然后使用2代替） .
我们必须在6个州中指定行为 . 假设不允许崩溃（即，所有行为都以某种方式计算和处理），那么我们有6 x 4 x 8 x 4 x 3 = 2,304图灵机 . 如果我们允许崩溃，我们可以将计算改为6 x 4 x（1 8 x 4 x 3）= 2,328图灵机 . 1允许每个状态和读取磁带符号崩溃或定义响应（状态x写入x移动） .
我可能在那里错过了一些考虑因素，但我提出的问题是要求进行这种分析 .
1 回答
我们可以假设单带确定性图灵机是预期的模型 . 还假设所有图灵机都在Q-start开始，磁带头指向最左边的非空白符号（或任何空白符号，如果磁带完全是空白的） .
在每个阶段，TM：
从磁带中读取符号 .
选择下一个要访问的州 .
选择要在磁带上写入的内容 .
选择是向左/向左/向右移动头部 .
我们有8个状态，4个磁带符号（读/写）和3个移动选项（注意：您的模型可能需要磁头向左或向右移动;然后使用2代替） .
我们必须在6个州中指定行为 . 假设不允许崩溃（即，所有行为都以某种方式计算和处理），那么我们有6 x 4 x 8 x 4 x 3 = 2,304图灵机 . 如果我们允许崩溃，我们可以将计算改为6 x 4 x（1 8 x 4 x 3）= 2,328图灵机 . 1允许每个状态和读取磁带符号崩溃或定义响应（状态x写入x移动） .
我可能在那里错过了一些考虑因素，但我提出的问题是要求进行这种分析 .