Bitwise Cyclic Tagの概要と実装例まとめ

この記事は，[Bitwise Cyclic Tag](https://esolangs.org/wiki/Bitwise_Cyclic_Tag)（Esolang Wiki）の構成や実行手順の概要と，様々なプログラミング言語による実装例について述べています．

【関連記事】[タグシステム（抽象機械）の各言語等実装例まとめ](https://qiita.com/ytaki0801/items/d933fc1db1b152043ca3)

# Bitwise Cyclic Tagの概要

[万能チューリングマシンと等価](https://ja.wikipedia.org/wiki/%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E5%AE%8C%E5%85%A8)であることが証明されているものに**Cyclic Tag System**（[循環タグシステム](https://ja.wikipedia.org/wiki/%E3%82%BF%E3%82%B0%E3%82%B7%E3%82%B9%E3%83%86%E3%83%A0#%E5%BE%AA%E7%92%B0%E3%82%BF%E3%82%B0%E3%82%B7%E3%82%B9%E3%83%86%E3%83%A0)）があり，キュー構造処理に基づく極めて単純な構成であることから，**様々な仕組みがチューリング完全であることを示すために実装される**ことがあります．

- [On the Turing Completeness of Super Mario Maker](https://youtu.be/hd0EtsTUbmg)
- [Universality in Rule 110](https://www.comunidad.escom.ipn.mx/genaro/rule110/ctsRule110.html)
- [Universality of Wolfram’s 2, 3 Turing Machine](https://www.wolframscience.com/prizes/tm23/TM23Proof.pdf)

**[Bitwise Cyclic Tag](https://esolangs.org/wiki/Bitwise_Cyclic_Tag)（以下BCT）は，このCyclic Tag Systemをエミュレートできるプログラミング言語**として構成されていますが，そのプログラム実行手順はCyclic Tag Systemよりも[更にシンプル](https://esolangs.org/wiki/Bitwise_Cyclic_Tag#BCT_programs)です．BCT処理系には，プログラムと（初期値としての）データが与えられ，それぞれキュー構造処理が可能であることが想定されています．

| プログラム先頭 | 実行 |
|:-:|:-:|
| 0 | データの先頭1ビットを削除 |
| 11 | データの先頭1ビットが1ならば，1をデータの後尾に追加 |
| 10 | データの先頭1ビットが1ならば，0をデータの後尾に追加 |

※プログラム先頭1～2ビットは最後尾に追加され，先頭からは削除される．
※以上を，データが一定の要素数未満になるまで繰り返す[^1]．
[^1]: Esolang Wiki原文では『データが空になれば停止』なのですが，コラッツ数列の計算例のように，元となったタグシステムの削除数*m*未満の要素数で停止する必要があるなど，計算本体で停止処理できないものもあるため，ここではこのように設定しています．なお，Wiki原文の『プログラムが空ならば即座に停止』についても，例外処理相当と捉えて今回は言及していません．

疑似コード風に記述したPythonプログラムの例は次のようになります．基本的には，一定要素数未満となるまでの反復，先頭が１かどうかによる分岐，先頭や後尾の要素を追加・複製・削除するといったキュー処理のみで構成できます．
```py
while 一定の要素数未満ではない(データ):
    if 先頭が１(プログラム):
        後尾に追加(プログラム, 先頭を複製(プログラム))
        先頭を削除(プログラム)
        if 先頭が１(データ):
            後尾に追加(データ, 先頭を複製(プログラム))
    else:
        先頭を削除(データ)
    後尾に追加(プログラム, 先頭を複製(プログラム))
    先頭を削除(プログラム)
    出力(データ)
```

プログラムやデータは，[タグシステム](https://ja.wikipedia.org/wiki/%E3%82%BF%E3%82%B0%E3%82%B7%E3%82%B9%E3%83%86%E3%83%A0)の考え方で構成されます．タグシステムは，キュー（データ）の先頭の記号に対応する記号列を生成規則（プログラム）より導いてキューの最後尾に追加し，決まった数*m*の記号をキューの先頭より削除します．このシステムのうち，削除数*m=2*の **[2-タグシステム](https://qiita.com/ytaki0801/items/d933fc1db1b152043ca3)** は，万能チューリングマシンをエミュレートできることが証明されています．

2-タグシステムの生成規則としては[コラッツ数列の計算](https://ja.wikipedia.org/wiki/%E3%82%BF%E3%82%B0%E3%82%B7%E3%82%B9%E3%83%86%E3%83%A0#%E4%BE%8B:_%E3%82%B3%E3%83%A9%E3%83%83%E3%83%84%E6%95%B0%E5%88%97%E3%81%AE%E8%A8%88%E7%AE%97)が知られており，次のキュー初期値と生成規則で構成されています．なお，キューの要素数が*m=2*未満となると削除できないため，キューの要素数が1となった際に（[本来のコラッツ関数と同じく](https://ja.m.wikipedia.org/wiki/%E3%82%B3%E3%83%A9%E3%83%83%E3%83%84%E3%81%AE%E5%95%8F%E9%A1%8C#%E6%A6%82%E8%A6%81)）停止することが想定されています．

- 使用する記号：`a`，`b`，`c`
- 生成規則：`a`⇒`bc`，`b`⇒`a`，`c`⇒`aaa`
- 初期値：`aaaaa`（整数5を表現）

Cyclic Tag Systemは記号として二値（ここでは`0`と`1`）のみを用いる仕組みで，キューの削除数は1のみですが，記号を次のように置き換え，*(削除数m=2)×(3規則)＝6個*の生成規則をキューに循環適用することで，**2-タグシステムをエミュレートすることが可能**です．次の例では，記号が3つであることから，キューの要素数が3となった際に停止することが想定されています．

- 使用する記号の置き換え：`a`を`100`，`b`を`010`，`c`を`001`
- 生成規則の記号列：`{010001, 100, 100100100, '', '', ''}`（`''`は記号を追加しない）
- 初期値：`100100100100100`

BCTは，**生成規則をプログラムとして更に置き換える**ことで，Cyclic Tag Systemの循環適用をプログラム実行手順の一部としています．コラッツ数列の計算を用いた例は次の通りです．データ相当のキューの初期値はそのままで，Cyclic Tag Systemと同じく，キューの要素数が3となった際に停止することが想定されています．

- 生成規則の記号列の最後に，BCTの`0`の実行を示す仮記号として`;`を追加し，結合する．
⇒`010001;100;100100100;;;;`
- `0`を`10`，`1`を`11`，`;`を`0`に置き換える．
⇒`10 11 10 10 10 11 0 11 10 10 0 11 10 10 11 10 10 11 10 10 0 0 0 0`
⇒`101110101011011101001110101110101110100000`

# 実装例

最初に，前節の疑似コード風に記述したPythonプログラムによる，初期値5のコラッツ数列の実行例を示します．Debian GNU/Linux 11 x86_64のシェル環境でPython 3.9.2による実行を確認しています．
```bct_ja.py
def キューを初期化(d):
    r = []
    for c in d: r.append(True if c == '1' else False)
    return r
def 先頭を複製(s): return s[0]
def 先頭を削除(s): s.pop(0)
def 後尾に追加(s, t): s.append(t)
def 先頭が１(s): return s[0]
def 一定の要素数未満ではない(s): return s[3:]
def 出力(s): print(''.join(['1' if c else '0' for c in s]))
```
```bct-Collatz5_ja.py
from bct_ja import *

データ = キューを初期化("100100100100100")
プログラム = キューを初期化("101110101011011101001110101110101110100000")

while 一定の要素数未満ではない(データ):
    if 先頭が１(プログラム):
        後尾に追加(プログラム, 先頭を複製(プログラム))
        先頭を削除(プログラム)
        if 先頭が１(データ):
            後尾に追加(データ, 先頭を複製(プログラム))
    else:
        先頭を削除(データ)
    後尾に追加(プログラム, 先頭を複製(プログラム))
    先頭を削除(プログラム)
    出力(データ)
```
```
$ python3 bct-Collatz5_ja.py
1001001001001000
10010010010010001
100100100100100010
1001001001001000100
10010010010010001000
100100100100100010001
00100100100100010001
00100100100100010001
00100100100100010001
00100100100100010001
（略）
0001100
0001100
0001100
0001100
0001100
0001100
001100
01100
1100
100
```
【参考】

https://www.youtube.com/watch?v=cuWR719nzrY&t=59s

次は，各言語に特化して作成した実装例です．出力結果は全て同じです（上記デモ動画参照）．

## Python
```py:bct-Collatz5.py（Python 3.9.2）
q = '100100100100100'
r = '101110101011011101001110101110101110100000'

while q[3:]:
    if r[0] == '0': q = q[1:]
    else:
        r = r[1:]+'1'
        if q[0] == '1': q += r[0]
    r = r[1:]+r[0]
    print(q)
```
## Scheme
```scheme:bct-Collatz5.scm（Gauche 0.9.12，Chibi-Scheme 0.10.0）
(define (bct q r)
  (for-each display q) (newline)
  (if (zero? (length (cdddr q))) q
      (if (zero? (car r))
          (bct (cdr q) (append (cdr r) '(0)))
          (bct (append q (if (zero? (car q)) '() `(,(cadr r))))
               (append (cddr r) `(,(car r) ,(cadr r)))))))

(bct '(1 0 0 1 0 0 1 0 0 1 0 0 1 0 0)
     '(1 0 1 1 1 0 1 0 1 0 1 1 0 1 1 1 0 1 0 0 1
       1 1 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 0 0 0 0))
```
## C
```c:bct-Collatz5.c（gcc 10.2.1）
#include <stdio.h>
#include <string.h>

#define QMAX 16384

char t[QMAX];
char deq(char s[]) { char c = s[0]; strcpy(t, s+1); strcpy(s, t); return c; }
void enq(char s[], char c) { int i = strlen(s); s[i] = c; s[i+1] = '\0'; }

int main(void)
{
  char q[QMAX], r[QMAX];
  strcpy(q, "100100100100100");
  strcpy(r, "101110101011011101001110101110101110100000");

  while (q[3]) {
    if (r[0] == '0') deq(q);
    else {
      enq(r, deq(r));
      if (q[0] == '1') enq(q, r[0]);
    }
    enq(r, deq(r));
    printf("%s\n", q);
  }

  return 0;
}
```
## Rust
```rs:bct-Collatz5.rs（rustc 1.48.0）
fn main() {
  let mut q = String::from("100100100100100");
  let mut r = String::from("101110101011011101001110101110101110100000");

  while q.len() != 3 {
    if r.chars().nth(0) == Some('0') { q.remove(0); }
    else {
      r.remove(0); r += "1";
      if q.chars().nth(0) == Some('1') {
        q += if r.chars().nth(0) == Some('0') { "0" } else { "1" };
      }
    }
    let d = r.remove(0); r.push(d);
    println!("{}", q);
  }
}
```
## Prolog
```prolog:bct-Collatz5.swi
bct_([_,_,_],_).
bct_([_|Q],[0|R])   :- append(R,[0],  RN), bct(Q,RN).
bct_([1|Q],[1,0|R]) :- append(R,[1,0],RN), append(Q,[0],QN), bct([1|QN],RN).
bct_([0|Q],[1,0|R]) :- append(R,[1,0],RN), bct([0|Q],RN).
bct_([1|Q],[1,1|R]) :- append(R,[1,1],RN), append(Q,[1],QN), bct([1|QN],RN).
bct_([0|Q],[1,1|R]) :- append(R,[1,1],RN), bct([0|Q],RN).

bct(Q,R) :- maplist(write, Q), nl, bct_(Q,R).

:- bct([1,0,0,1,0,0,1,0,0,1,0,0,1,0,0],
       [1,0,1,1,1,0,1,0,1,0,1,1,0,1,1,1,0,1,0,0,1,
        1,1,0,1,0,1,1,1,0,1,0,1,1,1,0,1,0,0,0,0,0]).
:- halt.
```
## Haskell
```hs:bct-Collatz5.hs（GHC 8.8.4）
bct (_:_:_:[]) _ l = l
bct (_:q) ('0':r) l = bct q (r ++ '0':[]) (l ++ q:[])
bct ('1':q) ('1':'0':r) l = bct ('1':q ++ '0':[]) (r ++ '1':'0':[]) (l ++ q:[])
bct ('0':q) ('1':'0':r) l = bct ('0':q) (r ++ '1':'0':[]) (l ++ q:[])
bct ('1':q) ('1':'1':r) l = bct ('1':q ++ '1':[]) (r ++ '1':'1':[]) (l ++ q:[])
bct ('0':q) ('1':'1':r) l = bct ('0':q) (r ++ '1':'1':[]) (l ++ q:[])

main = do
  let q = "100100100100100"
  let r = "101110101011011101001110101110101110100000"
  mapM putStrLn $ bct q r []
```
## POSIX Shell
```sh:bct-Collatz5.sh（dash 0.5.11）
Q=100100100100100
R=101110101011011101001110101110101110100000

while [ ${Q#???} ]; do
  case ${R%${R#?}} in
    0) Q=${Q#?};;
    *) R=${R#?}1
       case ${Q%${Q#?}} in 1) Q=$Q${R%${R#?}};; esac
  esac
  R=${R#?}${R%${R#?}}
  echo $Q
done
```

# 備考

## 記事に関する補足
- Haskell版は手抜き感満載（Prolog版の焼き直し…）．

## 更新履歴
- 2023-01-28：疑似コード風Pythonプログラム例を改訂
- 2023-01-27：停止判定に関する脚注を追加
- 2023-01-27：初版公開