单磁带图灵机，用于将二进制数转换为一元

Question

我一直在试图解决的一个问题上，即将没有前导零的二进制数转换为同一磁带上的一元表示形式。

例如 110 -> xxxxxx

我发现马尔可夫算法是一个潜在的解决方案，但无法实现它。将不胜感激一些方向！

编辑：我自己想通了。为二进制减法编写一台机器，然后为每个减法编写一个 x。

Answer 1

1 q0:q1 0 R
1 q1:q1 1 R
0 q1:q1 0 R
  q1:qRev | L
| q1:q1 | R
0 q0:qCon # R
0 qCon:q00 0 R
1 qCon:q00 1 R
| qCon:! | S
0 q00:q00 0 R
1 q00:q00 1 R
| q00:q00 | R
  q00:qMul   L
|* qMul:qMul |* L
| qMul:qMul1 |* R
|* qMul1:qMul1 |* R
  qMul1:qMul |* L
1 qMul:qBea 1 R
0 qMul:qBea 0 R
|* qBea:qBea | R
  qBea:qRev   L
| qRev:qRev | L
1 qRev:qRev 1 L
0 qRev:qRev 0 L
# qRev:q0 # R
  qRev:q0   R