Symulator maszyny Turinga

15

Napisać symulator maszyny Turinga .

Dla uproszczenia możemy przyjąć statusy jako liczby całkowite, symbole jako char, pusty symbol równa się spacji

5 krotek w postaci aktualnego stanu, symbolu wejściowego, następnego stanu, symbolu wyjściowego, kierunku (w lewo lub w prawo) kolejność nie jest obowiązkowa, ale określ, czy chcesz ją zamienić

Maszyna musi zatrzymać się po osiągnięciu nieznanego stanu, niedozwolone są żadne inne warunki zatrzymania.

Taśma jest nieskończona w obu kierunkach i zawsze możesz odczytać pusty znak.

Dane wejściowe: taśma początkowa, stan początkowy i program. możesz czytać dane z dowolnego miejsca w wybranym przez siebie formacie

Wyjście: taśma po wykonaniu programu

Wymagane: przykładowy program działający na symulatorze

To jest kod-colf, więc wygrywa najkrótszy kod.

W ciągu kilku godzin opublikuję implementację i kilka przykładowych programów.

code-golf interpreter Marco Martinelli
źródło
4
O kompletności Turinga w programie PowerPoint (SIGBOVIK)
sergiol

Odpowiedzi:

2

GolfScript, 92 znaki

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

Maszyna Turinga w GolfScript stała się znacznie dłuższa niż zamierzona. Wciąż bawię się różnymi przedstawieniami taśmy.

Pierwszy wiersz wejścia to stan pierwotny, drugi wiersz początkowa taśma, a następnie tablica przejść (z bieżącym stanem zamówienia, symbolem wejściowym, następnym stanem, kierunkiem, symbolem wyjściowym).

Przykład ( dostępny również online )

> 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
źródło
pokonałeś moją implementację sed o jeden znak, czas sprawdzić, czy dam radę lepiej
Geoff Reedy
7

GNU sed z -r- 133 117 111 93 znakami

Tak, sed jest już gotowy. GNU sed i -r(rozszerzone wyrażenia regularne) służą tylko do zapisania kilku znaków, to tylko niewielka zmiana w pracy z POSIX sed.

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

Format wejściowy to 

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

Separatory @, #i charakter głowa >nie może być używany jako symbol na taśmie. Etykiety państwowe nie mogą zawierać @ >lub #.

Uruchomi wszystkie programy na wejściu, po jednym w wierszu

Przykłady:

Marco to n b n programu

Wejście

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

Wynik

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

Cześć Marco! program

Wejście

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

Wynik

6@Hello!> #0@ 1@Hr#1@ 2@er#2@ 3@lr#3@ 4@lr#4@ 5@or#5@ 6@!r
Geoff Reedy
źródło
7

Trochę się spóźniłem, ale pomyślałem, że zostawię to tutaj ...

Maszyna Turinga Symulacja maszyny Turinga: 370 bajtów?

Tutaj używam struktury Turinga zastosowanej w jego artykule z 1936 roku. Używam jednego symbolu = jeden bajt, w tym m-config i operacji.

╔═══════════════╦═══════╦═══════════════════╦═══════════════╗
║    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           ║
╚═══════════════╩═══════╩═══════════════════╩═══════════════╝

Oto jeden z przykładów Turinga z powyższego artykułu na moją maszynę:

['<', 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]

Wypróbuj online! (Używa Pythona 3 jako interpretera) - Edycja: Właśnie sprawdziłem TIO i wydaje się, że tak naprawdę nie działa poprawnie ... Wypróbuj go na komputerze lokalnym i (mam nadzieję) powinien działać. To działa na moją.

zginać
źródło
Żadna szkoda zamierzona, po prostu wyrównanie granic na stole.
Greg Bacon
@GregBacon Bez obrazy ... być może istnieje różnica między tym, jak różne komputery wyświetlają blokady kodu, ale twoja edycja znacznie pogorszyła wyrównanie na moim ekranie edycji ... Jestem pewien, że wyglądało dobrze, kiedy zasugerowałeś edycję; nie jestem pewien, na czym polega problem
bendl
3

APL (110)

(To nie jest nawet takie krótkie ...)

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⋄,/⊃⌽⍺}⎕

