设计一个图灵机,它将输入两个非负数并对它们执行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;擦除分隔符及其后的所有内容,然后将所有磁带符号更…

2019年11月17日 0条评论 50点热度 阅读全文