Talk:Bitwise Cyclic Tag
Commands in BCT
BCT has two commands (0 and 1); however, operationally, a 1-command always pairs with the next command after it, effectively producing the composite commands 10 and 11. A trivial variant of BCT would have three non-composite commands, say {0, 10, 11} with the obvious definitions. --r.e.s. (Talk) 11:53, 13 August 2007 (UTC)
I've added a note in the article, explaining how BCT was in fact obtained from such a three-command language (which might be called CT). --71.135.227.61 00:03, 12 October 2007 (UTC)
Turing-completeness of BCT without arbitrary memory string as input?
Could a variant of BCT (or CT which is also in this article) be Turing-complete without the input memory string? Could there be a Turing-complete variation where instead of being input the memory were a constant like "01" every time, and the actual program string needed to create the "initial" memory or something to that effect? --Keymaker (talk) 13:19, 13 December 2013 (UTC)
- I believe it's Turing-complete with a constant "1" as the initial memory string, for much the same reason as in DownRight; you can just use the first rule for the initial string, then arrange for it to never be run again. --ais523 18:27, 17 January 2014 (UTC) 18:27, 17 January 2014 (UTC)
- For any BCT (program-string, data-string) pair, say (P,Q), there is a pair (P',1) that simulates the same computation. This follows from Lemma 7 in a 2013 paper by Turlough Neary, Undecidability in binary tag systems and the Post correspondence problem for four pairs of words: "Lemma 7. Let C = α_0, α_1 . . . , α_{p−1} be a cyclic tag system and let w be an input dataword to C. Then there is a cyclic tag system C_w that takes a single 1 as its input and simulates the computation of C on w." I will update the article to mention this. -- r.e.s. 16:24, 26 July 2015 (UTC)
There was already a TC-proof
Collatz function#Reduction to cyclic tag systems, also linked from Cyclic tag system. --Ørjan (talk) 18:46, 4 June 2018 (UTC)
- Oh well, I guess we have three now. That can't hurt for something that's at the base of most of our TC hierarchy. --ais523 20:23, 4 June 2018 (UTC)
Explicit example of a translated register machine
The following program is a translation of a 2-command register machine that adds its inputs into the left register.
10101010101010101010101010101010101010 0 11101110101010101010101010101010101010 11101010101110101010101010101010101010 0 10111010101010101010101010101010101010 11101011101010101010101010101010101011 10111010101010101010101010101010101010 0 10101010111010101010101010101010101010 0 10111010101010101010101010101010101010 10111010101010101010101010101010101010 0 11101011101010101010101010101010101011 10111010101010101010101010101010101010 11101011101010101010101010101010101011 0 11101010101011101010101010101010101010 11101010101011101010101010101010101010 0 10101010101010101010101010101011101011 11101010101010111010101010101010101010 10101010101010101110101010101110101010 0 10101010101010101110101010101010101010 10101010101010101011101010101010101011 0 11101010101010111010101010101010101010 0 11101010101010101010101110101010101011 0 11101010101010101010101011101010101010 0 10101010101010101010101010111010101011 0 11101010101010101010101010101010101010 0 10101010101010101010101010111010101010 0 10101010101010101010101010101010111011 0 10101010101010101010101010101010101110 0 11101010101010101010101010111010101011 0 10101010101010101010101010101010101010 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
The starting queue is 0000000000000001001000000000000000000000000000100000100000000000000000000000, 2^a copies of 01000000000000000000000000000000000000, 10000010000000000000000000000000000000, and 2^b copies of 01000000000000000000000000000000000000. The cyclic tag system never empties its queue, but the emulated MRM halts when the tenth production executes with a queue length of 19 mod 38. CatIsFluffy (talk) 21:56, 3 January 2021 (UTC)
Python Interpreter
Here is an interpreter I made for Bitwise Cyclic Tag in Python. It takes in the program string (p) and the data string (d) and returns the deletion sequence (s)
def bct(p,d):
t = 1
s = d
p += p
while d:
if p[t-1:t] == '0': d = d[1:]
if p[t-1:t] == '1':
t += 1
if d[:1] == '1':
d += p[t-1:t]
s += p[t-1:t]
t += 1
if t > len(p)/2: t=1
return s
I hope this helps someone. CosmicMan08 (talk) 23:47, 2 August 2021 (UTC)
I didn't realize this was here and made my own Python interpreter. I linked to your Python interpreter on the main page, and now I want to put mine here too, because it operates differently to interpret the language. Squidmanescape (talk) 08:12, 21 November 2021 (UTC)
def run_bct(program: str, data: str) -> None:
# Will not operate on strings which contain non-bits
for bit in program:
if bit not in "01":
return
for bit in data:
if bit not in "01":
return
# padding for print statements
padding = ""
# allows you to step through the program
# and quickly stop infinite loops
stop = ""
# if data is empty, it stops
# if input is not empty, it stops
while data != "" and stop == "":
if program[0] == "0":
# prints output similar to esolangs page
print(f" {program[0]}|{padding}{data}", end="")
program = program[1:] + program[:1]
padding += " "
data = data[1:]
else:
print(f"{program[:2]}|{padding}{data}", end="")
if data[0] == "1":
data += program[1]
program = program[2:] + program[:2]
stop = input()
CT in python 3
def l2s(L):
s =
for c in L:
s += c
return s
print('exit via ctrl-c')
p = input('program here:')
d = input('data here:')
try:
while 1:
for s in p:
if s != ';':
d += s * (d[0] in '*1')
else:
L = list(d)
del L[0]
d = l2s(L)
print(d)
except:
pass
lets do a code walk (yay)
ask for program and data repeat until ctrl-c:
repeat for every command:
if the command is not ;
it must be a 1 or 0
if d[0] is a 1:append the command to d
if it was a ; instead delete d[0]
--Example99 (talk) 12:25, 6 May 2023 (UTC)
TCness of self-BCT
Is there a proof that self-BCT is TC? Maybe it's trivial and I'm just blind, but if so it would be nice to mention it on the page. It would give an easier way of proving TCness of some languages. Olus2000 (talk) 08:08, 3 February 2024 (UTC)