Turing Machine Simulator

15

Schreiben Sie einen Turing-Maschinensimulator .

Der Einfachheit halber können wir Status als Ganzzahl, Symbole als Zeichen und leere Symbole als Leerzeichen annehmen

5-Tupel in Form von aktuellem Status, Eingabesymbol, nächster Status, Ausgabesymbol, Richtung (links oder rechts) Die Reihenfolge ist nicht obligatorisch, aber geben Sie an, ob Sie sie tauschen

Die Maschine muss anhalten, wenn ein unbekannter Zustand erreicht ist. Eine andere Anhaltebedingung ist nicht zulässig.

Das Band ist in beide Richtungen unendlich und Sie können immer ein leeres Zeichen lesen.

Eingabe: das Anfangsband, ein Anfangszustand und ein Programm. Sie können die Daten in dem von Ihnen gewünschten Format von jedem beliebigen Ort aus lesen

Ausgabe: das Band nach der Ausführung des Programms

Erforderlich: Ein Beispielprogramm, das auf Ihrem Simulator ausgeführt wird

Dies ist ein Code-Colf, so dass der kürzeste Code gewinnt.

Ich werde in den nächsten Stunden eine Implementierung und einige Beispielprogramme veröffentlichen.

code-golf interpreter Marco Martinelli
quelle
4
Zur Vollständigkeit von PowerPoint (SIGBOVIK)
Sergiol

Antworten:

2

GolfScript, 92 Zeichen

~:m;n\+{:^.n?)>1<]m{2<1$=},.{~2>~^n/~1>[@\+]n*1$%n/~\1$1<+[\1>.!{;" "}*]n*\%@}{;;^0}if}do n-

Die Turing-Maschine in GolfScript wurde viel länger als beabsichtigt. Ich spiele immer noch mit verschiedenen Darstellungen des Bandes herum.

Die erste Zeile der Eingabe ist der ursprüngliche Zustand, die zweite Zeile das ursprüngliche Band, gefolgt von einer Reihe von Übergängen (mit dem aktuellen Ordnungszustand, dem Eingabesymbol, dem nächsten Zustand, der Richtung, dem Ausgabesymbol).

Beispiel (auch online verfügbar )

> 0
> '101'
> [[0 '0' 0 1 '0']
>  [0 '1' 0 1 '1']
>  [0 ' ' 1 -1 ' ']
>  [1 '0' 2 1 '1']
>  [1 '1' 3 -1 '0']
>  [3 '0' 2 1 '1']
>  [3 ' ' 2 1 '1']
>  [3 '1' 3 -1 '0']] 

110
Howard
quelle
Du hast meine sed-Implementierung um einen Charakter geschlagen, um zu sehen, ob ich es besser machen kann
Geoff Reedy,
7

GNU sed mit -r- 133 117 111 93 Zeichen

Ja, sed ist fertig. GNU sed und -r(erweiterte reguläre Ausdrücke) dienen nur zum Speichern weniger Zeichen. Die Arbeit mit POSIX sed ist nur eine kleine Änderung.

