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

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

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

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

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