Domanda

Ok ragazzi, l'obiettivo di oggi è quello di costruire un simulatore di macchina di Turing. Per coloro che non sanno cosa sia, vedi l'articolo di Wikipedia . La tabella di stato che stiamo usando oggi si trova alla fine di la definizione formale che fa parte di quella pagina .

Il codice avrà una sequenza di "0" e "1" caratteri della stringa, un numero intero che rappresenta il carattere che la macchina inizia con, e un numero intero che rappresenta lo stato del programma (in ordine sparso), e di uscita risultato finale delle operazioni sulla corda, così come la posizione finale. Esempi:

Esempio 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)

Esempio 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)

Varie:

  • Il codice deve gestire correttamente tentativi di scrivere in "spazi vuoti" sul nastro, estendendo la stringa come necessario.
  • Poiché la macchina stato specificato non specifica alcun tipo di azione "nastro vuoto", il trattamento di tutti i valori vuoti come 0.
  • È necessario contare solo il metodo che gestisce la valutazione di una stringa con stato iniziale, come è uscita che i dati è a voi.
  • Spostamento direttamente sul nastro è Incrementando alto (posizione stringa 0 trova completamente a sinistra), stato 0 è A, stato 1 è B, e lo stato 2 è C.

(si spera) montaggio finale: Offro le mie scuse più sincere per quanto riguarda la confusione e problemi che ho causato con questa domanda: ho letto male la tabella di stato fornito ho elencato, e ottenuto indietro. Spero che mi perdonerete per sprecare il vostro tempo; era del tutto non intenzionale!

È stato utile?

Soluzione

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

Questo è stato divertente da trovare. Due trucchi. Si usa un hash per il nastro, e sai una cosa? Un hash è auto-estensibile, quindi non è necessario più a cuore i confini nastro. L'altro trucco è per la combinazione sia di lettura e scrittura della cella si accede. Basta dovuto cambiare le convenzioni interne 0 e lo spazio significa 0 e qualsiasi altro valore significa 1. Queste due trucchi implica alcuni decodifica banale di uscita, ma io credo che sia ok. Anche io non contato il punto e virgola finale nella mia funzione come gnibbler non ha contato la sua nella sua golfscript.

Se qualcuno è interessato anche io posso pubblicare le mie altri tentativi. Sono un po 'più a lungo, ma usa trucchi divertenti. Uno è basato regex per esempio, e lavora direttamente con nastro come stringa di un altro è una sorta di po-fu.

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

ho contato la funzione unica e ci vuole una stringa, un num stato ed una posizione nell'ordine specificato. La funzione restituisce nuovo stato nastro come un array.

Un'altra variante 106 char 

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

Non è chiaro se questo è barare o meno. Dà risultati corretti e si estende automaticamente nastro (senza limite fissato), ma per evitare il test se è necessario o non prolungare nastro lo fa ogni passo e regolare indice.

Un'altra variante 98 char

Questo è anche l'unione, ma in un modo diverso. E basta usare globali per passare parametri all'interno della funzione. Quindi si impostano le variabili di fuori della funzione invece che all'interno. rimuovendo così 14 caratteri dal corpo della funzione. 

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

Altri suggerimenti

Python - 133 caratteri

battere perl per un po 'almeno:) 

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 caratteri 

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

casi di test 

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

C - 282 44 98 caratteri (Comprese tutte le var e tabella dichiarazioni di anello interno) 

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

C # - 157 caratteri 

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

Il metodo prende un List<int> come nastro, in modo che possa essere espanso finché memoria permette.

Asserzione: 

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

Se barare e allocare una matrice di grandi dimensioni abbastanza dall'inizio, 107 caratteri : 

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

Perl 142 char (senza contare la lettura di argomenti su linea di comando e stampa finale. Ebbene, la maggior parte del codice è il programma di castoro, il motore stesso è soltanto 46 char.

Ho cambiato il formato di input per mettere Stato presso la sua posizione nella stringa. Non mi sento in colpa a tutti, altrimenti la maggior parte del codice sarebbe stata la gestione delle frontiere quando la testa era fuori di corda. Anche in questo confine stringa della versione gestione dei costi di 17 caratteri ... Il trucco è solo per ricordare che si può esprimere le macchine di Turing come catene di Markov ... quello che ho fatto con le regex. 

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

Nota: come un dato di fatto che questo non è ancora veramente giocato a golf, ma solo un ingenuo primo tentativo. Potrei tornare con qualcosa di reale breve.

Golfscript - 102 caratteri 

{: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 caratteri 

{: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 caratteri
lettura intero programma da 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

esempi 

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

Per chiarire, questo programma simula il Busy Beaver Turing Macchina esattamente come descritto nell'articolo wikipedia, non l'OP (OP ha R e L acceso)

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

Perl, 97 (96 infatti, a causa finale ";" è facoltativo per sottotassello) 

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$`);

L'idea: $ _ Variabile contiene 0 e 1 se non sotto la testa. Sotto la testa, 0 In uno stato dà 2, 1 in uno stato dà 3, 0 in B Stato dà 4, 1 B Stato dà 5, 0 in C Stato dà 6, 1 in stato di C dà 7.

modo seguente il primo esempio "1010" (pos 3, Stato A) dà "1051" quindi "1411", "1131", "1117" (1111, stato C, pos 3) e stop (inclusa posizionare il nastro a destra)

Lua:

versione semi-golfed: 

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)

versione compattata un peso di 441 caratteri: 

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)

Far passare gli argomenti in forma di nastro, puntatore all'istruzione, dello stato, come il seguente: 

turing.lua 1010 3 0

F # - 275 caratteri

Ok, quindi sicuramente non il più breve, ma di apprendimento. Se qualcuno può aiutare su come ottenere lo String.mapi di utilizzare una function piuttosto che la fun match with sarei grato, continuo a ricevere 'Il modello discriminatore x non è definito'. Qualcuno sa di un sito che descrive le regole di utilizzare la parola chiave function in un lambda? 

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)

Uso 

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

Qui è una versione ampliata per migliorare la leggibilità: 

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)

Sto anche cercando di pensare a un modo migliore per gestire la manipolazione della stringa, qualcosa di diverso poi il String.mapi. Commenti e suggerimenti costruttivi (per favore) di benvenuto e incoraggiato.

Ruby, 129

(quando trattino rimosso) 

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
Non affiliato a StackOverflow
scroll top