:s
s/^(.*@)(.*)>(.)(.*#\1\3([^@]*@)(..))/\5\2\6>\4/
T
s/(..)l>|r>/>\1/
s/>@/@> /
s/>#/> #/
bs

Eingabeformat ist 

[initial state]@[non-empty tape with > marking head position]#[state]@[input symbol][next state]@[output symbol][direction l or r]#...

Die Trennzeichen @, #und Kopfzeichen >können nicht als ein Symbol auf dem Band verwendet werden. Zustandsbezeichnungen dürfen nicht @ >oder enthalten #.

Es werden alle Programme in der Eingabe ausgeführt, eines pro Zeile

Beispiele:

Marco ist ein n b n Programm

Eingang

0@>aaabbb#0@a1@ r#0@ 4@ r#1@a1@ar#1@b1@br#1@ 2@ l#2@b3@ l#2@a5@al#3@b3@bl#3@a3@al#3@ 0@ r#4@ 5@Tr

Ausgabe

5@    T>  #0@a1@ r#0@ 4@ r#1@a1@ar#1@b1@br#1@ 2@ l#2@b3@ l#2@a5@al#3@b3@bl#3@a3@al#3@ 0@ r#4@ 5@Tr

Marco ist Hallo! Programm

Eingang

0@> #0@ 1@Hr#1@ 2@er#2@ 3@lr#3@ 4@lr#4@ 5@or#5@ 6@!r

Ausgabe

6@Hello!> #0@ 1@Hr#1@ 2@er#2@ 3@lr#3@ 4@lr#4@ 5@or#5@ 6@!r
Geoff Reedy
quelle
7

Ich bin also etwas spät dran, dachte aber, ich lasse das hier ...

Turingmaschine Eine Turingmaschine simulieren: 370 Bytes?

Hier verwende ich die Struktur, die Turing in seiner Arbeit von 1936 verwendet hat. Ich verwende ein Symbol = ein Byte, einschließlich M-Configs und Operationen.

╔═══════════════╦═══════╦═══════════════════╦═══════════════╗
║    m-config    ║ Symbol ║     Operations      ║ Final m-config ║
╠═══════════════╬═══════╬═══════════════════╬═══════════════╣
║ currentCommand ║ Any    ║ L                   ║ currentCommand ║
║                ║ *      ║ MR                  ║ readCommand    ║
╠----------------╬--------╬---------------------╬----------------╣
║ nextCommand    ║ Any    ║ L                   ║ nextCommand    ║
║                ║ *      ║ E  R  R  R  P* R    ║ readCommand    ║
╠----------------╬--------╬---------------------╬----------------╣
║ readCommand    ║ P      ║ R                   ║ readCommandP   ║
║                ║ M      ║ R                   ║ readCommandM   ║
║                ║ G      ║ R                   ║ readCommandG   ║
║                ║ E      ║ R                   ║ MHPNone        ║
╠----------------╬--------╬---------------------╬----------------╣
║ readCommandP   ║ 0      ║                     ║ MHP0           ║
║                ║ 1      ║                     ║ MHP1           ║
║                ║ e      ║                     ║ MHPe           ║
║                ║ x      ║                     ║ MHPx           ║
║                ║ None   ║                     ║ MHPNone        ║
╠----------------╬--------╬---------------------╬----------------╣
║ readCommandM   ║ R      ║                     ║ MHMR           ║
║                ║ L      ║                     ║ MHML           ║
╠----------------╬--------╬---------------------╬----------------╣
║ readCommandG   ║ 1      ║                     ║ G2<1           ║
║                ║ 2      ║                     ║ G2<2           ║
║                ║ 3      ║                     ║ G2<3           ║
║                ║ 4      ║                     ║ G2<4           ║
║                ║ 5      ║                     ║ G2<5           ║
╠----------------╬--------╬---------------------╬----------------╣
║ G2<1           ║ int(1) ║ L  P@ R  R  R  P* R ║ GTS            ║
║                ║ <      ║                     ║ G21            ║
║                ║ *      ║ E  L                ║ G2<1           ║
║                ║ @      ║ E  L                ║ G2<1           ║
║                ║ Any    ║ L                   ║ G2<1           ║
╠----------------╬--------╬---------------------╬----------------╣
║ G2<2           ║ int(2) ║ L  P@ R  R  R  P* R ║ GTS            ║
║                ║ <      ║                     ║ G22            ║
║                ║ *      ║ E  L                ║ G2<2           ║
║                ║ @      ║ E  L                ║ G2<2           ║
║                ║ Any    ║ L                   ║ G2<2           ║
╠----------------╬--------╬---------------------╬----------------╣
║ G2<3           ║ int(3) ║ L  P@ R  R  R  P* R ║ GTS            ║
║                ║ <      ║                     ║ G23            ║
║                ║ *      ║ E  L                ║ G2<3           ║
║                ║ @      ║ E  L                ║ G2<3           ║
║                ║ Any    ║ L                   ║ G2<3           ║
╠----------------╬--------╬---------------------╬----------------╣
║ G2<4           ║ int(4) ║ L  P@ R  R  R  P* R ║ GTS            ║
║                ║ <      ║                     ║ G24            ║
║                ║ *      ║ E  L                ║ G2<4           ║
║                ║ @      ║ E  L                ║ G2<4           ║
║                ║ Any    ║ L                   ║ G2<4           ║
╠----------------╬--------╬---------------------╬----------------╣
║ G2<5           ║ int(5) ║ L  P@ R  R  R  P* R ║ GTS            ║
║                ║ <      ║                     ║ G25            ║
║                ║ *      ║ E  L                ║ G2<5           ║
║                ║ @      ║ E  L                ║ G2<5           ║
║                ║ Any    ║ L                   ║ G2<5           ║
╠----------------╬--------╬---------------------╬----------------╣
║ G21            ║ int(1) ║ L  P@ R             ║ GTS            ║
║                ║ Any    ║ R                   ║ G21            ║
╠----------------╬--------╬---------------------╬----------------╣
║ G22            ║ int(2) ║ L  P@ R             ║ GTS            ║
║                ║ Any    ║ R                   ║ G22            ║
╠----------------╬--------╬---------------------╬----------------╣
║ G23            ║ int(3) ║ L  P@ R             ║ GTS            ║
║                ║ Any    ║ R                   ║ G23            ║
╠----------------╬--------╬---------------------╬----------------╣
║ G24            ║ int(4) ║ L  P@ R             ║ GTS            ║
║                ║ Any    ║ R                   ║ G24            ║
╠----------------╬--------╬---------------------╬----------------╣
║ G25            ║ int(5) ║ L  P@ R             ║ GTS            ║
║                ║ Any    ║ R                   ║ G25            ║
╠----------------╬--------╬---------------------╬----------------╣
║ GTS            ║ ^      ║ R                   ║ TS             ║
║                ║ Any    ║ R                   ║ GTS            ║
╠----------------╬--------╬---------------------╬----------------╣
║ TS             ║ 0      ║                     ║ RL0            ║
║                ║ 1      ║                     ║ RL1            ║
║                ║ e      ║                     ║ RLe            ║
║                ║ x      ║                     ║ RLx            ║
║                ║ None   ║                     ║ RLNone         ║
╠----------------╬--------╬---------------------╬----------------╣
║ RL0            ║ @      ║ R  R                ║ GTS0           ║
║                ║ Any    ║ L                   ║ RL0            ║
╠----------------╬--------╬---------------------╬----------------╣
║ RL1            ║ @      ║ R  R                ║ GTS1           ║
║                ║ Any    ║ L                   ║ RL1            ║
╠----------------╬--------╬---------------------╬----------------╣
║ RLe            ║ @      ║ R  R                ║ GTSe           ║
║                ║ Any    ║ L                   ║ RLe            ║
╠----------------╬--------╬---------------------╬----------------╣
║ RLx            ║ @      ║ R  R                ║ GTSx           ║
║                ║ Any    ║ L                   ║ RLx            ║
╠----------------╬--------╬---------------------╬----------------╣
║ RLNone         ║ @      ║ R  R                ║ GTSNone        ║
║                ║ Any    ║ L                   ║ RLNone         ║
╠----------------╬--------╬---------------------╬----------------╣
║ GTS0           ║ 0      ║ R  P*  R            ║ readCommand    ║
║                ║ Any    ║ R                   ║ GTS0           ║
╠----------------╬--------╬---------------------╬----------------╣
║ GTS1           ║ 1      ║ R  P*  R            ║ readCommand    ║
║                ║ Any    ║ R                   ║ GTS1           ║
╠----------------╬--------╬---------------------╬----------------╣
║ GTSe           ║ e      ║ R  P*  R            ║ readCommand    ║
║                ║ Any    ║ R                   ║ GTSe           ║
╠----------------╬--------╬---------------------╬----------------╣
║ GTSx           ║ x      ║ R  P*  R            ║ readCommand    ║
║                ║ Any    ║ R                   ║ GTSx           ║
╠----------------╬--------╬---------------------╬----------------╣
║ GTSNone        ║ _      ║ R  P*  R            ║ readCommand    ║
║                ║ Any    ║ R                   ║ GTSNone        ║
╠----------------╬--------╬---------------------╬----------------╣
║ MHP0           ║ ^      ║ R                   ║ Print0         ║
║                ║ Any    ║ R                   ║ MHP0           ║
╠----------------╬--------╬---------------------╬----------------╣
║ MHP1           ║ ^      ║ R                   ║ Print1         ║
║                ║ Any    ║ R                   ║ MHP1           ║
╠----------------╬--------╬---------------------╬----------------╣
║ MHPe           ║ ^      ║ R                   ║ Printe         ║
║                ║ Any    ║ R                   ║ MHPe           ║
╠----------------╬--------╬---------------------╬----------------╣
║ MHPx           ║ ^      ║ R                   ║ Printx         ║
║                ║ Any    ║ R                   ║ MHPx           ║
╠----------------╬--------╬---------------------╬----------------╣
║ MHPNone        ║ ^      ║ R                   ║ PrintNone      ║
║                ║ Any    ║ R                   ║ MHPNone        ║
╠----------------╬--------╬---------------------╬----------------╣
║ MHMR           ║ ^      ║ R  R                ║ MHR            ║
║                ║ Any    ║ R                   ║ MHMR           ║
╠----------------╬--------╬---------------------╬----------------╣
║ MHML           ║ ^      ║ L                   ║ MHL            ║
║                ║ Any    ║ R                   ║ MHML           ║
╠----------------╬--------╬---------------------╬----------------╣
║ Print0         ║ ^      ║ R                   ║ Print0         ║
║                ║ None   ║ P0                  ║ nextCommand    ║
║                ║ Any    ║ E                   ║ Print0         ║
╠----------------╬--------╬---------------------╬----------------╣
║ Print1         ║ ^      ║ R                   ║ Print1         ║
║                ║ None   ║ P1                  ║ nextCommand    ║
║                ║ Any    ║ E                   ║ Print1         ║
╠----------------╬--------╬---------------------╬----------------╣
║ Printx         ║ ^      ║ R                   ║ Printx         ║
║                ║ None   ║ Px                  ║ nextCommand    ║
║                ║ Any    ║ E                   ║ Printx         ║
╠----------------╬--------╬---------------------╬----------------╣
║ Printe         ║ ^      ║ R                   ║ Printe         ║
║                ║ None   ║ Pe                  ║ nextCommand    ║
║                ║ Any    ║ E                   ║ Printe         ║
╠----------------╬--------╬---------------------╬----------------╣
║ PrintNone      ║ ^      ║ R                   ║ PrintNone      ║
║                ║ None   ║                     ║ nextCommand    ║
║                ║ Any    ║ E                   ║ PrintNone      ║
╠----------------╬--------╬---------------------╬----------------╣
║ MHL            ║ ^      ║ R  R                ║ MHL            ║
║                ║ [      ║                     ║ SBL            ║
║                ║ Any    ║ L  P^ R  R  E       ║ nextCommand    ║
╠----------------╬--------╬---------------------╬----------------╣
║ MHR            ║ ^      ║ R  R                ║ MHR            ║
║                ║ ]      ║                     ║ SBR            ║
║                ║ None   ║ P^ L  L  E          ║ nextCommand    ║
╠----------------╬--------╬---------------------╬----------------╣
║ SBR            ║ ]      ║ E  R  R  P]         ║ currentCommand ║
╠----------------╬--------╬---------------------╬----------------╣
║ SBL            ║ ]      ║ R                   ║ SBLE           ║
║                ║ Any    ║ R                   ║ SBL            ║
╠----------------╬--------╬---------------------╬----------------╣
║ SBLE           ║ [      ║                     ║ currentCommand ║
║                ║ None   ║ L                   ║ SBLE           ║
║                ║ Any    ║ E  R  R  P] L       ║ SBLE           ║
╚═══════════════╩═══════╩═══════════════════╩═══════════════╝

