Talk:Bitwise Cyclic Tag

From Esolang
Jump to: navigation, search

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)