图灵机代码高尔夫

Question

好了大家，今天的目标是构建一个图灵机模拟器。对于那些不知道它是什么的人，请参阅维基百科文章。我们今天使用的状态表位于作为该页面一部分的正式定义< /a>.

该代码将采用“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)

Answer 2

C - 282 44 98 个字符
（包括所有内循环变量和表声明）

#include<stdio.h>
#include<string.h>

char*S="  A2C1C2  C3A2A0";
f(char*p,char c){char*e;while(c){e=S+*p*8+c*2;*p=1;p+=*e++-66;c=*e-48;}}

char T[1000];
main()
{
  char *p;
        char c;
        char *e;

    int initial;
    scanf("%s %d %c",&T[500],&initial,&c);
    c = c - '0' + 1;

    for(p=&T[500]; *p; p++)
        *p -= '0';

    p = &T[500+initial];

    f(p, c);

    char *left = T;
    while((left < T+500)&&(!*left))
        left++;

    char *right = T+sizeof(T)-1;
    while((right > T+500)&&(!*right))
        right--;

    initial = p - left;

    for(p=left; p<=right; p++)
        *p+='0';

    printf("%.*s %d\n\n",right-left+1,left,initial);
}

Answer 3

Perl function 101 char

sub f{($_,$S,$p)=@_;for(%h=map{$i++,$_}split//;7^$S;$p-=$S<=>3){$S=7&236053>>3*($S%4*2+!!$h{$p}++)}};

f(@ARGV);
@allpos = sort keys %h;
for (@allpos){
    print $h{$_}?1:0;
}
print " H ".($p-$allpos[0])."\n";

找到这个很有趣。两个技巧。它对磁带使用哈希值，你知道吗？哈希是可自动扩展的，因此无需再关心磁带边界。另一个技巧是将所访问的单元格的读取和写入结合起来。只需更改内部约定 0，空格表示 0，任何其他值表示 1。这两个技巧意味着对输出进行一些简单的解码，但我相信这是可以的。我也没有计算我的函数中的最后一个分号，因为 gnibbler 没有计算他的高尔夫球脚本中的分号。

如果有人感兴趣我也可以发布我的其他尝试。它们有点长，但使用了有趣的技巧。例如，一个是基于正则表达式的，直接使用磁带作为字符串，另一个是一种 bit-fu。

Perl function 112 char

sub f{($_,$S,$p)=@_;for(split//;7^$S;@_=($p=0,@_)if($p-=$S<=>3)<0){$S=7&236053>>3*($S%4*2+$_[$p]);$_[$p]=1}@_};

@res = f@ARGV;
print @res," H $p\n";

我只计算了该函数，它按照指定的顺序接受一个字符串、一个状态编号和一个位置。该函数以数组形式返回新的磁带状态。

另一个变体106个字符

sub f{($_,$S,$p)=@_;for(split//;7^$S;$p-=$S<=>3){$S=7&236053>>($S%4*6+$_[$p]*3);$_[$p++]=1;@_=(0,@_)}@_};`

@res = f(@ARGV);
print @res," H $p\n";

目前还不清楚这个变体是否作弊。它给出正确的结果并自动延长磁带（无固定限制），但为了避免测试是否有必要延长磁带，它会在每一步中执行此操作并调整索引。

另一个变体 98 字符

这个也在合并中，但方式不同。它只是使用全局变量在函数内部传递参数。因此，您可以在函数外部而不是内部设置变量。因此从函数体中删除了 14 个字符。

sub f{for(split//;7^$S;@_=($p=0,@_)if($p-=$S<=>3)<0){$S=7&236053>>3*($S%4*2+$_[$p]);$_[$p]=1}@_};

($_,$S,$p) = @ARGV;
@res = f();
print @res," H $p\n";

Answer 4

C# - 157 个字符

void T(List<int>t,ref int p,int s){while(s!=3){if(p<0)t.Insert(0,p=0);if(p==t.Count)t.Add(0);var c=t[p]==1;t[p]=1;p+=s==0==c?1:-1;s=s==1==c?1:c?s==0?2:3:0;}}

该方法采用 List 作为磁带，因此只要内存允许，就可以对其进行扩展。

断言：

List<int> tape;
int pos;

tape = "1010".Select(c => c - '0').ToList();
pos = 3;
T(tape, ref pos, 0);
Debug.Assert(String.Concat(tape.Select(n => n.ToString()).ToArray()) == "1111" && pos == 2);

tape = "110100".Select(c => c - '0').ToList();
pos = 3;
T(tape, ref pos, 1);
Debug.Assert(String.Concat(tape.Select(n => n.ToString()).ToArray()) == "11111111" && pos == 1);

如果我们作弊并从一开始就分配一个足够大的数组，107 个字符：

void X(int[]t,ref int p,int s){while(s!=3){var c=t[p]==1;t[p]=1;p+=s==0==c?1:-1;s=s==1==c?1:c?s==0?2:3:0;}}

Answer 5

Perl 142 个字符（不包括在命令行和最终打印上读取参数。好吧，大部分代码是 Beaver 程序，引擎本身只有 46 个字符。

我更改了输入格式以将状态放在字符串中的位置。我不知道根本不用感到内疚，否则当 head 脱离字符串时，大多数代码将进行边界管理，即使在这个版本中，字符串边界管理也需要 17 个字符......诀窍是记住您可以将图灵机表示为马尔可夫。链...我用正则表达式做了什么。

perl -e '$b=shift;%p=qw(A0|A$ 1B ^A1|0A1 C01 1A1 C11 0B0|^B0 A01 1B0|1B$ A11 B1 1B 0C0|^C0 B01 1C0|1C$ B11 C1 1H);while($b!~/H/){$b=~s/$_/$p{$_}/for keys%p}print"$b\n"' 00A1011

111H1111

注意：事实上，这还不是真正的高尔夫，而只是一个天真的第一次尝试。我可能会带着一些很短的东西回来。

Answer 6

Golfscript - 102 个字符

{:s;{\:$;:^0<{0.:^$+:$}{^$}if.,@>!'0'*+.^=1&s.++:c;.^<1+\^)>+:$[^(^).^(^)^(]c=:^3"120113"c=3&:s-}do}:f

;
["1010" 3 0 f]p
["110100" 3 1 f]p
["1000000" 3 1 f]p

106 个字符

{:s;\:$;:i{0<{0.:i$+:$}{i$}if.,@>!'0'*+.i=1&s.++:c;.i<1+\i)>+:$;[i(i).i(i)i(]c=:i 3"120113"c=3&:s-}do$\}:f

113 个字符
读取

' '/(:$;(~:i;~~:s;{0i>{0.:i$+:$}{i$}if.,@>!'0'*+.i=1&s.++:c;.i<1+\i)>+:$;[i(i).i(i)i(]c=:i;3"120113"c=3&:s-}do
Golfscript - 102 个字符
{:s;{\:$;:^0<{0.:^$+:$}{^$}if.,@>!'0'*+.^=1&s.++:c;.^<1+\^)>+:$[^(^).^(^)^(]c=:^3"120113"c=3&:s-}do}:f

;
["1010" 3 0 f]p
["110100" 3 1 f]p
["1000000" 3 1 f]p

106 个字符
{:s;\:$;:i{0<{0.:i$+:$}{i$}if.,@>!'0'*+.i=1&s.++:c;.i<1+\i)>+:$;[i(i).i(i)i(]c=:i 3"120113"c=3&:s-}do$\}:f

 113 个字符

 读取
i

整个程序从 stdin示例

$ echo -n 1010 3 0 |../golfscript.rb turing.gs 
"1111"2
$ echo -n 110100 3 1 |../golfscript.rb turing.gs 
"11111111"1

Answer 7

澄清一下，这个程序完全按照维基百科文章中的描述模拟 Busy Beaver 图灵机，而不是 OP（OP 已切换 R 和 L）

Python 255 char

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

Answer 8

Perl，97（确实是 96，因为最后的“;”对于子块是可选的）

sub f{($_,$a,pos)=@_;s/\G./
amp;+2*$a+2/e;1while s!(.?)(2|5)|(3|4|6)(.?)!$2?4+$1.1:8+$4+$3+5*/3/!e}
f@ARGV;
#output
s/7/1/;print;print " H ",(-1+length
Perl，97（确实是 96，因为最后的“;”对于子块是可选的）
);

想法：
$_ 变量包含 0 和 1，除了头部下方。
头下，
A 状态下的 0 给出 2，
A 状态下的 1 给出 3，
B 状态下的 0 给出 4，
B 状态下的 1 给出 5，
C 状态下的 0 给出 6，
C 状态下的 1 给出 7。

因此，按照第一个示例，“1010”（位置 3，状态 A）给出“1051”，然后“1411”、“1131”、“1117”（1111，状态 C，位置 3）并停止（加上将磁带移至右侧）

Answer 9

Lua：

半高尔夫版本：

a=arg
t=a[1]
i=a[2]+1
s=a[3]+0
r=string.rep
b=string.sub;z="0";o="1";while true do if i<1 then
        t=z..t
        i=1
    elseif i>#t then
        t=t..z
    end
    c=b(t,i,i)
    if i>0 then
        t=b(t,0,i-1)..o..b(t,i+1,#t)
    else
        t="1"..b(t,i+1,#t)
    end
    if s==0 then
        if c==z then
            i=i-1
            s=1
        elseif c==o then
            i=i+1
            s=2
        end
    elseif s==1 then
        if c==z then
            i=i+1
            s=0
        elseif c==o then
            i=i-1
        end
    elseif s==2 then
        if c==z then
            i=i+1
            s=1
        elseif c==o then
            i=i-1
            break
        end
    end
end
print(t,i-1)

压缩版本有441个字符：

a=arg t=a[1] i=a[2]+1 s=a[3]+0 r=string.rep b=string.sub;z="0";o="1";while true do if i<1 then t=z..t i=1 elseif i>#t then t=t..z end c=b(t,i,i) if i>0 then t=b(t,0,i-1)..o..b(t,i+1,#t) else t="1"..b(t,i+1,#t) end if s==0 then if c==z then i=i-1 s=1 elseif c==o then i=i+1 s=2 end elseif s==1 then if c==z then i=i+1 s=0 elseif c==o then i=i-1 end elseif s==2 then if c==z then i=i+1 s=1 elseif c==o then i=i-1 break end end end print(t,i-1)

以磁带、指令指针、状态的形式传递参数，如下所示：

turing.lua 1010 3 0

Answer 10

Lua，232

现在使用表查找。

j={{-1,1},{1,-1},{1,-1}}u={{1,2},{-1,0},{-1,1}}t,i,s=...i=i+1
s=s+1 z="0"o="1"while s<4 do if i<1 then t=z..t i=1
elseif i>#t then t=t..z end c=t:sub(i,i):byte()-47
t=t:sub(0,i-1)..o..t:sub(i+1)i=i+j[s][c]s=s+u[s][c]end print(t,i-1)

这只是 RCIX 的答案 重新打高尔夫球，332 个字符。

t,i,s=...i=i+1 s=s+0 r=string.rep b=string.sub z="0"o="1"while s<3 do if i<1 then
t=z..t i=1 elseif i>#t then t=t..z end c=b(t,i,i)t=b(t,0,i-1)..o..b(t,i+1,#t)if
s<1 then i=i+(c==o and 1 or -1)s=c==z and 1 or 2 elseif s<2 then i=i+(c==o and
-1 or 1)s=c==z and 0 or s else i=i+(c==o and -1 or 1)s=c==z and 1 or 3 end end
print(t,i-1)

• 使用 ... 运算符分配输入参数
• 使用 and 和 or 代替 if 语句，当更短
• 替换一些 < code>elseif 仅使用 else 假设有效的输入/状态
• 删除了括号、椭圆运算符和结束引号后的空格

Answer 11

F# - 275 个字符

好吧，所以绝对不是最短的，但学习。如果有人可以帮助让 String.mapi 使用函数，而不是有趣的匹配，我将不胜感激，我不断收到“模式鉴别器 x 未定义” '。有人知道有一个网站详细介绍了在 lambda 中使用 function 关键字的规则吗？

let rec t s i p=
    match s with
    |3->(p,i)
    |_->let g=[[(1,1);(-1,2)];[(-1,0);(1,1)];[(-1,1);(1,3)]]
        let p=match i with|_ when i<0 ->"0"+p|_ when i=p.Length->p+"0"|_->p
        let i=max 0 i
        let m,n=g.Item(s).Item((int p.[i])-48)
        String.mapi(fun x c->match x with|_ when x=i->'1'|_->c) p |> t n (i+m)

用法

t 1 2 "101011" |> printfn "%A"

这里是一个扩展版本，以提高可读性：

let rec tur state index tape =
    printfn "Index %d: State %d: Tape %s:" index state tape
    match state with
    |3 -> (tape, index)
    |_ -> let prog = [[(1,1);(-1,2)];[(-1,0);(1,1)];[(-1,1);(1,3)]]
          let tape = match index with |_ when index<0 ->"0"+tape |_ when index=tape.Length->tape+"0" |_->tape
          let index = max 0 index
          let move,newstate = prog.Item(state).Item((int tape.[index])-48)
          String.mapi (fun i c -> match i with |_ when i=index->'1' |_->c) tape
          |> tur newstate (index+move)

我还试图想出一种更好的方法来处理字符串的操作，而不是 String.mapi。欢迎并鼓励意见和建议（请有建设性的）。

Answer 12

Ruby，129

（删除缩进后）

def pr t,z,s      # DEBUG
  p [t,s]     # DEBUG
  p [' '*z + '^'] # DEBUG
end       # DEBUG


def q t,z,s
  s*=2
  (t=t.ljust z+1
    (t=' '+t;z=0)if z<0
    a=t[z]&1
    t[z]=?1
    b=s>0?1-a: a
    s="240226"[s|a]&7
    z+=b*2-1)while s!=6
  [t,z]
end

p q "1010",3,0
p q "110100",3,1