Симулятор машины Тьюринга

15

Напишите симулятор машины Тьюринга .

Для простоты мы можем принять статусы как целое число, символы как символ, пустой символ равен пробелу

5-кортеж в виде текущего состояния, входного символа, следующего состояния, выходного символа, направления (влево или вправо), порядок не обязателен, но укажите, если вы меняете его местами

Машина должна остановиться при достижении неизвестного состояния, никакие другие условия остановки не допускаются.

Лента бесконечна в обоих направлениях, и вы всегда можете прочитать пустой символ.

Вход: начальная лента, исходное состояние и программа. Вы можете читать данные из любого места в формате, который вам нравится

Вывод: лента после выполнения программы

Требуется: пример программы, которая запускается поверх вашего симулятора

Это код-colf, поэтому самый короткий код выиграл.

Я опубликую реализацию и несколько примеров программ в ближайшие несколько часов.

code-golf interpreter Марко Мартинелли
источник
4
О тьюринговой полноте PowerPoint (SIGBOVIK)
sergiol

Ответы:

2

GolfScript, 92 символа

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

Машина Тьюринга в GolfScript стала намного длиннее, чем предполагалось. Все еще играю с различными представлениями ленты.

Первая строка ввода - это исходное состояние, вторая строка - исходная лента, за которой следует массив переходов (с текущим состоянием ордера, символом ввода, следующим состоянием, направлением, символом вывода).

Пример (также доступен онлайн )

> 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
Говард
источник
ты побил мою реализацию sed одним символом, пора посмотреть, смогу ли я добиться большего успеха
Джефф Риди,
7

GNU sed с -r- 133 117 111 93 символов

Да, sed завершается. GNU sed и -r(расширенные регулярные выражения) предназначены только для сохранения нескольких символов, это лишь небольшое изменение для работы с POSIX sed.

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

Формат ввода 

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

Разделители @, #и голова персонажа >не могут быть использованы в качестве символа на ленте. Метки состояния не могут содержать @ >или #.

Он будет запускать все программы на входе, по одной на строку

Примеры:

Марко это п б п программа

вход

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

Выход

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

Привет Марко! программа

вход

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

Выход

6@Hello!> #0@ 1@Hr#1@ 2@er#2@ 3@lr#3@ 4@lr#4@ 5@or#5@ 6@!r
Джефф Риди
источник
7

Так что я немного опоздал, но подумал, что оставлю это здесь ...

Машина Тьюринга, имитирующая машину Тьюринга: 370 байт?

Здесь я использую структуру, которую Тьюринг использовал в своей статье 1936 года. Я использую один символ = один байт, включая m-конфигурации и операции.

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

Вот один из примеров Тьюринга из статьи выше для моей машины:

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

Попробуйте онлайн! (Использует Python 3 в качестве переводчика) - Редактировать: Я только что проверил TIO, и он, кажется, на самом деле не работает правильно ... Попробуйте его на своей локальной машине, и он должен (надеюсь) работать. Это на моем.

Bendl
источник
Никакого вреда не предполагается, просто выравнивая границы на столе.
Грег Бэкон
@GregBacon Без обид ... возможно, есть какая-то разница между тем, как разные компьютеры рендерит кодовые блоки, но ваше редактирование значительно ухудшило выравнивание на моем экране редактирования ... Я уверен, что это выглядело хорошо, когда вы предложили редактирование; не уверен в чем проблема
бендл
3

APL (110)

(Это даже не так коротко ...)

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

Он читает две строки с клавиатуры: первая - это программа, а вторая - начальная лента.

Формат

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

и все они должны быть на одной линии. «Движение» - это 0, чтобы двигаться вправо, и 1, чтобы двигаться влево.

Пример программы (разрывы строк вставлены для ясности, все они должны быть в одной строке.)

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

Программа добавляет два одинарных числа вместе, например:

in:  1111 111
out: 1111111

Пример 2 (адаптировано из программы двоичного приращения из записи Марко Мартинелли):

