interpreter - 图灵机 Code Golf

Question

已锁定。这个问题及其答案是 locked因为这个问题是题外话，但却具有历史意义。目前不接受新的答案或互动。

好了大家，今天的目标是构建一个图灵机模拟器。对于那些不知道它是什么的人，请参阅 the Wikipedia article 。我们今天使用的状态表位于 the Formal Definition that's part of that page 的末尾。 .

该代码将采用“0”和“1”字符串字符的序列、表示机器启动字符的整数以及表示程序状态的整数(无特定顺序)，并输出字符串操作的最终结果以及最终位置。示例:

示例1:

1010 state A(0)
   ^ (3)
1011 state B(1)
  ^ (2)
1011 state B(1)
 ^ (1)
1111 state A(0)
  ^ (2)
1111 state C(0)
   ^ (3)
1111 HALT
  ^ (2)

示例2:

110100 state B(1)
   ^ (3)
110100 state B(1)
  ^ (2)
111100 state A(0)
   ^ (3)
111100 state C(2)
    ^ (4)
111110 state B(1)
     ^ (5)
1111110 state A(0)
      ^ (6, tape has been extended to right)
1111111 state B(1)
     ^ (5)
1111111 state B(1)
    ^ (4)
1111111 state B(1)
   ^ (3)
1111111 state B(1)
  ^ (2)
1111111 state B(1)
 ^ (1)
1111111 state B(1)
^ (0)
01111111 state B(1)
^ (0, tape has been extended to left)
11111111 state A(0)
 ^ (1)
11111111 state C(2)
  ^ (2)
11111111 HALT
 ^ (1)

其他:

• 您的代码必须通过根据需要扩展字符串来正确处理写入磁带上“空格”的尝试。
• 由于指定的状态机未指定任何类型的“空白磁带”操作，因此将所有空白值视为 0。
• 您必须仅计算处理具有初始状态的字符串的计算的方法，如何输出该数据取决于您。
• 在磁带上向右移动是向上递增(字符串位置 0 一直在左侧)，状态 0 为 A，状态 1 为 B，状态 2 为 C。

(希望)最终编辑:对于我在这个问题上造成的困惑和麻烦，我表示最诚挚的歉意:我误读了我列出的提供的状态表，并将其弄反了。希望您能原谅我浪费了您的时间；这完全是无意的!

Answer 1

Python - 133 个字符

至少要打败 perl 一段时间:)

def f(t,i,s):
 t=map(int,t) 
 while s<3:t=[0]*-i+t+[0][:i>=len(t)];i*=i>0;c,t[i]=s*4+t[i]*2,1;i+=1-(2&2178>>c);s=3&3401>>c
 return t,i

Python - 172 个字符

def f(t,i,s):
 t=map(int,t)
 while s<3:
  t=[0]*-i+t+[0]*(i-len(t)+1);i=max(0,i);c,t[i]=t[i],1;i,s=[[(i-1,1),(i+1,2)],[(i+1,0),(i-1,s)],[(i+1,1),(i-1,3)]][s][c]
 return t,i

测试用例

assert f("1010",3,0) == ([1, 1, 1, 1], 2)
assert f("110100",3,1) == ([1, 1, 1, 1, 1, 1, 1, 1], 1)