interpreter - チューリングマシンコードゴルフ

Question

皆さん、今日の目標はチューリングマシンシミュレータを構築することです。それが何かわからない人は、ウィキペディアの記事を参照してください。現在使用している状態テーブルは、そのページの一部である Formal Definitionの最後にあります。

このコードは、一連の「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 です。

（できれば）最終編集： この質問で混乱とトラブルを引き起こしたことについて、心からお詫び申し上げます。リストした提供された状態テーブルを読み違えて、逆に取得しました。時間を無駄にしてしまったことをお許しください。それは完全に意図的ではありませんでした！

score 10 · Accepted Answer

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)

score 9 · Accepted Answer

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);
}

score 6 · Accepted Answer

Perl関数101文字

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";

これは見つけるのが楽しかったです。2つのトリック。テープにハッシュを使用し、何を知っていますか？ハッシュは自動拡張可能であるため、テープの境界を気にする必要はありません。もう1つのトリックは、アクセスされたセルの読み取りと書き込みの両方を組み合わせることです。内部規則0を変更する必要があり、スペースは0を意味し、その他の値は1を意味します。これらの2つのトリックは、出力の簡単なデコードを意味しますが、問題ないと思います。また、gnibblerが彼のゴルフスクリプトで彼を数えなかったので、私は私の関数の最後のセミコロンを数えませんでした。

誰かが興味を持っているなら、私は他の試みを投稿することもできます。彼らは少し長いですが、楽しいトリックを使用しています。1つは正規表現ベースで、文字列としてテープを直接操作します。もう1つは一種のビットフーです。

Perl関数112文字

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";

score 3 · Accepted Answer

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<int>テープとして使用するため、メモリが許す限り拡張できます。

アサーション:

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;}}

score 3 · Accepted Answer

Perl 142 文字 (コマンドラインでの引数の読み取りと最終出力はカウントされません。ほとんどのコードはビーバープログラムであり、エンジン自体はわずか 46 文字です。

入力形式を変更して、状態を文字列内の位置に配置しました。そうでなければ、頭が文字列から外れると、ほとんどのコードが境界管理になるので、私はまったく罪悪感を感じません。このバージョンでも、文字列の境界管理には 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

注: 実際のところ、これはまだ実際にゴルフを行ったわけではなく、単純な最初の試みにすぎません。私は本当に短い何かで戻ってくるかもしれません。

score 3 · Accepted Answer

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 文字
stdin から読み取るプログラム全体

' '/(:$;(~: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$`i

例

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

score 2 · Accepted Answer

明確にするために、このプログラムは、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

score 2 · Accepted Answer

Perl、97 (サブブロックの最後の「;」はオプションであるため、実際には 96)

sub f{($_,$a,pos)=@_;s/\G./$&+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$`);

アイデア: $_ 変数には、頭の下を除いて 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) が返され、停止します (テープを右に移動します)。

score 1 · Accepted Answer

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

score 1 · Accepted Answer

ルア、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)

これは、332 文字の RCIX の回答を再ゴルフしたものです。

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)

演算子を使用...して入力パラメータを割り当てます
ステートメントが短い場合はステートメントの代わりにandandを使用しますorif
有効な入力/状態を想定elseifするだけで一部を置き換えましたelse
括弧、楕円演算子、終了引用符の後のスペースを削除

score 1 · Accepted Answer

F# - 275 文字

さて、間違いなく最短ではなく学習です。誰かが String.mapi を使用するのを手伝うことができればfunction、fun match with私はそれを感謝します. 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。. コメントや提案 (建設的なお願い) を歓迎し、奨励します。

score 0 · Accepted Answer

ルビー、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