(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')
Мэринус
источник
Как я могу попробовать это? Я использую Linux и пробовал с Aplus, но он не работает (неопределенный токен :(). Какой интерпретатор / компилятор я должен попробовать?
Марко Мартинелли
Я использую Dyalog APL. Я не знаю об использовании каких-либо специфичных для Dyalog функций, но A + не совсем то же самое. Есть бесплатная версия Dyalog, но она только для Windows. (Он может работать под Wine, но он использует свой собственный метод ввода, поэтому вы можете ввести APL.) Если вы запускаете Dyalog, просто введите / вставьте код APL (в одну строку), затем программу машины Тьюринга (во вторую строку). ), затем начальная лента (на третьей строке).
марин
хорошо, я попробую это, спасибо
Марко Мартинелли
3

Питон, 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 и p - входные данные, b - исходная лента, p кодирует правила как (строковое представление) из набора (в состоянии, в ленте) в кортеж (из состояния, перемещение головки, из ленты) , Если перемещение равно 0, программа завершается, 1 - перемещение вправо, а -1 - перемещение влево.

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

В этом примере программы проверяется, является ли последняя буква строки (перед пустой лентой) «a», в этом случае записывается «Y» в конце строки (первый пустой пробел).

Изменить 1:

Изменил ленту, чтобы она была представлена ​​как диктовка, так как это казалось самым коротким способом написания расширяемой структуры данных. От второй до последней строки в основном преобразуется в читаемую форму для вывода.

Изменить 2:

Спасибо Strigoides за большое количество улучшений.

Изменить 3:

Я излишне сделал это так, что 0, поскольку выходные данные оставили бы место, как это. Я удалил это, так как мы всегда можем записать вывод так же, как ввод.

shiona
источник
Я не думаю, что это правильное решение, потому что в вашей реализации лента ограничена. Таким образом, вам нужно заранее знать потребление памяти вашей программой. И есть проблемы с движением влево. Подсказка: лента может быть сделана из двух модифицированных стопок, в которых вы всегда можете вставить пустой символ.
Марко Мартинелли
Ах, правда. Извините, не думал, что это слишком далеко.
Шион
Хм .. afaik лента бесконечна в обоих направлениях, и вы всегда можете прочитать пустой символ. Я уточню это в ответе.
Марко Мартинелли
Вы были правы (у нас были более строгие правила в наших упражнениях). Я исправил хотя бы некоторые из недостатков.
Шион
Вы можете удалить пробел в первой строке, r=0;s=0стать r=s=0(и точка с запятой в конце этой строки не нужна), вы можете удалить функцию w, так как она не используется, скобки могут быть удалены (s,m,t)=r[s,c], try/ exceptблок может быть сокращен используя dict.get; c=a.get(i,' '), так mкак это 0 или 1, вы можете использовать if m-1:, и вы можете сократить свой map()вызов, преобразовав его в понимание списка.
Стригоидес
3

постскриптум (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

Это, вероятно, обман, но таблица переходов содержит код для выполнения переходов. А так как лента представлена ​​в виде преобразования целых чисел в целые, я представлял состояния в виде отображения имен в словари, поэтому лента и программа сосуществуют в одном анонимном словаре.

Дополнительная экономия за счет выполнения всех имен состояний исполняемыми, поэтому они автоматически загружаются.

Разгружен со встроенной программой "Hello". Дополнительные 52 символа покупают цикл для чтения ленты со стандартного ввода.Беги с 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

Таким образом, формат таблицы 

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

где in-state- имя, in-tapeи out-tapeявляются символами (т. е. целыми числами или выражениями, которые дают целые числа), movement- -1для левого или 1правого и out-stateявляется исполняемым именем. Несколько in-tapeпереходов для одного и того же состояния должны быть объединены, как указано выше.

Люзер Дрог
источник
Другая проблема заключается в том, что нет места для того, чтобы узнать, какая часть ленты интересна. Это будет стоить совсем немного, чтобы сделать currentdict{search-for-min-and-max}forall juggle-params-for-for. :(
luser droog
Попробовал мой, но был далеко за пределами вашей краткости. Но я предложил некоторые улучшения вашего кода.
Томас В.
Кстати, как насчет начальной ленты? Я удалил закомментированную строку из кода, не предназначенного для игры в гольф, потому что он, похоже, не справлялся с работой. («0 not» возвращает -1, следовательно, нет итерации цикла)
Томас В.
Отличные улучшения! ... О первоначальном коде ленты, я думаю, что я набрал его из своей записной книжки. SB 0 1 0 not{(%stdin)(r)file read not{exit}if def}for. Я не уверен, почему я думал, что смогу обойтись без этого в версии для гольфа. : P
luser droog
Ой, подождите, -1! Тогда 0 notдолжно быть 16#7fffffff. Сожалею. Ага! вот почему это было прокомментировано! Он вышел прямо из блокнота, не прошел тестирование, и я обрезал все комментарии, не глядя, когда играл в гольф. Не говори парню Питона! : P
luser droog
2

C (еще не в гольф)

Я полагаю, я не могу победить с этим, все же было весело заставить его работать. Это еще более верно теперь , что это действительно делает работу. :)

За исключением того, что это только бесконечно в одном направлении. Полагаю, для этого тоже нужна отрицательная лента. Вздох....

Негатив не был так плох. Мы чередуем две стороны как четные и нечетные. Сложность теперь заключается в том, что лента должна отображаться в последовательном порядке , так как сам файл теперь перемешан. Я думаю, это законное изменение. Сам Тьюринг упростил этот путь.

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

И вот тест-запуск:

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

Программа выводит ленту в последовательном порядке, но файл представляет чередующиеся отрицательные и положительные стороны.

Люзер Дрог
источник
Есть проблемы с вашей реализацией. Попробуйте эту программу, которая поменяет местами a и b 0 'a' 0 'b' R; 0 'b' 0 'a' Rс вводом aaa, но вместо bbb выводится bab. И есть проблемы с движением влево.
Марко Мартинелли
Спасибо за внимание! Обновление исправляет оба, я думаю (надеюсь).
Люсер Дрог
хм .. все еще рожать
Марко Мартинелли
да, но на этот раз это правильно! «aaa» соответствует позициям [0, -1,1] на ленте. Но вывод, который должен показать это, явно нуждается в работе.
Люсер Дрог
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()}

Отформатирован для удобства чтения

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 это функция, которая устанавливает ленту e это функция, которая оценивает программу

Пример 1 - Распечатать "Hello!" на ленте :)

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)

Пример 2 - Оставьте T на ленте, если начальная строка имеет вид a n b n , иначе остановитесь.

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)

Пример 3 - Увеличение двоичного числа

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)

в примерах 1 означает перемещение вправо, а -1 означает перемещение влево

Марко Мартинелли
источник