给定一个一元数 (0 = 1, 1 = 11, 2 = 111, 3 = 1111, ...)，在其后面留一个空白符号，并写出同一数的二进制表示形式 (0 = 0, 1 = 1、2 = 10、3 = 11、4 = 100，...）。以相反的顺序写数字是可以接受的（不是必需的）。完成后，TM 应切换到接受状态。无需验证输入，假设输入是 100% 的一元数，并且磁带上没有写任何其他内容。
这是基于 Welbog 提示的解决方案。
TM 会在 1 结束后写入 0 1 空格开始。我们知道磁带上至少会有一个 1。然后，我们可以为第一个空白左侧看到的每个 1 添加一个到二进制表示形式。我们不妨通过将哪些一元 1 更改为 0 来记住我们已经处理过的一元 1。如果我们想像完成时一样将磁带放回去，我们可以在二进制表示左侧的 0 上写回 1。
Q T Q' T' d
-----------------------
q0 1 q0 1 R // scan right to first blank space
q0 # q1 # R // after unary. then, write a 0
q1 # q2 0 L // to start the binary.
q2 # q3 # L // scan left past any binary data
q2 0 q2 0 L // to get to the blank separating
q2 1 q2 1 L // unary and binary
q3 # hA # R // scan left for another unary
q3 0 q3 0 L // digit, ignoring ones that have
q3 1 q4 0 R // been processed. if done, halt.
q4 # q5 # R // scan right to the blank separating
q4 0 q4 0 R // unary and binary
q5 # q2 1 L // add one to the binary representation
q5 0 q2 1 L // by toggling bits until you toggle a
q5 1 q5 0 R // zero to a one, completing the addition
示例：
#111#### => #111#### => #111#### => #111#### => (next line)
^q0 ^q0 ^q0 ^q0
#111#### => #111#0## => #111#0## => #110#0## => (next line)
^q1 ^q2 ^q3 ^q4
#110#0## => #110#1## => #110#1## => #110#1## => (next line)
^q5 ^q2 ^q3 ^q3
#100#1## => #100#1## => #100#1## => #100#0## => (next line)
^q4 ^q4 ^q5 ^q5
#100#01# => #100#01# => #100#01# => #100#01# => (next line)
^q2 ^q2 ^q3 ^q3
#100#01# => #000#01# => #000#01# => #000#01# => (next line)
^q3 ^q4 ^q4 ^q4
#000#01# => #000#11# => #000#11# => #000#11# => (next line)
^q5 ^q2 ^q3 ^q3
#000#11# => #000#11# => #000#11#
^q3 ^q3 ^hA
另一种方法是在一元输入中标记所有其他
1011011这会将大端二进制表示形式放置在输出部分中（因此在“反向”中）。注意：生成小端表示并不需要太多的努力。
这是该算法的转换表：
| 状态 | 阅读 | 写 | 摇头 | 下一个状态 |
|---|---|---|---|---|
| 开始 | 1 | 0 | 对 | 奇怪 |
| 开始 | 0 | 对 | 开始 | |
| 开始 | _ | 左 | 干净 | |
| 奇怪 | 0 | 对 | 奇怪 | |
| 奇怪 | 1 | 对 | 均匀 | |
| 奇怪 | _ | 对 | 追加1 | |
| 均匀 | 0 | 对 | 均匀 | |
| 均匀 | 1 | 0 | 对 | 奇怪 |
| 均匀 | _ | 对 | 追加0 | |
| 追加0 | 0 或 1 | 对 | 追加0 | |
| 追加0 | _ | 0 | 左 | 中心 |
| 追加1 | 0 或 1 | 对 | 追加1 | |
| 追加1 | _ | 1 | 左 | 中心 |
| 中心 | 0 或 1 | 左 | 中心 | |
| 中心 | _ | 左 | 左 | |
| 左 | 0 或 1 | 左 | 左 | |
| 左 | _ | 对 | 开始 | |
| 干净 | 0 | 1 | 左 | 干净 |
| 干净 | _ | 对 | 停下来 |
以及一个可运行的实现：
createTuring({
transitions: [
{ state: "start", read: "1", write: "0", move: "R", nextState: "odd" },
{ state: "start", read: "0", move: "R", nextState: "start" },
{ state: "start", read: "_", move: "L", nextState: "clean" },
{ state: "odd", read: "0", move: "R", nextState: "odd" },
{ state: "odd", read: "1", move: "R", nextState: "even" },
{ state: "odd", read: "_", move: "R", nextState: "append1" },
{ state: "even", read: "0", move: "R", nextState: "even" },
{ state: "even", read: "1", write: "0", move: "R", nextState: "odd" },
{ state: "even", read: "_", move: "R", nextState: "append0" },
{ state: "append0", read: "01", move: "R", nextState: "append0" },
{ state: "append0", read: "_", write: "0", move: "L", nextState: "center" },
{ state: "append1", read: "01", move: "R", nextState: "append1" },
{ state: "append1", read: "_", write: "1", move: "L", nextState: "center" },
{ state: "center", read: "01", move: "L", nextState: "center" },
{ state: "center", read: "_", move: "L", nextState: "left" },
{ state: "left", read: "01", move: "L", nextState: "left" },
{ state: "left", read: "_", move: "R", nextState: "start" },
{ state: "clean", read: "0", write: "1", move: "L", nextState: "clean" },
{ state: "clean", read: "_", move: "R", nextState: "halt" },
],
initState: "start",
tape: "11111111111",
});<script src="https://trincot.github.io/turing.js"></script>时间复杂度为 O(𝑛log𝑛)。