6 января 2011 в 01:13

Программирование на машине Поста из песочницы

Недавно на хабре появилось сразу два материала, посвященных языкам из «большой четверки тьюринговых трясин»: про алгоритм Маркова и Brainfuck. Думаю, для полноты картины будет интересно сравнить эти эзотерические системы с еще одним важным алгоритмическим примитивом — машиной Поста, которой я как раз занимаюсь.

Машина Поста (wiki; для простоты оттуда же взят вариант синтаксиса) похожа на всем известную машину Тьюринга, однако обладает интересными особенностями. Она содержит лишь 6 команд, кроме того, в ячейки-биты памяти могут записываться лишь 2 символа (двоичное кодирование информации). «Естественно», никакой дополнительной памяти, не зря же эзотерикой зовется!

Таким образом, при программировании на машине Поста помимо необходимости совладать с оккамовским синтаксисом надо думать о том, как записать на ленте все промежуточные результаты, не потеряв по пути обратную тропинку к остаткам входных данных. Почему «остаткам»? Зачастую ввиду отсутствия дополнительной памяти приходится обрабатывать входные данные итеративно (а иногда и рекурсивно). Надеюсь, вышеизложенное убедительно доказывает, что написание привычных алгоритмов на машине Поста — неплохая разминка для мозгов и весьма увлекательное занятие.


Пример


Рассмотрим одну из кратчайших реализаций умножения двух натуральных чисел. Числа n и m записываются на ленте в единичной системе счисления, разделяются одной пустой ячейкой. Вход/выход алгоритма может быть таким (отмечено начальное положение каретки):
   v
..01110110..   →   ..01111110..
    3 * 2      =        6


Идея алгоритма — краткое сложение. В каждом проходе цикла машина «откусывает» один бит от левого множителя и «копирует» самый правый имеющийся блок (сперва это второй множитель, затем — его последняя копия). Когда левый множитель «закончится», на ленте остается n блоков по m единиц. Их слияние дает искомое число n*m.

Код

 0. !        - команда остановки, выполнение начинается со строки №1
 1. 0        - главный цикл
 2. →
 3. ? 29, 4  - 29:левый множитель закончился
 4. →
 5. ? 6, 4
 6. →
 7. ? 8, 4
 8. ←
 9. ←
10. 0        - копирование правого блока
11. →
12. ? 13, 11
13. →
14. ? 15, 13
15. 1
16. ←
17. ? 18, 16
18. ←
19. ? 20, 18
20. 1
21. ←
22. ? 23, 10 - конец блока копирования
23. ← 
24. ? 25, 23
25. ←
26. ? 27, 23
27. →
28. → 1
29. →        - слияние копий второго множителя
30. 0
31. → 
32. ? 33, 31
33. 1
34. →
35. ? 0, 36  - выход из программы
36. ←
37. ? 29, 36 


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

Это самая короткая известная мне реализация умножения. Однако, потенциально ее можно ужать еще сильнее, если придумать, как экономно объединить процессы создания копий и их слияния в единый массив.

Если вас заинтересовала тема, предлагаю подумать над следующими задачами:
  • Вывод i-го числа Фибоначчи
  • Деление двух натуральных чисел c остатком
  • «Сборщик мусора». На ленте неизвестным образом распределено конечное количество (n) отмеченных ячеек. Необходимо «сгрести» их в одну кучу, т. е. машина должна оставить на ленте только блок в n отметок подряд.


P. S. «Большой четверкой» называю машину Тьюрига, Поста, систему Маркова и Brainfuck — самые изучаемые тьюринговые трясины.
Роман Левентов @leventov
карма
101,0
рейтинг 5,7
Хеш-таблицы, key-value
Самое читаемое Разработка