Hier ist eines von Turings Beispielen aus dem obigen Papier für meine Maschine:

['<', None, 1, '0', None, 'P', 'e', None, 'M', 'R', None, 'P', 'e', None, 'M', 'R', None, 'P', '0', None, 'M', 'R', None, 'M', 'R', None, 'P', '0', None, 'M', 'L', None, 'M', 'L', None, 'G', '2',
                      '1', None, 'P', 'e', None, 'M', 'R', None, 'P', 'e', None, 'M', 'R', None, 'P', '0', None, 'M', 'R', None, 'M', 'R', None, 'P', '0', None, 'M', 'L', None, 'M', 'L', None, 'G', '2',
                      'e', None, 'P', 'e', None, 'M', 'R', None, 'P', 'e', None, 'M', 'R', None, 'P', '0', None, 'M', 'R', None, 'M', 'R', None, 'P', '0', None, 'M', 'L', None, 'M', 'L', None, 'G', '2',
                      'x', None, 'P', 'e', None, 'M', 'R', None, 'P', 'e', None, 'M', 'R', None, 'P', '0', None, 'M', 'R', None, 'M', 'R', None, 'P', '0', None, 'M', 'L', None, 'M', 'L', None, 'G', '2',
                      '_', None, 'P', 'e', None, 'M', 'R', None, 'P', 'e', None, 'M', 'R', None, 'P', '0', None, 'M', 'R', None, 'M', 'R', None, 'P', '0', None, 'M', 'L', None, 'M', 'L', None, 'G', '2',

             None, 2, '1', None, 'M', 'R', None, 'P', 'x', None, 'M', 'L', None, 'M', 'L', None, 'M', 'L', None, 'G', '2',
                      '0', None, 'G', '3',

             None, 3, '0', None, 'M', 'R', None, 'M', 'R', None, 'G', '3',
                      '1', None, 'M', 'R', None, 'M', 'R', None, 'G', '3',
                      '_', None, 'P', '1', None, 'M', 'L', None, 'G', '4',

             None, 4, 'x', None, 'E', 'E', None, 'M', 'R', None, 'G', '3',
                      'e', None, 'M', 'R', None, 'G', '5',
                      '_', None, 'M', 'L', None, 'M', 'L', None, 'G', '4',

             None, 5, '0', None, 'M', 'R', None, 'M', 'R', None, 'G', '5',
                      '1', None, 'M', 'R', None, 'M', 'R', None, 'G', '5',
                      'e', None, 'M', 'R', None, 'M', 'R', None, 'G', '5',
                      'x', None, 'M', 'R', None, 'M', 'R', None, 'G', '5',
                      '_', None, 'P', '0', None, 'M', 'L', None, 'M', 'L', None, 'G', '2',
        None, '[', '^', None, ']', None]