Czyta z klawiatury dwa wiersze: pierwszy to program, a drugi to początkowa taśma.

Format to

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

i wszyscy powinni być na tej samej linii. „Ruch” to 0, aby przejść w prawo i 1, aby przejść w lewo.

Przykładowy program (wstawione linie podziału dla zachowania przejrzystości, powinny znajdować się w jednym wierszu).

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

Program dodaje razem dwie liczby jednoargumentowe, na przykład:

in:  1111 111
out: 1111111

Przykład 2 (dostosowany z programu przyrostowego binarnego z wpisu 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
źródło
Jak mogę tego spróbować? Korzystam z Linuksa i wypróbowałem z aplus, ale to nie działa (niezdefiniowany token :(). Który interpreter / kompilator powinienem wypróbować?
Marco Martinelli,
Używam APL Dyalog. Nie jestem świadomy korzystania z funkcji specyficznych dla Dyalogu, ale A + to nie to samo. Istnieje darmowa wersja Dyalog, ale jest tylko dla systemu Windows. (Może działać pod Wine, ale używa własnej metody wprowadzania, więc możesz wpisać APL.) Jeśli uruchomisz Dyalog, po prostu wpisz / wklej kod APL (w jednym wierszu), a następnie program maszyny Turinga (w drugim wierszu ), a następnie początkowa taśma (w trzecim wierszu).
marinus
ok, spróbuję tego, dziękuję
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 i p są wejściami, b jest początkową taśmą, p koduje reguły jako (ciąg reprezentujący) dykta z krotki (w stanie, na taśmie) do krotki (w stanie, ruchu głowy, poza taśmą) krotki . Jeśli ruch wynosi 0, program kończy się, 1 to ruch w prawo, a -1 to ruch w lewo.

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')}"""

Ten przykładowy program sprawdza, czy ostatnia litera łańcucha (przed pustą taśmą) to „a”, jeśli tak, zapisuje „Y” na końcu łańcucha (pierwsza pusta spacja).

Edycja 1:

Zmieniono taśmę, aby była reprezentowana jako dyktando, ponieważ wydawało się to najkrótszym sposobem na napisanie rozszerzalnej struktury danych. Przedostatni wiersz w większości przekształca go z powrotem w czytelną formę na wyjście.

Edycja 2:

Dzięki Strigoides za wiele ulepszeń.

Edycja 3:

Zrobiłem to niepotrzebnie, więc 0, ponieważ wyjście opuszczałoby to miejsce. Usunąłem to, ponieważ zawsze możemy zapisać dane wyjściowe tak samo jak dane wejściowe.

shiona
źródło
Nie sądzę, że jest to prawidłowe rozwiązanie, ponieważ w twojej implementacji taśma jest ograniczona. W ten sposób musisz wiedzieć z góry zużycie pamięci twojego programu. I są problemy z poruszaniem się w lewo. Wskazówka: taśmę można wykonać z dwóch zmodyfikowanych stosów, w których zawsze można wyciąć pusty symbol.
Marco Martinelli
Ach, prawda. Przepraszam, nie pomyślałem tak daleko.
shiona
Uhm .. afaik taśma jest nieskończona w obu kierunkach i zawsze możesz odczytać pusty znak. Sprecyzuję to w odpowiedzi.
Marco Martinelli,
Miałeś rację (w naszych ćwiczeniach mieliśmy bardziej surowe zasady). Naprawiłem przynajmniej niektóre wady.
shiona
Możesz usunąć spację w pierwszym wierszu, r=0;s=0możesz stać się r=s=0(a średnik na końcu tego wiersza nie jest potrzebny), możesz usunąć funkcję w, ponieważ nie jest używana, można usunąć nawiasy (s,m,t)=r[s,c], skrócić blok try/ exceptusing dict.get; c=a.get(i,' '), ponieważ mma wartość 0 lub 1, możesz użyć if m-1:i możesz skrócić map()połączenie, przekształcając je w funkcję czytania listy.
Strigoides
3

Postscriptum (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

Prawdopodobnie jest to oszustwo, ale tabela przejścia zawiera kod do wykonywania przejść. Ponieważ taśma jest reprezentowana przez odwzorowanie liczb całkowitych na liczby całkowite, przedstawiłem stany jako odwzorowanie nazw na słowniki, więc taśma i program współistnieją w tym samym anonimowym słowniku.

Dodatkowe oszczędności dzięki możliwości wykonywania wszystkich nazw stanów, dzięki czemu są one automatycznie ładowane.

Niegolfowany z wbudowanym programem „Hello”. Dodatkowe 52 znaki kupują pętlę do odczytu taśmy ze standardowego wejścia.Uruchom z 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

Tak więc format tabeli to 

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

gdzie in-statejest nazwą, in-tapei out-tapesą znakami (tj. liczbami całkowitymi lub wyrażeniami, które dają liczby całkowite), movementjest -1dla lewej lub 1prawej i out-statejest nazwą wykonywalną . Wiele in-tapeprzejść dla tego samego stanu należy połączyć jak powyżej.

luser droog
źródło
Kolejny problem polega na tym, że nie ma możliwości odkrycia, która część taśmy jest interesująca. To będzie kosztować sporo currentdict{search-for-min-and-max}forall juggle-params-for-for. :(
luser droog
Próbowałem własnych, ale było znacznie poza twoją zwięzłością. Ale zasugerowałem kilka ulepszeń w kodzie.
Thomas W.
BTW, a co z początkową taśmą? Usunąłem skomentowany wiersz z kodu bez golfa, ponieważ wydaje się, że nie spełnia swojej roli. („Nie 0” zwraca -1, dlatego nie ma iteracji pętli)
Thomas W.
Doskonałe ulepszenia! ... Jeśli chodzi o początkowy kod taśmy, to chyba pomyliłem go z mojego notatnika. SB 0 1 0 not{(%stdin)(r)file read not{exit}if def}for. Nie jestem pewien, dlaczego myślałem, że mogę uciec od pominięcia tego w wersji golfowej. : P
luser droog
Och, czekaj, -1! To 0 notpowinno być 16#7fffffff. Przepraszam. Aha! dlatego zostało to skomentowane! Wyszedł prosto z notebooka, nie został przetestowany, i skasowałem wszystkie komentarze, nie patrząc, kiedy grałem w golfa. Nie mów facetowi Pythonowi! : P
luser droog
2

C (jeszcze nie grał w golfa)

Chyba nie mogę z tym wygrać, ale fajnie było go uruchomić. Jest to tym bardziej prawdziwe, że teraz to naprawdę robi pracę. :)

Tyle że jest nieskończony tylko w jednym kierunku. Przypuszczam, że potrzebuje też taśmy negatywnej. Westchnienie....

Negatywne nie było takie złe. Przeplatamy obie strony jako wyrównania i szanse. Komplikacja polega teraz na tym, że musi wyświetlać taśmę w kolejności sekwencyjnej , ponieważ sam plik jest teraz pomieszany. Myślę, że to uzasadniona zmiana. Turing się uprościł w ten sposób.

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

A oto przebieg próbny:

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

Program wysyła taśmę w kolejności sekwencyjnej, ale plik przedstawia przeplecione strony negatywne i pozytywne.

luser droog
źródło
Występują problemy z twoją implementacją. Wypróbuj ten program, który zamienia aib0 'a' 0 'b' R; 0 'b' 0 'a' R z wejściem aaa, wyjściem jest bab zamiast bbb. I są problemy z poruszaniem się w lewo.
Marco Martinelli
Dziękuję za uwagę! Aktualizacja naprawia oba, jak sądzę (mam nadzieję).
luser droog
uhm .. wciąż dostaje babę
Marco Martinelli
tak, ale tym razem jest poprawne! „aaa” odpowiada pozycjom [0, -1,1] na taśmie. Ale wyniki, które powinny to wyraźnie pokazać, wymagają pracy.
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()}

Sformatowane dla czytelności

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 jest funkcją, która ustawia taśmę e jest funkcją, która ocenia program

Przykład 1 - Wydrukuj „Hello!” na taśmie :)

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)

Przykład 2 - Pozostaw literę T na taśmie, jeśli początkowy ciąg znaków ma postać n b n , w przeciwnym razie zatrzymaj się.

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)

Przykład 3 - Przyrost liczby binarnej

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)

w przykładach 1 oznacza ruch w prawo, a -1 oznacza ruch w lewo

Marco Martinelli
źródło