设计计算二进制数奇偶校验的图灵机

Question

所以我在大学里遇到了这个问题，我真的很迷茫，我不知道你能不能帮我，因为这不是严格的代码，我想我必须这样做手写图表。

那么，问题就是设计一个计算二进制数奇偶性的图灵机。如果1的个数是成对的在末尾加0，如果不是成对的在末尾加1。

示例

a) 001001 -> 0010010

b) 101010 -> 1010101

希望你能帮助我，谢谢

Answer 1

输入：一串x二进制数字

输出：xd where d id 0 if #1(x) is even and 1 if #1(x) is odd, where #1(x) 是 x.

中 1 的实例数

设计：我们将从左到右扫描字符串，跟踪到目前为止看到的 1 的实例数的奇偶性。当我们运行出input的时候，我们会看到自己处于哪个状态，写入相应的末尾数字，然后halt-accept.

实施：

q    t    q'   t'   d      comment

q0   0    q0   0    right  see a zero, stay in state and keep looking
q0   1    q1   1    right  see a one, now we've seen odd number, keep looking
q0   B    ha   0    same   ran out after seeing even number

q1   0    q1   0    right  see a zero, stay in state and keep looking
q1   1    q0   1    right  see a one, now we've seen an even number, keep looking
q1   B    hA   1    same   ran out after seeing odd number

设计计算二进制数奇偶校验的图灵机

Design a Turing machine that calculates the parity of a binary number

binary

turing-machines

parity