Probieren Sie es online! (Verwendet Python 3 als Interpreter) --Bearbeiten: Ich habe gerade das TIO überprüft und es scheint nicht richtig zu funktionieren ... Probieren Sie es auf Ihrem lokalen Computer aus und es sollte (hoffentlich) funktionieren. Das tut es bei mir.

bendl
quelle
Kein Schaden beabsichtigt, nur die Ränder auf dem Tisch ausrichten.
Greg Bacon
@GregBacon Keine Beleidigung ... vielleicht gibt es einen Unterschied, wie verschiedene Computer Codeblöcke rendern, aber Ihre Bearbeitung hat die Ausrichtung auf meinem Bearbeitungsbildschirm erheblich verschlechtert ... Ich bin sicher, es hat gut ausgesehen, als Sie die Bearbeitung vorgeschlagen haben. nicht sicher, was das Problem ist
Bendl
3

APL (110)

(Es ist nicht einmal so kurz ...)

0(''⍞){×⍴X←0~⍨⍺∘{x y S T s m t←⍺,⍵⋄S T≡x,⊃⊃⌽y:s,⊂(⊃y){m:(¯1↓⍺)(⍵,⍨¯1↑⍺)⋄(⍺,⊃⍵)(1↓⍵)}t,1↓⊃⌽y⋄0}¨⍵:⍵∇⍨⊃X⋄,/⊃⌽⍺}⎕

