• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

图灵机:取两个数字的mod?

automata 来源:Sohaib Aslam 4次浏览

设计一个图灵机,它将输入两个非负数并对它们执行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###### 

版权声明:本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。
喜欢 (0)