图灵机：取两个数字的mod？

  • Z时代
  • 2024-01-10
  • 分类：问答

设计一个图灵机，它将输入两个非负数并对它们执行mod操作，例如mod（3,7）= 3和mod（7,3）= 1。显然，指定关于TM的输入和输出的任何假设和格式。图灵机：取两个数字的mod？

回答：

输入是两个正整数X和Y，由一个分隔符号分隔开。输出是一个单一的数字Z. TM是单面单带确定性的。

首先，向右移动找到分隔符。然后，在X的结尾和Y的开头之间来回跳动，标记符号对。如果在用完Y之前用完了X，则X < Y和X mod Y = X;擦除分隔符及其后的所有内容，然后将所有磁带符号更改为一元数字并停止接受。如果在X之前用完Y，则将X中的标记符号更改为擦除/分隔符，将Y的标记符号恢复为一元数字，并重复（X> = Y，因此X mod Y =（X-Y）mod Y ）。

这是你的2模3如何得到处理：

#110111# 
#1a0b11# 
#aa0bb1# 
#aa##### 
#11#####

这里的3 MOD 2如何得到处理：

#111011# 
#11a0b1# 
#1aa0bb# 
#100011# 
#a000b1# 
#a###### 
#1######

以上是 图灵机：取两个数字的mod？ 的全部内容， 来源链接： utcz.com/qa/260237.html

回到顶部