Программирование на машине Поста

Недавно на хабре появилось сразу два материала, посвященных языкам из «большой четверки тьюринговых трясин»: про алгоритм Маркова и 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 — самые изучаемые тьюринговые трясины.
Поделиться публикацией
Комментарии 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) делимое. Делимое может быть нулем. Каретка стоит на левой единице делителя.
              В конце каретка оказывается на ячейке с нулем. Слева от нее — частное, справа — остаток. И то, и другое может быть нулем.

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

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

              Самое читаемое