Es liest zwei Zeilen von der Tastatur: die erste ist das Programm und die zweite ist das Anfangsband.

Das Format ist

(in-state in-tape out-state movement out-tape)

und sie sollten alle auf der gleichen Linie sein. 'Bewegung' ist 0, um sich nach rechts und 1, um sich nach links zu bewegen.

Beispielprogramm (Aus Gründen der Übersichtlichkeit sollten Zeilenumbrüche in einer Zeile stehen.)

(0 ' ' 1 0 '1')
(0 '1' 0 0 '1')
(1 '1' 1 0 '1')
(1 ' ' 2 1 ' ')
(2 '1' 3 1 ' ')

Das Programm addiert zwei unäre Zahlen, zum Beispiel:

in:  1111 111
out: 1111111

Beispiel 2 (angepasst aus dem binären Inkrementierungsprogramm von Marco Martinelli):

(0 '0' 0 0 '0')
(0 '1' 0 0 '1')
(0 ' ' 1 1 ' ')
(1 '0' 2 0 '1')
(1 '1' 3 1 '0')
(3 '0' 2 0 '1')
(3 ' ' 2 0 '1')
(3 '1' 3 1 '0')
Marinus
quelle
Wie kann ich es versuchen? Ich benutze Linux und habe es mit aplus versucht, aber es funktioniert nicht (undefined token :(). Welchen Interpreter / Compiler sollte ich versuchen?
Marco Martinelli
Ich benutze Dyalog APL. Ich bin mir nicht bewusst, dass ich Dyalog-spezifische Funktionen verwende, aber A + ist nicht ganz dasselbe. Es gibt eine kostenlose Version von Dyalog, aber nur für Windows. (Es kann unter Wine ausgeführt werden, verwendet jedoch eine eigene Eingabemethode, sodass Sie APL eingeben können.) Wenn Dyalog ausgeführt wird, geben Sie einfach den APL-Code (in einer Zeile) und anschließend das Turing-Maschinenprogramm (in einer zweiten Zeile) ein ), dann das erste Band (in der dritten Zeile).
Marinus
ok, ich werde das versuchen, danke
Marco Martinelli
3

Python, 101 189 152 142

