图灵机算法计算 0 并写入二进制中有多少个
我碰巧需要一种用于图灵机的算法，该算法读取一串 0，然后在磁带上以二进制形式写入有多少个 0。
我意识到在实践中机器实际上不会计算 0，但我对如何做到这一点感到非常困惑。
我想首先我需要标记二进制数以 X 或其他内容开头的位置，然后只需为第一个 0 写入 1，对于接下来的每个 0，如果最低有效位是 0，则它会变成1 但如果是 1 呢？也许把它变成 0，然后继续向左将所有 1 变成 0，直到找到 0 或空白来变成 1？话又说回来，在这种情况下，无论 LSB 如何，它都是一样的，因为我会做同样的事情，只有 0 才是第一个位置……
嗯……橡皮鸭……
I happen to need an algorithm for a turing machine that reads a string of 0's and then writes on the tape how many there were in binary.
I realize that in practice the machine won't actually count the 0's but I am pretty stumped as for how to do it.
I supose first of all I'd need to mark the place where the binary number starts with an X or something, then just write a 1 for the first 0 and for each of the following 0s if least significant bit is a 0 it becomes a 1 but what if it's a 1? Maybe turn it into 0 and keep going left turing all 1s into 0s until I find a 0 or blank to turn into 1? Then again, in that case it's the same thing regardless of the LSB because I'd be doing the same only the 0 would be the first position...
Hmm...rubber duckie...
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
假设输入磁带为
#00000000000#，其中初始读取位置为第一个0。向右移动直至到达末尾
#，保持磁带的奇偶校验遇到的0数量（最初是 0，然后是 1，然后是 0，...）。将每对的第一个0替换为-。-读取被忽略，不改变奇偶校验。将奇偶校验写入输出磁带并向左移动（按顺序写入位）
将输入磁头返回到左
#，转到1。在第一遍结束时，输入磁带将为
#-0-0-0-0-0-#，输出为1。第二遍结束时：
#---0---0---#和11。第三遍结束时：
#--------0---#和011。第四遍结束时：
#------------#和1011。Suppose the input tape is
#00000000000#, where the initial read position is the first 0.Move right until the end
#is reached, maintaining the parity of the number of0encountered (initially 0, then 1, then 0,...). Replace the first0of each pair with a-. The-read are ignored and do not change the parity.Write the parity to the output tape and move left (to write bits in order)
Return the input head to the left
#, and goto 1.At the end of the first pass, the input tape will be
#-0-0-0-0-0-#and output is1.At the end of the second pass:
#---0---0---#and11.At the end of the third pass:
#-------0---#and011.At the end of the fourth pass:
#-----------#and1011.查看这个图灵机模拟器及其二进制计数示例程序：
Check out this Turing machine simulator and its binary counting sample program:
编辑：我承认班维尔。
我昨晚想出了我想做什么，它需要两个独立的图灵机，这可能是作弊。
第一台机器的磁头会在输入磁带上运行，如果扫描到 0，则简单地启动第二台机器。
第二台机器只是一个加法机，会将 1 加到当前数字上，这很容易做到，只是很长加法，您可以创建一个状态，表示有余数，然后继续向左移动，直到达到零（并将其替换为 1）或找到一个空白点（并创建 1）。
班维尔赢得了我的投票。
Edit: I concede to Bainville.
I figured out what I wanted to do last night and it required two separate turing machines and thats probably cheating.
The first machine's head would run over the input tape and simply start the second machine if it scanned a 0.
The second machine would simply be an adding machine and would add 1 to the current number, which is fairly easy to do, it's just long addition and you can create a state that says there is a remainder and continue moving left until you reach a zero (and replace it with 1) or find a blank spot (and create a 1).
Bainville wins my vote.