Комментарии (18)

  • +5
    Если уж сортировать «тьюринговые трясины» по важности, то надо начинать с основных — математических, на которых всё строилось, а потом уж добавлять в список новомодную эзотерику вроде Brainfuck.
    В таком случае это будут:
    • машина Тьюринга (машину Поста знаю, конечно, но популярности она не приобрела);
    • лямбда-исчисление Черча;
    • рекурсивные функции Черча;
    • нормальные алгоритмы Маркова.

    Во «второй эшелон» попадут-таки машина Поста, блок-схема Поста, комбинаторное исчисление Шейнфинкеля, и, если уж добавлять современные «эзотерические языки программирования» в список — Brainfuck со товарищи.

    И, будьте добры, не называйте «тьюринговы трясины» эзотерическими системами. Это сейчас BF и ему подобные — эзотерические языки программирования на фоне современных высокоуровневых, а машина Тьюринга и эквивалентные ей создавались не чувство юмора программиста потешить, а математически понятие вычислимости и алгоритмистики исследовать, это совершенно разные вещи.

    Как-то так.
  • 0
    Да, про лямбда-исчисление забыл.

    «Эзотерическими системами» я назвал только алгоритмы Маркова и Brainfuck ввиду их _современного_ применения. В Тьюринге вообще ничего особо веселого нет.
  • +1
    На 9 состояний короче:

    0:!
    1: 0 // main loop
    2: →
    3:? 2: 4
    4: →
    5: 0 // loop by second multiple
    6: →
    7:? 6: 8
    8: →
    9:? 8: 10
    10: 1
    11: ←
    12:? 11: 13
    13: ←
    14:? 13: 15
    15: 1
    16: →
    17:? 5: 18
    18: ←
    19:? 18: 20
    20: ←
    21:? 22: 25
    22: ←
    23:? 22: 24
    24: → 1
    25: →
    26: → // erase second multiple
    27:? 28: 0
    28: 0 26

    Честно говоря, машина Тьюринга мне кажется логичнее (если используются только те символы, которые есть в условии задачи — т.е. для унарного умножения только 0 и 1). Все-таки, в отличие от машины Поста в ней не 5-7 команд, а одна, хотя и длинная. И там нет разночтений в синтаксисе (типа «возможен ли переход не на следующую команду», «есть ли условный переход с двумя метками, или два отдельных перехода if(0) и if(1)») — эти мелочи могут сильно влиять на то, какой алгоритм кодируется короче.
    • 0
      изящно!
      • 0
        Спасибо )))
  • 0
    Кстати, третью задачу я не понял. Что такое n? Константа, от которой будет зависеть длина программы? Или это число тоже будет записано на ленте?
    • 0
      Не очень удачно сформулировано. Про ленту ничего не известно, про кол-во отметок тоже. Каретка неизвестно где. Естественно, работа должна идти вечно.
      • 0
        Жестоко. С первой попытки получилось 60 состояний, примерно 15 из них — поиск первой отметки, и примерно столько же — борьба с разнообразными начальными условиями :) Основной цикл — 26 состояний.
        • 0
          1. ? 2, 3    
          2. 1       .вместо поиска первой метки
          3. →       .создание опорных меток
          4. ? 5, 3
          5. →
          6. ? 7, 3
          7. 1       
          8. ← 
          9. ? 10, 8
          10. ←
          11. ? 12, 8
          12. 1 20    ..
          13. ←       .цикл слева
          14. ? 15, 16
          15. 1 20
          16. →
          17. ? 16, 18
          18. ←
          19. 1
          20. →
          21. ? 20, 22
          22. →
          23. ? 24, 22
          24. →
          25. ? 24, 26
          26. 0        
          27. →        справа
          28. ? 29, 30
          29. 1 34
          30. ←
          31. ? 30, 32
          32. →
          33. 1
          34. ←
          35. ? 34, 36
          36. ←
          37. ? 38, 36
          38. ←
          39. ? 38, 40
          40. 0 13     ..
          

          с трудом представляю, как за 15 строк можно найти первую отметку.
          • 0
            В программе до конца не разобрался, но уже первые три строчки вызывают подозрение: при переходе к состоянию 3 у нас потерялась информация — поставили мы новую единицу, или нет.
            Кстати, в команде "? a, b" в каком порядке идут состояния? Вики предлагает сначала состояние для заполненной ячейки, потом для пустой.
            Проверил свою программу — у меня ошибка. Неправильно отрабатывается найденная первая метка. Так что размер был бы еще больше (на 8 состояний). Если бы можно было оставить блок не из n, а из n+1 единицы, все было бы гораздо проще.
            Интересно, считать ли корректым решением то, в котором блок из n единиц возникает только в некоторых точках программы, и при этом постепенно уползает в бесконечность.

            Задачка попроще: на ленте записано число n (каретка стоит на правой его ячейке), а справа от него записано n чисел, разделенных неизвестным числом пробелов. Требуется найти их сумму.

            • 0
              n в итоге будет или n+1 меток — не так уж важно, суть в сборе меток. Так
              1. ? 2, 3    
              2. 1       .вместо поиска первой метки
              

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

              ? j, k
              if 0: j; else: k
              • 0
                У меня с поиском получилось 52 (если нигде не ошибся)

                1: → // ищем пустое место
                2:? 3, 1 // (пусть через запятую будет if(0) 3; else 1, а через двоеточие — наоборот :) )
                3: 1 // первая оборная метка
                4: → // ищем два нуля подряд
                5:? 6, 4
                6: →
                7:? 8, 4
                // здесь могла бы быть вторая опорная метка. Но мы бы ее сразу стерли, поэтому и ставить не будем
                8: →
                9:? 12, 10 // нашли ли ячейку?
                10: ← // да — возвращаемся к первой опорной метке и выходим из цикла
                11:? 10, 22
                12: 1 // нет — ставим новую метку и возвращаемся к первой
                13: ←
                14? 13, 15
                15: 0 // стерли первую метку
                16: ←
                17:? 18, 22 // нашли ли ячейку?
                18: 1 // нет — продолжаем поиск
                19: →
                20:? 19, 21 // поиск правой опорной метки
                21: 0 8 // стерли и ушли на цикл
                // сейчас у нас поставлены две опорных метки и стерта ровно одна ячейка. Мы не левой опорной метке, между метками хотя бы два нуля
                22: →
                23: →
                24: 1 // создали центральный блок. Он может оказаться вплотную к правой метке, но это не страшно
                25: → // пошел главный цикл
                26:? 25, 27
                27: 0
                28: →
                29:? 30, 33
                30: 1
                31: ←
                32:? 31, 37
                33: ←
                34:? 33, 35
                35: →
                36: 1
                37: ←
                38:? 39, 37
                39: ←
                40:? 39, 41
                41: 0
                42: ←
                43:? 44, 47
                44: 1
                45: →
                46:? 45, 51
                47: →
                48:? 47, 49
                49: ←
                50: 1
                51: →
                52:? 51, 25

                Можно написать код в 23 состояния (слегка переделав первую часть программы), в результате работы которого на ленте окажутся два расползающихся в разные стороны блока из 1 и n+1 метки.
                • 0
                  не смог привести этот код в рабочее состояние.
                  • 0
                    В строке 14 пропущено двоеточие
                    в строке 52 перепутаны адреса — должно быть

                    52:? 25, 51

                    строки с 29 по 37 должны выглядеть так:

                    29:? 33, 30
                    30: ←
                    31:? 30, 32
                    32: → 24
                    33: 1
                    34: ←
                    35:? 34, 37
                    36:! // сэкономленное состояние, никогда не выполняется
                    37: ←

                    Мне пока не удалось ее обмануть (пришлось написать свой интерпретатор — код на Java, если это не .jar, я запускать не умею)
                    • 0
                      Можно сэкономить еще состояние 32, если написать
                      31:? 30, 23

                      Итого 50
  • 0
    Числа Фибоначчи — 43 состояния (включая остановку). Каретка вначале стоит на левой метке числа.

    0:!
    1: ←
    2: ←
    3: 1
    4: →
    5: ?4,6
    6: 0
    7: →
    8: ?36,9
    9: ←
    10: ?9,11
    11: 0
    12: ←
    13: ?14,12
    14: ←
    15: ?16,14
    16: ←
    17: ?18,16
    18: 1
    19: →
    20: ?21,19
    21: →
    22: ?23,21
    23: →
    24: ?29,25
    25: →
    26: ?27,25
    27: 1
    28: ← 11
    29: 1
    30: ←
    31: 1
    32: →
    33: ?34,32
    34: ←
    35: 0 4
    36: ←
    37: ?36,38
    38: ←
    39: ?40,38
    40: ←
    41: ?0,42
    42: 0 40
    • 0
      UPD. Можно сократить до 40 — но тогда программа будет выполнять одно лишнее сложение.
  • 0
    Деление с остатком — 31 состояние:

    0:!
    1: 0
    2: →
    3: ?4,2
    4: →
    5: ?25,6
    6: →
    7: ?8,6
    8: ←
    9: 0
    10: ←
    11: ?12,10
    12: ←
    13: ?14,12
    14: 1
    15: →
    16: ?17,1
    17: ←
    18: ?19,17
    19: ←
    20: ?21,19
    21: 1
    22: →
    23: ?24,22
    24: → 1
    25: ←
    26: ←
    27: ?29,28
    28: 0 26
    29: ←
    30: ?0,29

    На ленте записан делитель, потом (через один 0) делимое. Делимое может быть нулем. Каретка стоит на левой единице делителя.
    В конце каретка оказывается на ячейке с нулем. Слева от нее — частное, справа — остаток. И то, и другое может быть нулем.

    Кто сделает короче?

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.