interpreter - hacer - maquina de turing ejemplos

Código de la máquina de Turing Golf (12)

Ok chicos, el objetivo de hoy es construir un simulador de máquina de Turing. Para aquellos que no saben lo que es, vea el artículo de Wikipedia . La tabla de estados que utilizamos hoy se encuentra al final de la definición formal que forma parte de esa página .

El código tomará una secuencia de caracteres de cadena "0" y "1", un entero que representa el carácter con el que comienza la máquina y un entero que representa el estado del programa (sin ningún orden en particular), y generará el resultado final de Las operaciones en la cadena, así como la posición final. Ejemplos:

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

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

Misceláneo

Su código debe manejar adecuadamente los intentos de escribir en "espacios en blanco" en la cinta, extendiendo la cadena según sea necesario.
Dado que la máquina de estado especificada no especifica ningún tipo de acción de "cinta en blanco", trata todos los valores en blanco como 0.
Debe contar solo el método que maneja la evaluación de una cadena con el estado inicial, de qué manera la información que emita depende de usted.
El movimiento hacia la derecha en la cinta está aumentando (la posición de la cadena 0 está totalmente a la izquierda), el estado 0 es A, el estado 1 es B y el estado 2 es C.

(con suerte) edición final: ofrezco mis más sinceras disculpas por la confusión y los problemas que he causado con esta pregunta: he leído mal la tabla de estado provista en la lista, y la obtuve al revés. Espero que me perdones por perder tu tiempo; ¡Fue completamente involuntario!

Golfscript - 102 personajes

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

{: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 personajes
Programa completo de lectura desde 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

ejemplos

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

Python - 133 personajes

Tienes que vencer a perl por un tiempo al menos :)

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 personajes

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

Casos de prueba

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 # - 157 caracteres

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

El método toma una List<int> como cinta, por lo que se puede expandir siempre que la memoria lo permita.

Afirmación:

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

Si hacemos trampa y asignamos una matriz lo suficientemente grande desde el inicio, 107 caracteres :

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

F # - 275 caracteres

Bueno, definitivamente no es el más corto sino el aprendizaje. Si alguien puede ayudar a que String.mapi use una function lugar de la combinación fun match with que agradecería, seguiré obteniendo "El discriminador del patrón x no está definido". ¿Alguien sabe de un sitio que detalla las reglas de uso de la palabra clave de function en un lambda?

Uso

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

Aquí está una versión ampliada para la legibilidad:

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)

También estoy tratando de pensar en una mejor manera de manejar la manipulación de la cadena, algo que no sea el String.mapi . Comentarios y sugerencias (constructivos por favor) bienvenidos y alentados.

Lua, 232

Ahora usando la tabla de búsqueda.

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)

Esta es solo la respuesta de RCIX re-golfed, 332 caracteres.

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)

utiliza ... operador para asignar parámetros de entrada
utiliza yy or lugar de declaraciones if cuando sea más corto
reemplazó algún otro elseif con solo else asumiendo entradas / estados válidos
espacios eliminados después de parens, operador de elipse y citas finales

Ruby, 129

(cuando se elimina la sangría)

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

Para aclarar, este programa simula la máquina Busing Beaver Turing exactamente como se describe en el artículo de wikipedia, no el OP (el OP tiene R y L cambiados)

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 142 caracteres (sin contar los argumentos de lectura en la línea de comando y la impresión final. Bueno, la mayor parte del código es el programa del castor, el motor en sí tiene solo 46 caracteres.

Cambié el formato de entrada para poner el estado en su posición en la cadena. No me siento culpable en absoluto, ya que, de lo contrario, la mayoría del código sería la gestión de fronteras cuando el jefe no tenía cuerda. Incluso en esta versión, la gestión de borde de cadena cuesta 17 caracteres ... El truco es recordar que puede expresar las máquinas como cadenas de Markov ... lo que hice con expresiones regulares.

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: de hecho, esto no es realmente un juego de golf, sino un primer intento ingenuo. Puedo volver con algo muy corto.

Perl, 97 (96 de hecho, porque final ";" es opcional para el subbloque)

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

La idea: $ _ variable contiene 0s y 1s excepto debajo de la cabeza. Debajo de la cabeza, 0 en el estado A da 2, 1 en el estado A da 3, 0 en el estado B da 4, 1 en el estado B da 5, 0 en el estado C da 6, 1 en el estado C da 7.

por lo tanto, después del primer ejemplo "1010" (pos 3, estado A) aparece "1051", luego "1411", "1131", "1117" (1111, estado C, pos 3) y se detiene (más mover la cinta hacia la derecha)

C - ~~282~~ 44 98 caracteres (incluidas todas las declaraciones de tabla y var de bucle 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); }

Función Perl 101 caracteres

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

Este fue divertido de encontrar. Dos trucos Utiliza un hash para la cinta, ¿y sabes qué? Un hash es auto-extensible, por lo que ya no necesita preocuparse por los límites de la cinta. El otro truco es combinar tanto la lectura como la escritura de la celda a la que se accede. Solo tuve que cambiar las convenciones internas 0 y el espacio significa 0 y cualquier otro valor significa 1. Estos dos trucos implican una decodificación trivial de la salida, pero creo que está bien. Tampoco conté el punto y coma final en mi función, ya que gnibbler no contó el suyo en su guión de golf.

Si alguien está interesado también puedo publicar mis otros intentos. Son un poco más largos pero usan trucos divertidos. Uno está basado en expresiones regulares, por ejemplo, y funciona directamente con cinta como una cadena. Otro es un tipo de bit-fu.

Función Perl 112 caracteres

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

Solo conté la función y toma una cadena, un número de estado y una posición en ese orden según lo especificado. La función devuelve el nuevo estado de la cinta como una matriz.

Otra variante de 106 caracteres.

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

No está claro si éste está engañando o no. Da resultados correctos y extiende automáticamente la cinta (sin límite fijo), pero para evitar las pruebas si es necesario o no extender la cinta, lo hace a cada paso y ajusta el índice.

Otra variante de 98 caracteres.

Este también está en la fusión, pero de una manera diferente. Solo usa globales para pasar parámetros dentro de la función. Por lo tanto, establece sus variables fuera de la función en lugar de dentro. Así se eliminan 14 caracteres del cuerpo de la función

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

Lua

Versión 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)

Versión compactada con un peso de 441 caracteres:

Pase los argumentos en forma de cinta, puntero de instrucción, estado, como los siguientes:

turing.lua 1010 3 0