a=dict(zip(range(len(b)),b))
r=eval(p)
i=s=0
while 1:
 c=a.get(i,' ')
 s,m,a[i]=r[s,c]
 if 0==m:exit([x[1]for x in sorted(a.items())])
 i=i+m

b und p sind die Eingaben, b ist das Anfangsband, p codiert die Regeln als (Zeichenfolgendarstellung von) einem Diktat von (In-State-, In-Tape-) Tupel zu (Out-State-, Head-Move-, Out-Tape-) Tupel . Wenn move 0 ist, wird das Programm beendet, 1 wird nach rechts verschoben und -1 wird nach links verschoben.

b="aaba"

p="""{(0, 'a'): (1, 1, 'a'),
      (0, 'b'): (0, 1, 'b'),
      (1, 'a'): (1, 1, 'a'),
      (1, 'b'): (0, 1, 'b'),
      (1, ' '): (1, 0, 'Y'),
      (0, ' '): (0, 0, 'N')}"""

In diesem Beispielprogramm wird geprüft, ob der letzte Buchstabe der Zeichenfolge (vor dem leeren Band) "a" ist. In diesem Fall wird "Y" am Ende der Zeichenfolge (erstes Leerzeichen) geschrieben.

Bearbeiten 1:

Das Band wurde geändert, um als Diktat dargestellt zu werden, da dies der kürzeste Weg zu sein schien, eine erweiterbare Datenstruktur zu schreiben. Die vorletzte Zeile wandelt sie zumeist wieder in lesbare Form für die Ausgabe um.

Bearbeiten 2:

Vielen Dank an Strigoides für viele Verbesserungen.

Edit 3:

Ich hatte es unnötigerweise auf 0 gesetzt, da die Ausgabe den Ort so belassen würde, wie er ist. Ich habe dies entfernt, da wir immer die gleiche Ausgabe wie die Eingabe schreiben können.

Shiona
quelle
Ich denke nicht, dass dies eine gültige Lösung ist, da in Ihrer Implementierung das Band begrenzt ist. Auf diese Weise müssen Sie den Speicherverbrauch Ihres Programms im Voraus kennen. Und es gibt Probleme, sich nach links zu bewegen. Tipp: Ein Band kann aus zwei modifizierten Stapeln erstellt werden, in denen Sie immer ein leeres Symbol platzieren können.
Marco Martinelli
Ah, stimmt. Entschuldigung, habe das nicht zu weit gedacht.
Shiona
Ähm ... afaik das Band ist unendlich in beide Richtungen und Sie können immer ein leeres Zeichen lesen. Ich werde das in der Antwort spezifizieren.
Marco Martinelli
Sie hatten Recht (wir hatten strengere Regeln in unseren Übungen). Ich habe zumindest einige der Mängel behoben.
Shiona
Sie können das Leerzeichen in der ersten Zeile entfernen, r=0;s=0werden r=s=0(und das Semikolon am Ende dieser Zeile ist unnötig), Sie können die Funktion entfernen w, da es nicht verwendet wird, die Klammern können entfernt werden (s,m,t)=r[s,c], der try/ exceptBlock kann gekürzt werden mit dict.get; c=a.get(i,' '), da mentweder 0 oder 1 ist, können Sie verwenden if m-1:, und Sie können Ihren map()Anruf verkürzen , indem Sie ihn in ein Listenverständnis umwandeln.
Strigoides
3

Nachsatz (205) (156) (150) (135)

