fixedpoint.jp


Introduction to tag, a Tag system processor (2019-02-03)

Emil Post's Tag system is a simple yet Turing-complete abstract machine. Here we introduce an open-source implementation of Tag system processor called tag: https://github.com/fixedpoint/tag.

With tag, it is easy to define and run your favorite Tag system, which accepts any finite input word written in a user-defined set of alphabets. For example, if you would like to run a well-known 2-Tag system for Collatz (sub)sequences, save the following three lines encoding its rules with alphabets {a, b, c}:

a bc
b a
c aaa

Supposing that the file is named collatz.txt in your working directory,

$ tag -i collatz.txt aaaaa
will generate the following outout and halt successfully:
aaaaa
  aaabc
    abcbc
      cbcbc
        cbcaaa
          caaaaaa
            aaaaaaaa
              aaaaaabc
                aaaabcbc
                  aabcbcbc
                    bcbcbcbc
                      bcbcbca
                        bcbcaa
                          bcaaa
                            aaaa
                              aabc
                                bcbc
                                  bca
                                    aa
                                      bc
                                        a

Please find more details in tag's README. Enjoy Tag systems and your feedback is highly appreciated.


© 2006-2019 fixedpoint.jp