この記事は，Bitwise Cyclic Tag（Esolang Wiki）の構成や実行手順の概要と，様々なプログラミング言語による実装例について述べています．
【関連記事】タグシステム（抽象機械）の各言語等実装例まとめ
Bitwise Cyclic Tagの概要
万能チューリングマシンと等価であることが証明されているものにCyclic Tag System（循環タグシステム）があり，キュー構造処理に基づく極めて単純な構成であることから，様々な仕組みがチューリング完全であることを示すために実装されることがあります．
- On the Turing Completeness of Super Mario Maker
- Universality in Rule 110
- Universality of Wolfram’s 2, 3 Turing Machine
Bitwise Cyclic Tag（以下BCT）は，このCyclic Tag Systemをエミュレートできるプログラミング言語として構成されていますが，そのプログラム実行手順はCyclic Tag Systemよりも更にシンプルです．BCT処理系には，プログラムと（初期値としての）データが与えられ，それぞれキュー構造処理が可能であることが想定されています．
| プログラム先頭 | 実行 |
|---|---|
| 0 | データの先頭1ビットを削除 |
| 11 | データの先頭1ビットが1ならば，1をデータの後尾に追加 |
| 10 | データの先頭1ビットが1ならば，0をデータの後尾に追加 |
※プログラム先頭1～2ビットは最後尾に追加され，先頭からは削除される．
※以上を，データが一定の要素数未満になるまで繰り返す1．
疑似コード風に記述したPythonプログラムの例は次のようになります．基本的には，一定要素数未満となるまでの反復，先頭が１かどうかによる分岐，先頭や後尾の要素を追加・複製・削除するといったキュー処理のみで構成できます．
while 一定の要素数未満ではない(データ):
if 先頭が１(プログラム):
後尾に追加(プログラム, 先頭を複製(プログラム))
先頭を削除(プログラム)
if 先頭が１(データ):
後尾に追加(データ, 先頭を複製(プログラム))
else:
先頭を削除(データ)
後尾に追加(プログラム, 先頭を複製(プログラム))
先頭を削除(プログラム)
出力(データ)
プログラムやデータは，タグシステムの考え方で構成されます．タグシステムは，キュー（データ）の先頭の記号に対応する記号列を生成規則（プログラム）より導いてキューの最後尾に追加し，決まった数mの記号をキューの先頭より削除します．このシステムのうち，削除数m=2の 2-タグシステム は，万能チューリングマシンをエミュレートできることが証明されています．
2-タグシステムの生成規則としてはコラッツ数列の計算が知られており，次のキュー初期値と生成規則で構成されています．なお，キューの要素数がm=2未満となると削除できないため，キューの要素数が1となった際に（本来のコラッツ関数と同じく）停止することが想定されています．
- 使用する記号：
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による実行を確認しています．
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]))
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
【参考】
次は，各言語に特化して作成した実装例です．出力結果は全て同じです（上記デモ動画参照）．
Python
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
(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
#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
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
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
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
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：初版公開
-
Esolang Wiki原文では『データが空になれば停止』なのですが，コラッツ数列の計算例のように，元となったタグシステムの削除数m未満の要素数で停止する必要があるなど，計算本体で停止処理できないものもあるため，ここではこのように設定しています．なお，Wiki原文の『プログラムが空ならば即座に停止』についても，例外処理相当と捉えて今回は言及していません． ↩