<<
>>begin
/${stopped}def([){add dup{load}${exit}if}def
0 A{1 index{load}${pop( )}if
get{exec}${exit}if}loop
3{-1[pop}loop{1[print}loop

Dies ist wahrscheinlich ein Betrug, aber die Übergangstabelle enthält Code zum Ausführen der Übergänge. Und da das Band durch eine Zuordnung von Ganzzahlen zu Ganzzahlen dargestellt wird, habe ich Zustände als Zuordnung von Namen zu Wörterbüchern dargestellt, sodass das Band und das Programm im gleichen anonymen Wörterbuch existieren.

Zusätzliche Einsparungen, indem alle Statusnamen ausführbar gemacht werden und automatisch geladen werden.

Ungolfed mit eingebettetem "Hallo" -Programm. Weitere 52 Zeichen kaufen eine Schleife, um das Band von stdin zu lesen.Laufen Sie mit gsnd -q tm.ps.

%!
<<
    /A<<( ){dup(H)def 1 add B}>>
    /B<<( ){dup(e)def 1 add C}>>
    /C<<( ){dup(l)def 1 add D}>>
    /D<<( ){dup(l)def 1 add E}>>
    /E<<( ){dup(o)def 1 add F}>>
>>begin %ds: int-keys=tape name-keys=prog
0 A %pos state
{ %loop
    1 index{load}stopped{pop( )}if  %pos state tape(pos)
    get    {exec}stopped{exit  }if  %new-pos new-state
} loop
% Loop from tape position 0 to left until left tape end is found
0{                                  %pos
  -1 add                            %new-pos
  dup{load}stopped{exit}if          %new-pos tape(new-pos)
  pop                               %new-pos tape(new-pos)
}loop
% Move to the right and print all chars until right end is hit
{                                   %pos
  1 add                             %new-pos
  dup{load}stopped{exit}if          %new-pos tape(new-pos)
  print                             %new-pos tape(new-pos)
}loop

Das Tabellenformat ist also 

/in-state<<in-tape{dup out-tape def movement add out-state}
           in-tape2{dup out-tape2 def movement2 add out-state2}>>

wo in-stateist ein Name, in-tapeund out-tapesind Zeichen (dh. ganze Zahlen oder Ausdrücke , die Ausbeute ganze Zahlen sind ), movementist -1für die nach links oder 1nach rechts, und out-stateist ein ausführbarer Datei - Name. Mehrfachübergänge in-tapefür denselben Zustand müssen wie oben kombiniert werden.

Luser Droog
quelle
Ein weiteres Problem ist, dass es keine Vorkehrungen gibt, um herauszufinden, welcher Teil des Bandes interessant ist. Das wird einiges kosten currentdict{search-for-min-and-max}forall juggle-params-for-for. :(
luser droog
Versuchte meine eigene, war aber weit über Ihre Prägnanz. Aber ich schlug einige Verbesserungen an Ihrem Code vor.
Thomas W.
Übrigens, was ist mit dem ersten Band? Ich habe die auskommentierte Zeile aus dem Code ohne Golf entfernt, weil sie anscheinend nicht funktioniert hat. ("0 nicht" gibt -1 zurück, daher keine Iteration der Schleife)
Thomas W.
Hervorragende Verbesserungen! ... Über den anfänglichen Bandcode, ich glaube, ich habe ihn von meinem Notizbuch aus falsch geschrieben. SB 0 1 0 not{(%stdin)(r)file read not{exit}if def}for. Ich bin mir nicht sicher, warum ich dachte, ich könnte davonkommen, wenn ich das in der Golfversion weglasse. : P
luser droog
Oh, warte, -1! Dann 0 notsollte es sein 16#7fffffff. Es tut uns leid. Aha! deshalb wurde es kommentiert! Es kam direkt aus dem Notebook, wurde nicht getestet und ich habe alle Kommentare abgeschnitten, ohne nachzuschauen, wenn ich Golf gespielt habe. Erzähl es nicht dem Python-Typ! : P
luser droog
2

C (noch nicht golfen)

Ich schätze, ich kann damit nicht gewinnen, aber es hat Spaß gemacht, es zum Laufen zu bringen. Dies gilt umso mehr, als es nun wirklich funktioniert . :)

Außer es ist nur unendlich in eine Richtung. Ich nehme an, es braucht auch ein Negativband. Seufzer....

Negativ war nicht so schlimm. Wir verschachteln die beiden Seiten als Ausgleich und Chance. Die Komplikation besteht nun darin, dass das Band in sequenzieller Reihenfolge angezeigt werden muss , da die Datei selbst nun durcheinander gebracht wird. Das ist eine legitime Änderung, denke ich. Sich auf diese Weise zu vereinfachen.

#include<stdio.h>
int main(int c, char**v){
    int min=0,max=0;
    int pos=0,qi;sscanf(v[1],"%d",&qi);
    FILE*tab=fopen(v[2],"r");
    FILE*tape=fopen(v[3],"r+");
    setbuf(tape,NULL);
    do {
        min = pos<min? pos: min;
        max = pos>max? pos: max;
        fseek(tape,(long)(abs(pos)*2)-(pos<0),SEEK_SET);
        int c = fgetc(tape), qt=qi-1,qr;
        fseek(tape,(long)(abs(pos)*2)-(pos<0),SEEK_SET);
        char x = c==EOF?' ':c, xt=x-1,xr,d[2];
        if (x == '\n') x = ' ';
printf("%d '%c' %d (%d)\n", qi, x, pos, (int)ftell(tape));
        while((qt!=qi)||(xt!=x)){
            fscanf(tab, "%d '%c' %d '%c' %1[LRN]", &qt, &xt, &qr, &xr, d);
            if (feof(tab)){
                goto HALT;
            }
printf("%d '%c' %d '%c' %s\n", qt, xt, qr, xr, d);
        }
        qi=qr;
        rewind(tab);
        fputc(xr,tape);
        pos+=*d=='L'?-1:*d=='R'?1:0;
    } while(1);
HALT:
printf("[%d .. %d]:\n", min, max);
    for (pos = min; pos <= max; pos++){
        fseek(tape,(long)(abs(pos)*2)-(pos<0),SEEK_SET);
        //printf("%d ",pos);
        putchar(fgetc(tape));
        //puts("");
    }
    return qi;
}

Und hier ist der Testlauf:

522(1)04:33 AM:~ 0> cat bab.tm
0 'a' 0 'b' R
0 'b' 0 'a' R
523(1)04:33 AM:~ 0> echo aaaaa > blank; make tm ; tm 0 bab.tm blank; echo; cat blank
make: `tm' is up to date.
0 'a' 0 (0)
0 'a' 0 'b' R
0 'a' 1 (2)
0 'a' 0 'b' R
0 'a' 2 (4)
0 'a' 0 'b' R
0 ' ' 3 (6)
0 'a' 0 'b' R
0 'b' 0 'a' R
[0 .. 3]:
bbbÿ
babab

Das Programm gibt das Band in sequenzieller Reihenfolge aus, aber die Datei repräsentiert die verschachtelten negativen und positiven Seiten.

Luser Droog
quelle
Es gibt Probleme mit Ihrer Implementierung. Versuchen Sie dieses Programm, das a und b 0 'a' 0 'b' R; 0 'b' 0 'a' Rmit Eingabe aaa vertauscht. Die Ausgabe ist bab statt bbb. Und es gibt Probleme, sich nach links zu bewegen.
Marco Martinelli
Danke für ihre Aufmerksamkeit! Update behebt beides, denke ich (hoffe).
Luser Droog
ähm .. immer noch bab
Marco Martinelli
Ja, aber diesmal ist es richtig! 'aaa' entspricht den Positionen [0, -1,1] auf dem Band. Die Ausgabe, die dies zeigen soll, muss jedoch noch bearbeitet werden.
Luser Droog
1

Groovy 234 228 154 153 149 139 124

n=[:];i=0;t={it.each{n[i++]=it};i=0};e={p,s->a=p[s,n[i]?:' '];if(a){n[i]=a[1];i+=a[2];e(p,a[0])}else n.sort()*.value.join()}

Zur besseren Lesbarkeit formatiert

n=[:];
i=0;
t={it.each{n[i++]=it};i=0};
e={p,s->
    a=p[s,n[i]?:' '];
    if(a){
        n[i]=a[1];
        i+=a[2];
        e(p,a[0])
    }else n.sort()*.value.join()
}

t ist die Funktion, mit der das Band eingelegt wird. e ist die Funktion, mit der das Programm ausgewertet wird

Beispiel 1 - "Hallo!" auf dem Band :)

t('')
e([[0,' ']:[1,'H',1],
   [1,' ']:[2,'e',1],
   [2,' ']:[3,'l',1],
   [3,' ']:[4,'l',1],
   [4,' ']:[5,'o',1],
   [5,' ']:[6,'!',1]],0)

Beispiel 2 - Lassen Sie ein T auf dem Band, wenn die anfängliche Zeichenfolge die Form a n b n hat. Andernfalls beenden Sie den Vorgang.

t('aaabbb')
e([[0,'a']:[1,' ',1],
   [0,' ']:[4,' ',1],
   [1,'a']:[1,'a',1],
   [1,'b']:[1,'b',1],
   [1,' ']:[2,' ',-1],
   [2,'b']:[3,' ',-1],
   [2,'a']:[5,'a',-1],
   [3,'b']:[3,'b',-1],
   [3,'a']:[3,'a',-1],
   [3,' ']:[0,' ',1],
   [4,' ']:[5,'T',1]],0)

Beispiel 3 - Inkrementieren einer Binärzahl

t('101')
e([[0,'0']:[0,'0',1],
   [0,'1']:[0,'1',1],
   [0,' ']:[1,' ',-1],
   [1,'0']:[2,'1',1],
   [1,'1']:[3,'0',-1],
   [3,'0']:[2,'1',1],
   [3,' ']:[2,'1',1],
   [3,'1']:[3,'0',-1]],0)

in den Beispielen bedeutet 1 nach rechts und -1 nach links

Marco Martinelli
quelle