Abuse filter log

Abuse Filter navigation (Home | Recent filter changes | Examine past edits | Abuse log)
Jump to navigation Jump to search
Details for log entry 7,064

14:44, 31 March 2018: Hq9++fan (talk | contribs) triggered filter 12, performing the action "edit" on Bitwise Cyclic Tag. Actions taken: Disallow; Filter description: pattern vandalism/revert-warring: Unicode subscripts/superscripts (examine)

Changes made in edit

 
! BCT data-string !! Bijective base-2 numeral !! Integer represented
 
! BCT data-string !! Bijective base-2 numeral !! Integer represented
 
|-
 
|-
| b<sub>0</sub> b<sub>1</sub> ... b<sub>k</sub> || (b<sub>k</sub> + 1)(b<sub>k-1</sub> + 1)...(b<sub>0</sub> + 1) || SUM{(b<sub>i</sub> + 1) 2<sup>i</sup>: i = 0..k}
+
| b₀ b₁ ... bₖ || (bₖ + 1)(bₖ₋₁ + 1)...(b₀ + 1) || SUM{(bᵢ + 1) 2ⁱ: i = 0..k}
 
|}
 
|}
   
Note that the digits 1,2 are represented by the bits 0,1 respectively, and the numeral is read in ''reverse'' order from the bit-string. E.g., the BCT data-string 011 corresponds to the bijective base-2 numeral 221, representing the integer <u><b>2</b></u>*2<sup>2</sup> + <u><b>2</b></u>*2<sup>1</sup> + <u><b>1</b></u>*2<sup>0</sup> = 13.
+
Note that the digits 1,2 are represented by the bits 0,1 respectively, and the numeral is read in ''reverse'' order from the bit-string. E.g., the BCT data-string 011 corresponds to the bijective base-2 numeral 221, representing the integer <u><b>2</b></u>*2² + <u><b>2</b></u>*2¹ + <u><b>1</b></u>*2⁰ = 13.
   
 
Each BCT command in a program then corresponds to an explicit numerical function defined on the set '''N''' of nonnegative integers, as follows:
 
Each BCT command in a program then corresponds to an explicit numerical function defined on the set '''N''' of nonnegative integers, as follows:
 
| 0|| f(n) = [n is positive] * floor((n-1)/2)
 
| 0|| f(n) = [n is positive] * floor((n-1)/2)
 
|-
 
|-
| 10 || g<sub>0</sub>(n) = n + [n is positive and even] * 2<sup>(floor(log<sub>2</sub>(n+1)) + 0)</sup>
+
| 10 || g₀(n) = n + [n is positive and even] * 2⁽ᶠˡᵒᵒʳ⁽ˡᵒᵍ-²⁽ⁿ⁺¹⁾⁾ ⁰⁾
 
|-
 
|-
| 11 || g<sub>1</sub>(n) = n + [n is positive and even] * 2<sup>(floor(log<sub>2</sub>(n+1)) + 1)</sup>
+
| 11 || g₁(n) = n + [n is positive and even] * 2⁽ᶠˡᵒᵒʳ⁽ˡᵒᵍ-²⁽ⁿ⁺¹⁾⁾ ¹⁾
 
|}
 
|}
   
where we've shown separately the two cases for the program-bit that's next after the 1-command. Here [''condition''] is an [http://en.wikipedia.org/wiki/Iverson_bracket Iverson bracket], meaning 1 if ''condition'' is true, else 0; so the integer 0 is a fixed-point of all three of the functions f, g<sub>0</sub>, g<sub>1</sub>, and represents a permanent "halt" condition. (Also note that floor(log<sub>2</sub>(n+1)) is just the number of digits in the bijective base-2 numeral for n.)
+
where we've shown separately the two cases for the program-bit that's next after the 1-command. Here [''condition''] is an [http://en.wikipedia.org/wiki/Iverson_bracket Iverson bracket], meaning 1 if ''condition'' is true, else 0; so the integer 0 is a fixed-point of all three of the functions f, g₀, g₁, and represents a permanent "halt" condition. (Also note that floor(log₂(n+1)) is just the number of digits in the bijective base-2 numeral for n.)
   
Thus a BCT program is equivalent to a composition of finitely-many instances of the three functions f, g<sub>0</sub>, g<sub>1</sub>, all but some initial portion of which is iterated. Just as the sequence of successive data-strings encodes all input and output in a BCT computation, in the arithmetic interpretation the same role is fulfilled by the sequence of successive nonnegative integer arguments.
+
Thus a BCT program is equivalent to a composition of finitely-many instances of the three functions f, g₀, g₁, all but some initial portion of which is iterated. Just as the sequence of successive data-strings encodes all input and output in a BCT computation, in the arithmetic interpretation the same role is fulfilled by the sequence of successive nonnegative integer arguments.
   
 
===Gödel numbering===
 
===Gödel numbering===
   
A [http://en.wikipedia.org/wiki/G%C3%B6del_number Gödel numbering] of BCT programs is automatically provided by similarly interpreting each BCT program as the bijective base-2 numeral of an integer (now in the usual digit-order, unlike the data-string). Thus, <u>a BCT program is (the numeral of) its own Gödel number</u>. E.g., the program 011 is interpreted as the integer 10 (ten = 122 in bijective base-2) &mdash; and indeed 011 is the tenth nonempty BCT program in a [http://en.wikipedia.org/wiki/Shortlex_order shortlex ordering] of the set of all BCT programs.
+
A [http://en.wikipedia.org/wiki/G%C3%B6del_number Gödel numbering] of BCT programs is automatically provided by similarly interpreting each BCT program as the bijective base-2 numeral of an integer (now in the usual digit-order, unlike the data-string). Thus, <u>a BCT program is (the numeral of) its own Gödel number</u>. E.g., the program 011 is interpreted as the integer 10 (ten = 122 in bijective base-2) &mdash; and indeed 011 is the tenth nonempty BCT program in a [http://en.wikipedia.org/wiki/Shortlex_order shortlex ordering] of the set of all BCT programs.
   
 
===Example===
 
===Example===
 
step# cmd function bit-string bij. base-2 decimal function evaluation
 
step# cmd function bit-string bij. base-2 decimal function evaluation
 
----- ---- -------- ---------- ----------- ------- -------------------
 
----- ---- -------- ---------- ----------- ------- -------------------
0001 11 * g<sub>1</sub> 10 12 4
+
0001 11 * g₁ 10 12 4
 
 
0002 0 f 101 212 12 = g<sub>1</sub>(4)
+
0002 0 f 101 212 12 = g₁(4)
 
 
0003 10 g<sub>0</sub> 01 21 5 = f(12)
+
0003 10 g₀ 01 21 5 = f(12)
 
 
0004 0 f 01 21 5 = g<sub>0</sub>(5)
+
0004 0 f 01 21 5 = g₀(5)
 
 
0005 11 * g<sub>1</sub> 1 2 2 = f(5)
+
0005 11 * g₁ 1 2 2 = f(5)
 
 
0006 0 f 11 22 6 = g<sub>1</sub>(2)
+
0006 0 f 11 22 6 = g₁(2)
 
 
0007 10 g<sub>0</sub> 1 2 2 = f(6)
+
0007 10 g₀ 1 2 2 = f(6)
 
 
0008 0 f 10 12 4 = g<sub>0</sub>(2)
+
0008 0 f 10 12 4 = g₀(2)
 
 
0009 11 * g<sub>1</sub> 0 1 1 = f(4)
+
0009 11 * g₁ 0 1 1 = f(4)
 
 
0010 0 f 0 1 1 = g<sub>1</sub>(1)
+
0010 0 f 0 1 1 = g₁(1)
 
 
 
(halt) - - 0 = f(1)
 
(halt) - - 0 = f(1)

Action parameters

VariableValue
Whether or not the edit is marked as minor (no longer in use) (minor_edit)
false
Edit count of the user (user_editcount)
105
Name of the user account (user_name)
'Hq9++fan'
Age of the user account (user_age)
38870972
Page ID (page_id)
1621
Page namespace (page_namespace)
0
Page title (without namespace) (page_title)
'Bitwise Cyclic Tag'
Full page title (page_prefixedtitle)
'Bitwise Cyclic Tag'
Action (action)
'edit'
Edit summary/reason (summary)
'they are ! ! ! because they are customizable by the font designers!'
Old content model (old_content_model)
'wikitext'
New content model (new_content_model)
'wikitext'
Old page wikitext, before the edit (old_wikitext)
''''Bitwise Cyclic Tag (BCT)''' is a [[Turing-complete]] programming language using only two commands (0 and 1) to operate on a finite data-bitstring extensible without bound on the right. Its extremely simple syntax and semantics make it a useful target for [[Computational_class#Simulation|simulation]]-based proofs of a language's computational class. ==BCT programs== A '''BCT program''' is any finite string of bits (commands), executed as follows: {| class="wikitable" |- ! Command !! Execution |- | 0 || Delete the leftmost data-bit. |- | 1 || Goto the next command (say x). If the leftmost data-bit is 1, copy x to the right end of the data-string. |} If the program-string or the data-string is initially empty, execution halts immediately; otherwise, starting at the leftmost program-bit and halting only when the data-string becomes empty, the commands are executed in cyclic sequence from left to right (the leftmost bit following next after the rightmost bit). The program pointer advances one bit after each command-execution, and also advances one bit when the goto in a 1-command is executed; consequently, a 1-command always pairs with the next command after it (say x), such that 1x is effectively a composite command whose execution is if the leftmost data-bit is 1: copy x to the right end of the data-string Four equivalent variations of BCT are obtained by exchanging the roles of symbols 0 and 1 as commands, and by varying the parity required in the condition for copying a bit to the end of the data-string. ===Example=== Program: 00111 Execution sequence: 00111 (00111) (00111) (00111) ... = 0 (0 11 10) (0 11 10) (0 11 10) ... Initial data-string: 101 System evolution: Commands Data- Executed String -------- ------- 0 101 0 01 11 1 10 11 0 110 11 10 10 101 0 1010 11 010 10 010 0 010 11 10 ... ... ==BCT emulation of cyclic tag systems== For any [[cyclic tag system]] on a binary alphabet, there is a BCT program that emulates it (thus establishing that BCT is Turing-complete, since the set of cyclic tag systems is Turing-complete). Specifically, a BCT program that emulates a given cyclic tag system is obtained by writing the cyclic tag system productions as ';'-terminated strings, concatenating these strings, and then applying the following substitutions: 0 <-- 10 1 <-- 11 ; <-- 0 The initial data-string for the BCT program is the unaltered initial binary word for the cyclic tag system. '''*Note*''': BCT remains Turing complete even if the initial data-string is always just a single '''1'''. This is because, 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 a result in [http://arxiv.org/abs/1312.6700 Undecidability in binary tag systems and the Post correspondence problem for four pairs of words] (Turlough Neary, 2013), to the effect that for any cyclic tag system with initial word '''w''' (say), the same computation is simulated by some cyclic tag system whose initial word is a single '''1'''. ===The language '''CT'''=== BCT was created upon noticing that the operation of a cyclic tag system is exactly duplicated by interpreting the concatenation of its semicolon-terminated productions as a program that uses three commands {'''0''', '''1''', ''';'''} to operate on the current word (interpeted as a data bit-string). Calling this three-instruction language '''CT''', with programs that may be any finite string on {'''0''', '''1''', ''';'''}, the commands of a CT program are executed left-to-right in cyclic sequence, halting only when the data-string becomes empty: {| class="wikitable" |- ! CT Command !! Execution !! Equivalent BCT Command |- | 0 || If the leftmost data-bit is 1, append 0. || 10 |- | 1 || If the leftmost data-bit is 1, append 1. || 11 |- | ; || Delete the leftmost data-bit. || 0 |} The purpose of replacing CT by BCT was merely to obtain a language whose programs are binary (rather than ternary) strings. CT programs that might interest someone: *Program "1", data "1". Creates 'a pyramid of 1s'. *Program ";", data whatever. Removes all data and halts. *A sort of quines: Programs where the data remains forever identical to the initial program (and identical to data -- itself -- too). Any string consisting only of 0s and 1s, and which begins with a 0, suffices. Thus, for example: Program "0", data "0" (this is the shortest one possible). Program "0100111", data "0100111". ===Example (simple illustration)=== This is just to illustrate how things work ... Cyclic tag system Productions: (011, 10, 101) CT program: 011;10;101; Translation to a BCT program 011;10;101; --> 10 11 11 0 11 10 0 11 10 11 0 Initial data-string: 1 System evolution: Commands Executed Data-string -------- ------------- 10 1 11 10 11 101 0 1011 * 11 011 10 011 0 011 * 11 11 10 111 11 1110 0 11101 * 10 1101 11 11010 11 110101 0 1101011 * 11 101011 10 1010111 0 10101110 * 11 0101110 10 0101110 11 0101110 0 0101110 * 10 101110 ... ... The data-strings marked by '*' are those just after each deletion, and are the strings occurring in the evolution of the equivalent cyclic tag system, as follows: Production Data-string ---------- ------------- 011 1 10 011 101 11 011 1101 10 101011 101 0101110 011 101110 ... ... ===Example ([[Collatz sequence]])=== Here are B/CT programs that compute a [[Collatz sequence]] for the Collatz function in the form C(n) = (if n is even then n/2 else (3n+1)/2). Cyclic tag system: (010001, 100, 100100100, e, e, e) (where e is the empty word) CT program: 010001;100;100100100;;;; BCT program: 10 11 10 10 10 11 0 11 10 10 0 11 10 10 11 10 10 11 10 10 0 0 0 0 Initial data-string: (100)<sup>''n''</sup> (''n'' concatenated copies of '100', where ''n'' is a postive integer) In the computation, when (and only when) the data-string takes the form (100)<sup>''k''</sup> immediately before beginning a cycle through the program, it represents the integer ''k'' -- and these will be the successive terms of the Collatz sequence for ''n''. Here is a sample computation for ''n'' = 3, showing the data-strings at the beginning of each program-cycle: B/CT step# Collatz term B/CT data-string ----- ------------ ------------------------ 0000 3 100100100 0024 100010001 0048 001010001 0072 001100100100 0096 5 100100100100100 0120 100100100010001 0144 100010001010001 0168 001010001010001 0192 001010001100100100 0216 001100100100100100100 0240 8 100100100100100100100100 0264 100100100100100100010001 0288 100100100100010001010001 0312 100100010001010001010001 0336 010001010001010001010001 0360 010001010001010001100 0384 010001010001100100 0408 010001100100100 0432 4 100100100100 0456 100100010001 0480 010001010001 0504 010001100 0528 2 100100 0552 010001 0576 1 100 0600 001 0624 2 100100 0648 010001 0672 1 100 ... ... ... (The step-numbers are the multiples of 24, because there are 24 commands executed in each program-cycle.) ==Arithmetic interpretation of BCT== The BCT data-string can be interpreted as the unique numeral of a nonnegative integer written in [http://en.wikipedia.org/wiki/bijective_numeration bijective base-2 representation], as follows: {| class="wikitable" |- ! BCT data-string !! Bijective base-2 numeral !! Integer represented |- | b<sub>0</sub> b<sub>1</sub> ... b<sub>k</sub> || (b<sub>k</sub> + 1)(b<sub>k-1</sub> + 1)...(b<sub>0</sub> + 1) || SUM{(b<sub>i</sub> + 1) 2<sup>i</sup>: i = 0..k} |} Note that the digits 1,2 are represented by the bits 0,1 respectively, and the numeral is read in ''reverse'' order from the bit-string. E.g., the BCT data-string 011 corresponds to the bijective base-2 numeral 221, representing the integer <u><b>2</b></u>*2<sup>2</sup> + <u><b>2</b></u>*2<sup>1</sup> + <u><b>1</b></u>*2<sup>0</sup> = 13. Each BCT command in a program then corresponds to an explicit numerical function defined on the set '''N''' of nonnegative integers, as follows: {| class="wikitable" |- ! Command !! Equivalent numerical function (mapping '''N''' to '''N''') |- | 0|| f(n) = [n is positive] * floor((n-1)/2) |- | 10 || g<sub>0</sub>(n) = n + [n is positive and even] * 2<sup>(floor(log<sub>2</sub>(n+1)) + 0)</sup> |- | 11 || g<sub>1</sub>(n) = n + [n is positive and even] * 2<sup>(floor(log<sub>2</sub>(n+1)) + 1)</sup> |} where we've shown separately the two cases for the program-bit that's next after the 1-command. Here [''condition''] is an [http://en.wikipedia.org/wiki/Iverson_bracket Iverson bracket], meaning 1 if ''condition'' is true, else 0; so the integer 0 is a fixed-point of all three of the functions f, g<sub>0</sub>, g<sub>1</sub>, and represents a permanent "halt" condition. (Also note that floor(log<sub>2</sub>(n+1)) is just the number of digits in the bijective base-2 numeral for n.) Thus a BCT program is equivalent to a composition of finitely-many instances of the three functions f, g<sub>0</sub>, g<sub>1</sub>, all but some initial portion of which is iterated. Just as the sequence of successive data-strings encodes all input and output in a BCT computation, in the arithmetic interpretation the same role is fulfilled by the sequence of successive nonnegative integer arguments. ===Gödel numbering=== A [http://en.wikipedia.org/wiki/G%C3%B6del_number Gödel numbering] of BCT programs is automatically provided by similarly interpreting each BCT program as the bijective base-2 numeral of an integer (now in the usual digit-order, unlike the data-string). Thus, <u>a BCT program is (the numeral of) its own Gödel number</u>. E.g., the program 011 is interpreted as the integer 10 (ten = 122 in bijective base-2) &mdash; and indeed 011 is the tenth nonempty BCT program in a [http://en.wikipedia.org/wiki/Shortlex_order shortlex ordering] of the set of all BCT programs. ===Example=== bit-string bij. base-2 decimal ---------- ----------- ------- Program: 110100 221211 115 Initial data: 10 12 4 Execution-trace: data (at beginning of each step) -------------------------------- step# cmd function bit-string bij. base-2 decimal function evaluation ----- ---- -------- ---------- ----------- ------- ------------------- 0001 11 * g<sub>1</sub> 10 12 4 0002 0 f 101 212 12 = g<sub>1</sub>(4) 0003 10 g<sub>0</sub> 01 21 5 = f(12) 0004 0 f 01 21 5 = g<sub>0</sub>(5) 0005 11 * g<sub>1</sub> 1 2 2 = f(5) 0006 0 f 11 22 6 = g<sub>1</sub>(2) 0007 10 g<sub>0</sub> 1 2 2 = f(6) 0008 0 f 10 12 4 = g<sub>0</sub>(2) 0009 11 * g<sub>1</sub> 0 1 1 = f(4) 0010 0 f 0 1 1 = g<sub>1</sub>(1) (halt) - - 0 = f(1) ----- deletion sequence: 10110 An asterisk marks the first command executed in each cycle through the program &mdash; the first function evaluated in each iteration. ==Computations in BCT== It can be shown that for any Turing machine computation, there is a BCT system (program plus data-string) that simulates it &mdash; halting if and only if the TM halts, and encoding the TM's input and output in the sequence of deleted data-bits. This is a consequence of the Turing-completeness of cyclic tag systems, together with the fact that BCT can simulate any cyclic tag system. ==Self BCT== Any string of bits L...R, when read in cyclic sequence (rightward from L, with L next after R), parses into a unique sequence of instructions from the set {0, 10, 11}. Thus, any such string can be interpreted as a self-modifying program whose instructions are executed in cyclic sequence as follows (with labels L/R revised appropriately when a bit is deleted/appended): {| class="wikitable" |- ! Instruction !! Execution |- | 0 || Delete L. |- | 1x || If L > 0: append x to R. |} Program execution halts if and when the program deletes itself. This is essentially BCT, but with the data-string identified with the program-string itself. Example (^ or ^^ indicating the current instruction as 0 or 1x): Step Program-string ----- ---------------------- 00000 1011110111 ^^ 00001 10111101110 ^^ 00002 101111011101 ^^ 00003 1011110111011 ^ 00004 011110111011 ^^ 00005 011110111011 ^^ 00006 011110111011 ^^ 00007 011110111011 ^ 00008 11110111011 ^^ 00009 111101110111 ^^ 00010 1111011101111 ^ 00011 111011101111 ^^ 00012 1110111011111 ^^ 00013 11101110111110 ^^ 00014 111011101111101 ^^ 00015 1110111011111011 ^^ 00016 11101110111110110 ^^ 00017 111011101111101101 ^ 00018 11011101111101101 ^ ^ 00019 110111011111011011 ^^ ... ... 43074 (empty) This language might well be a Turing tarpit, with the 43,074 steps for the program "1011110111" already showing some characteristically rapid growth in the associated uncomputable [https://en.wikipedia.org/wiki/Busy_beaver#Max_shifts_function Radó S-sequence]. '''NB''': Both BCT and Self BCT generalise in obvious ways to languages that process a base-k data-string using k (≥ 2) instructions of the form dX, where d is any base-k digit and X is any base-k digit-string of length d. Thus, the command 0 unconditionally deletes the leftmost data-symbol, and the command dX (with 1 ≤ d ≤ k-1, and X of length d) appends X to the data-string iff the leftmost data-symbol ''is not'' 0 (or, as a variant, iff the leftmost data-symbol ''is'' d). A program would then be any base-k digit-string. ==Authorship== The languages CT and BCT were created by "[[r.e.s.]]" in December 2005. "Self BCT" was created by "r.e.s." in 2005-2006 (posted 2006 in a comp.theory usegroup message, [http://groups.google.com/group/comp.theory/browse_thread/thread/29b22b6fbd89179f/da69c701096e1c6d?hl=en&ie=UTF-8&q=BCT+%22cyclic+tag%22&fwc=1 "Variations on Cyclic Tag"]). ==External resources== * [http://www.73b.org/programs/bct.b Bitwise Cyclic Tag interpreter] written in [[brainfuck]] and [http://yiap.nfshost.com/esoteric/thue/bct.t interpreter] in [[Thue]] (by [[User:Keymaker]]) * [http://oerjan.nvg.org/esoteric/slashes/bct.sss Interpreter] in [[:///]] and [http://oerjan.nvg.org/esoteric/eodermdrome/bct.eode interpreter] in [[Eodermdrome]] (by [[User:Oerjan]]) * [https://github.com/graue/esofiles/tree/master/sortle/src/bct.sort Interpreter] in [[Sortle]] (by [[User:Graue]]) * [https://github.com/Coates-36411/BCT-interpreter Interpreter] in C (by [[User:Coates]]) * [[wikipedia:Tag system#Cyclic tag systems|Cyclic tag systems]] (Wikipedia) [[Category:Languages]] [[Category:Turing complete]] [[Category:Turing tarpits]] [[Category:Queue-based]] [[Category:2005]] [[Category:No IO]] [[Category:Implemented]]'
New page wikitext, after the edit (new_wikitext)
''''Bitwise Cyclic Tag (BCT)''' is a [[Turing-complete]] programming language using only two commands (0 and 1) to operate on a finite data-bitstring extensible without bound on the right. Its extremely simple syntax and semantics make it a useful target for [[Computational_class#Simulation|simulation]]-based proofs of a language's computational class. ==BCT programs== A '''BCT program''' is any finite string of bits (commands), executed as follows: {| class="wikitable" |- ! Command !! Execution |- | 0 || Delete the leftmost data-bit. |- | 1 || Goto the next command (say x). If the leftmost data-bit is 1, copy x to the right end of the data-string. |} If the program-string or the data-string is initially empty, execution halts immediately; otherwise, starting at the leftmost program-bit and halting only when the data-string becomes empty, the commands are executed in cyclic sequence from left to right (the leftmost bit following next after the rightmost bit). The program pointer advances one bit after each command-execution, and also advances one bit when the goto in a 1-command is executed; consequently, a 1-command always pairs with the next command after it (say x), such that 1x is effectively a composite command whose execution is if the leftmost data-bit is 1: copy x to the right end of the data-string Four equivalent variations of BCT are obtained by exchanging the roles of symbols 0 and 1 as commands, and by varying the parity required in the condition for copying a bit to the end of the data-string. ===Example=== Program: 00111 Execution sequence: 00111 (00111) (00111) (00111) ... = 0 (0 11 10) (0 11 10) (0 11 10) ... Initial data-string: 101 System evolution: Commands Data- Executed String -------- ------- 0 101 0 01 11 1 10 11 0 110 11 10 10 101 0 1010 11 010 10 010 0 010 11 10 ... ... ==BCT emulation of cyclic tag systems== For any [[cyclic tag system]] on a binary alphabet, there is a BCT program that emulates it (thus establishing that BCT is Turing-complete, since the set of cyclic tag systems is Turing-complete). Specifically, a BCT program that emulates a given cyclic tag system is obtained by writing the cyclic tag system productions as ';'-terminated strings, concatenating these strings, and then applying the following substitutions: 0 <-- 10 1 <-- 11 ; <-- 0 The initial data-string for the BCT program is the unaltered initial binary word for the cyclic tag system. '''*Note*''': BCT remains Turing complete even if the initial data-string is always just a single '''1'''. This is because, 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 a result in [http://arxiv.org/abs/1312.6700 Undecidability in binary tag systems and the Post correspondence problem for four pairs of words] (Turlough Neary, 2013), to the effect that for any cyclic tag system with initial word '''w''' (say), the same computation is simulated by some cyclic tag system whose initial word is a single '''1'''. ===The language '''CT'''=== BCT was created upon noticing that the operation of a cyclic tag system is exactly duplicated by interpreting the concatenation of its semicolon-terminated productions as a program that uses three commands {'''0''', '''1''', ''';'''} to operate on the current word (interpeted as a data bit-string). Calling this three-instruction language '''CT''', with programs that may be any finite string on {'''0''', '''1''', ''';'''}, the commands of a CT program are executed left-to-right in cyclic sequence, halting only when the data-string becomes empty: {| class="wikitable" |- ! CT Command !! Execution !! Equivalent BCT Command |- | 0 || If the leftmost data-bit is 1, append 0. || 10 |- | 1 || If the leftmost data-bit is 1, append 1. || 11 |- | ; || Delete the leftmost data-bit. || 0 |} The purpose of replacing CT by BCT was merely to obtain a language whose programs are binary (rather than ternary) strings. CT programs that might interest someone: *Program "1", data "1". Creates 'a pyramid of 1s'. *Program ";", data whatever. Removes all data and halts. *A sort of quines: Programs where the data remains forever identical to the initial program (and identical to data -- itself -- too). Any string consisting only of 0s and 1s, and which begins with a 0, suffices. Thus, for example: Program "0", data "0" (this is the shortest one possible). Program "0100111", data "0100111". ===Example (simple illustration)=== This is just to illustrate how things work ... Cyclic tag system Productions: (011, 10, 101) CT program: 011;10;101; Translation to a BCT program 011;10;101; --> 10 11 11 0 11 10 0 11 10 11 0 Initial data-string: 1 System evolution: Commands Executed Data-string -------- ------------- 10 1 11 10 11 101 0 1011 * 11 011 10 011 0 011 * 11 11 10 111 11 1110 0 11101 * 10 1101 11 11010 11 110101 0 1101011 * 11 101011 10 1010111 0 10101110 * 11 0101110 10 0101110 11 0101110 0 0101110 * 10 101110 ... ... The data-strings marked by '*' are those just after each deletion, and are the strings occurring in the evolution of the equivalent cyclic tag system, as follows: Production Data-string ---------- ------------- 011 1 10 011 101 11 011 1101 10 101011 101 0101110 011 101110 ... ... ===Example ([[Collatz sequence]])=== Here are B/CT programs that compute a [[Collatz sequence]] for the Collatz function in the form C(n) = (if n is even then n/2 else (3n+1)/2). Cyclic tag system: (010001, 100, 100100100, e, e, e) (where e is the empty word) CT program: 010001;100;100100100;;;; BCT program: 10 11 10 10 10 11 0 11 10 10 0 11 10 10 11 10 10 11 10 10 0 0 0 0 Initial data-string: (100)<sup>''n''</sup> (''n'' concatenated copies of '100', where ''n'' is a postive integer) In the computation, when (and only when) the data-string takes the form (100)<sup>''k''</sup> immediately before beginning a cycle through the program, it represents the integer ''k'' -- and these will be the successive terms of the Collatz sequence for ''n''. Here is a sample computation for ''n'' = 3, showing the data-strings at the beginning of each program-cycle: B/CT step# Collatz term B/CT data-string ----- ------------ ------------------------ 0000 3 100100100 0024 100010001 0048 001010001 0072 001100100100 0096 5 100100100100100 0120 100100100010001 0144 100010001010001 0168 001010001010001 0192 001010001100100100 0216 001100100100100100100 0240 8 100100100100100100100100 0264 100100100100100100010001 0288 100100100100010001010001 0312 100100010001010001010001 0336 010001010001010001010001 0360 010001010001010001100 0384 010001010001100100 0408 010001100100100 0432 4 100100100100 0456 100100010001 0480 010001010001 0504 010001100 0528 2 100100 0552 010001 0576 1 100 0600 001 0624 2 100100 0648 010001 0672 1 100 ... ... ... (The step-numbers are the multiples of 24, because there are 24 commands executed in each program-cycle.) ==Arithmetic interpretation of BCT== The BCT data-string can be interpreted as the unique numeral of a nonnegative integer written in [http://en.wikipedia.org/wiki/bijective_numeration bijective base-2 representation], as follows: {| class="wikitable" |- ! BCT data-string !! Bijective base-2 numeral !! Integer represented |- | b₀ b₁ ... bₖ || (bₖ + 1)(bₖ₋₁ + 1)...(b₀ + 1) || SUM{(bᵢ + 1) 2ⁱ: i = 0..k} |} Note that the digits 1,2 are represented by the bits 0,1 respectively, and the numeral is read in ''reverse'' order from the bit-string. E.g., the BCT data-string 011 corresponds to the bijective base-2 numeral 221, representing the integer <u><b>2</b></u>*2² + <u><b>2</b></u>*2¹ + <u><b>1</b></u>*2⁰ = 13. Each BCT command in a program then corresponds to an explicit numerical function defined on the set '''N''' of nonnegative integers, as follows: {| class="wikitable" |- ! Command !! Equivalent numerical function (mapping '''N''' to '''N''') |- | 0|| f(n) = [n is positive] * floor((n-1)/2) |- | 10 || g₀(n) = n + [n is positive and even] * 2⁽ᶠˡᵒᵒʳ⁽ˡᵒᵍ-²⁽ⁿ⁺¹⁾⁾ ⁺ ⁰⁾ |- | 11 || g₁(n) = n + [n is positive and even] * 2⁽ᶠˡᵒᵒʳ⁽ˡᵒᵍ-²⁽ⁿ⁺¹⁾⁾ ⁺ ¹⁾ |} where we've shown separately the two cases for the program-bit that's next after the 1-command. Here [''condition''] is an [http://en.wikipedia.org/wiki/Iverson_bracket Iverson bracket], meaning 1 if ''condition'' is true, else 0; so the integer 0 is a fixed-point of all three of the functions f, g₀, g₁, and represents a permanent "halt" condition. (Also note that floor(log₂(n+1)) is just the number of digits in the bijective base-2 numeral for n.) Thus a BCT program is equivalent to a composition of finitely-many instances of the three functions f, g₀, g₁, all but some initial portion of which is iterated. Just as the sequence of successive data-strings encodes all input and output in a BCT computation, in the arithmetic interpretation the same role is fulfilled by the sequence of successive nonnegative integer arguments. ===Gödel numbering=== A [http://en.wikipedia.org/wiki/G%C3%B6del_number Gödel numbering] of BCT programs is automatically provided by similarly interpreting each BCT program as the bijective base-2 numeral of an integer (now in the usual digit-order, unlike the data-string). Thus, <u>a BCT program is (the numeral of) its own Gödel number</u>. E.g., the program 011 is interpreted as the integer 10 (ten = 122 in bijective base-2) &mdash; and indeed 011 is the tenth nonempty BCT program in a [http://en.wikipedia.org/wiki/Shortlex_order shortlex ordering] of the set of all BCT programs. ===Example=== bit-string bij. base-2 decimal ---------- ----------- ------- Program: 110100 221211 115 Initial data: 10 12 4 Execution-trace: data (at beginning of each step) -------------------------------- step# cmd function bit-string bij. base-2 decimal function evaluation ----- ---- -------- ---------- ----------- ------- ------------------- 0001 11 * g₁ 10 12 4 0002 0 f 101 212 12 = g₁(4) 0003 10 g₀ 01 21 5 = f(12) 0004 0 f 01 21 5 = g₀(5) 0005 11 * g₁ 1 2 2 = f(5) 0006 0 f 11 22 6 = g₁(2) 0007 10 g₀ 1 2 2 = f(6) 0008 0 f 10 12 4 = g₀(2) 0009 11 * g₁ 0 1 1 = f(4) 0010 0 f 0 1 1 = g₁(1) (halt) - - 0 = f(1) ----- deletion sequence: 10110 An asterisk marks the first command executed in each cycle through the program &mdash; the first function evaluated in each iteration. ==Computations in BCT== It can be shown that for any Turing machine computation, there is a BCT system (program plus data-string) that simulates it &mdash; halting if and only if the TM halts, and encoding the TM's input and output in the sequence of deleted data-bits. This is a consequence of the Turing-completeness of cyclic tag systems, together with the fact that BCT can simulate any cyclic tag system. ==Self BCT== Any string of bits L...R, when read in cyclic sequence (rightward from L, with L next after R), parses into a unique sequence of instructions from the set {0, 10, 11}. Thus, any such string can be interpreted as a self-modifying program whose instructions are executed in cyclic sequence as follows (with labels L/R revised appropriately when a bit is deleted/appended): {| class="wikitable" |- ! Instruction !! Execution |- | 0 || Delete L. |- | 1x || If L > 0: append x to R. |} Program execution halts if and when the program deletes itself. This is essentially BCT, but with the data-string identified with the program-string itself. Example (^ or ^^ indicating the current instruction as 0 or 1x): Step Program-string ----- ---------------------- 00000 1011110111 ^^ 00001 10111101110 ^^ 00002 101111011101 ^^ 00003 1011110111011 ^ 00004 011110111011 ^^ 00005 011110111011 ^^ 00006 011110111011 ^^ 00007 011110111011 ^ 00008 11110111011 ^^ 00009 111101110111 ^^ 00010 1111011101111 ^ 00011 111011101111 ^^ 00012 1110111011111 ^^ 00013 11101110111110 ^^ 00014 111011101111101 ^^ 00015 1110111011111011 ^^ 00016 11101110111110110 ^^ 00017 111011101111101101 ^ 00018 11011101111101101 ^ ^ 00019 110111011111011011 ^^ ... ... 43074 (empty) This language might well be a Turing tarpit, with the 43,074 steps for the program "1011110111" already showing some characteristically rapid growth in the associated uncomputable [https://en.wikipedia.org/wiki/Busy_beaver#Max_shifts_function Radó S-sequence]. '''NB''': Both BCT and Self BCT generalise in obvious ways to languages that process a base-k data-string using k (≥ 2) instructions of the form dX, where d is any base-k digit and X is any base-k digit-string of length d. Thus, the command 0 unconditionally deletes the leftmost data-symbol, and the command dX (with 1 ≤ d ≤ k-1, and X of length d) appends X to the data-string iff the leftmost data-symbol ''is not'' 0 (or, as a variant, iff the leftmost data-symbol ''is'' d). A program would then be any base-k digit-string. ==Authorship== The languages CT and BCT were created by "[[r.e.s.]]" in December 2005. "Self BCT" was created by "r.e.s." in 2005-2006 (posted 2006 in a comp.theory usegroup message, [http://groups.google.com/group/comp.theory/browse_thread/thread/29b22b6fbd89179f/da69c701096e1c6d?hl=en&ie=UTF-8&q=BCT+%22cyclic+tag%22&fwc=1 "Variations on Cyclic Tag"]). ==External resources== * [http://www.73b.org/programs/bct.b Bitwise Cyclic Tag interpreter] written in [[brainfuck]] and [http://yiap.nfshost.com/esoteric/thue/bct.t interpreter] in [[Thue]] (by [[User:Keymaker]]) * [http://oerjan.nvg.org/esoteric/slashes/bct.sss Interpreter] in [[:///]] and [http://oerjan.nvg.org/esoteric/eodermdrome/bct.eode interpreter] in [[Eodermdrome]] (by [[User:Oerjan]]) * [https://github.com/graue/esofiles/tree/master/sortle/src/bct.sort Interpreter] in [[Sortle]] (by [[User:Graue]]) * [https://github.com/Coates-36411/BCT-interpreter Interpreter] in C (by [[User:Coates]]) * [[wikipedia:Tag system#Cyclic tag systems|Cyclic tag systems]] (Wikipedia) [[Category:Languages]] [[Category:Turing complete]] [[Category:Turing tarpits]] [[Category:Queue-based]] [[Category:2005]] [[Category:No IO]] [[Category:Implemented]]'
Unified diff of changes made by edit (edit_diff)
'@@ -199,8 +199,8 @@ ! BCT data-string !! Bijective base-2 numeral !! Integer represented |- -| b<sub>0</sub> b<sub>1</sub> ... b<sub>k</sub> || (b<sub>k</sub> + 1)(b<sub>k-1</sub> + 1)...(b<sub>0</sub> + 1) || SUM{(b<sub>i</sub> + 1) 2<sup>i</sup>: i = 0..k} +| b₀ b₁ ... bₖ || (bₖ + 1)(bₖ₋₁ + 1)...(b₀ + 1) || SUM{(bᵢ + 1) 2ⁱ: i = 0..k} |} -Note that the digits 1,2 are represented by the bits 0,1 respectively, and the numeral is read in ''reverse'' order from the bit-string. E.g., the BCT data-string 011 corresponds to the bijective base-2 numeral 221, representing the integer <u><b>2</b></u>*2<sup>2</sup> + <u><b>2</b></u>*2<sup>1</sup> + <u><b>1</b></u>*2<sup>0</sup> = 13. +Note that the digits 1,2 are represented by the bits 0,1 respectively, and the numeral is read in ''reverse'' order from the bit-string. E.g., the BCT data-string 011 corresponds to the bijective base-2 numeral 221, representing the integer <u><b>2</b></u>*2² + <u><b>2</b></u>*2¹ + <u><b>1</b></u>*2⁰ = 13. Each BCT command in a program then corresponds to an explicit numerical function defined on the set '''N''' of nonnegative integers, as follows: @@ -212,16 +212,16 @@ | 0|| f(n) = [n is positive] * floor((n-1)/2) |- -| 10 || g<sub>0</sub>(n) = n + [n is positive and even] * 2<sup>(floor(log<sub>2</sub>(n+1)) + 0)</sup> +| 10 || g₀(n) = n + [n is positive and even] * 2⁽ᶠˡᵒᵒʳ⁽ˡᵒᵍ-²⁽ⁿ⁺¹⁾⁾ ⁺ ⁰⁾ |- -| 11 || g<sub>1</sub>(n) = n + [n is positive and even] * 2<sup>(floor(log<sub>2</sub>(n+1)) + 1)</sup> +| 11 || g₁(n) = n + [n is positive and even] * 2⁽ᶠˡᵒᵒʳ⁽ˡᵒᵍ-²⁽ⁿ⁺¹⁾⁾ ⁺ ¹⁾ |} -where we've shown separately the two cases for the program-bit that's next after the 1-command. Here [''condition''] is an [http://en.wikipedia.org/wiki/Iverson_bracket Iverson bracket], meaning 1 if ''condition'' is true, else 0; so the integer 0 is a fixed-point of all three of the functions f, g<sub>0</sub>, g<sub>1</sub>, and represents a permanent "halt" condition. (Also note that floor(log<sub>2</sub>(n+1)) is just the number of digits in the bijective base-2 numeral for n.) +where we've shown separately the two cases for the program-bit that's next after the 1-command. Here [''condition''] is an [http://en.wikipedia.org/wiki/Iverson_bracket Iverson bracket], meaning 1 if ''condition'' is true, else 0; so the integer 0 is a fixed-point of all three of the functions f, g₀, g₁, and represents a permanent "halt" condition. (Also note that floor(log₂(n+1)) is just the number of digits in the bijective base-2 numeral for n.) -Thus a BCT program is equivalent to a composition of finitely-many instances of the three functions f, g<sub>0</sub>, g<sub>1</sub>, all but some initial portion of which is iterated. Just as the sequence of successive data-strings encodes all input and output in a BCT computation, in the arithmetic interpretation the same role is fulfilled by the sequence of successive nonnegative integer arguments. +Thus a BCT program is equivalent to a composition of finitely-many instances of the three functions f, g₀, g₁, all but some initial portion of which is iterated. Just as the sequence of successive data-strings encodes all input and output in a BCT computation, in the arithmetic interpretation the same role is fulfilled by the sequence of successive nonnegative integer arguments. ===Gödel numbering=== -A [http://en.wikipedia.org/wiki/G%C3%B6del_number Gödel numbering] of BCT programs is automatically provided by similarly interpreting each BCT program as the bijective base-2 numeral of an integer (now in the usual digit-order, unlike the data-string). Thus, <u>a BCT program is (the numeral of) its own Gödel number</u>. E.g., the program 011 is interpreted as the integer 10 (ten = 122 in bijective base-2) &mdash; and indeed 011 is the tenth nonempty BCT program in a [http://en.wikipedia.org/wiki/Shortlex_order shortlex ordering] of the set of all BCT programs. +A [http://en.wikipedia.org/wiki/G%C3%B6del_number Gödel numbering] of BCT programs is automatically provided by similarly interpreting each BCT program as the bijective base-2 numeral of an integer (now in the usual digit-order, unlike the data-string). Thus, <u>a BCT program is (the numeral of) its own Gödel number</u>. E.g., the program 011 is interpreted as the integer 10 (ten = 122 in bijective base-2) &mdash; and indeed 011 is the tenth nonempty BCT program in a [http://en.wikipedia.org/wiki/Shortlex_order shortlex ordering] of the set of all BCT programs. ===Example=== @@ -238,23 +238,23 @@ step# cmd function bit-string bij. base-2 decimal function evaluation ----- ---- -------- ---------- ----------- ------- ------------------- - 0001 11 * g<sub>1</sub> 10 12 4 + 0001 11 * g₁ 10 12 4 - 0002 0 f 101 212 12 = g<sub>1</sub>(4) + 0002 0 f 101 212 12 = g₁(4) - 0003 10 g<sub>0</sub> 01 21 5 = f(12) + 0003 10 g₀ 01 21 5 = f(12) - 0004 0 f 01 21 5 = g<sub>0</sub>(5) + 0004 0 f 01 21 5 = g₀(5) - 0005 11 * g<sub>1</sub> 1 2 2 = f(5) + 0005 11 * g₁ 1 2 2 = f(5) - 0006 0 f 11 22 6 = g<sub>1</sub>(2) + 0006 0 f 11 22 6 = g₁(2) - 0007 10 g<sub>0</sub> 1 2 2 = f(6) + 0007 10 g₀ 1 2 2 = f(6) - 0008 0 f 10 12 4 = g<sub>0</sub>(2) + 0008 0 f 10 12 4 = g₀(2) - 0009 11 * g<sub>1</sub> 0 1 1 = f(4) + 0009 11 * g₁ 0 1 1 = f(4) - 0010 0 f 0 1 1 = g<sub>1</sub>(1) + 0010 0 f 0 1 1 = g₁(1) (halt) - - 0 = f(1) '
New page size (new_size)
16508
Old page size (old_size)
16739
Lines added in edit (added_lines)
[ 0 => '| b₀ b₁ ... bₖ || (bₖ + 1)(bₖ₋₁ + 1)...(b₀ + 1) || SUM{(bᵢ + 1) 2ⁱ: i = 0..k}', 1 => 'Note that the digits 1,2 are represented by the bits 0,1 respectively, and the numeral is read in ''reverse'' order from the bit-string. E.g., the BCT data-string 011 corresponds to the bijective base-2 numeral 221, representing the integer <u><b>2</b></u>*2² + <u><b>2</b></u>*2¹ + <u><b>1</b></u>*2⁰ = 13.', 2 => '| 10 || g₀(n) = n + [n is positive and even] * 2⁽ᶠˡᵒᵒʳ⁽ˡᵒᵍ-²⁽ⁿ⁺¹⁾⁾ ⁺ ⁰⁾', 3 => '| 11 || g₁(n) = n + [n is positive and even] * 2⁽ᶠˡᵒᵒʳ⁽ˡᵒᵍ-²⁽ⁿ⁺¹⁾⁾ ⁺ ¹⁾', 4 => 'where we've shown separately the two cases for the program-bit that's next after the 1-command. Here [''condition''] is an [http://en.wikipedia.org/wiki/Iverson_bracket Iverson bracket], meaning 1 if ''condition'' is true, else 0; so the integer 0 is a fixed-point of all three of the functions f, g₀, g₁, and represents a permanent "halt" condition. (Also note that floor(log₂(n+1)) is just the number of digits in the bijective base-2 numeral for n.) ', 5 => 'Thus a BCT program is equivalent to a composition of finitely-many instances of the three functions f, g₀, g₁, all but some initial portion of which is iterated. Just as the sequence of successive data-strings encodes all input and output in a BCT computation, in the arithmetic interpretation the same role is fulfilled by the sequence of successive nonnegative integer arguments.', 6 => 'A [http://en.wikipedia.org/wiki/G%C3%B6del_number Gödel numbering] of BCT programs is automatically provided by similarly interpreting each BCT program as the bijective base-2 numeral of an integer (now in the usual digit-order, unlike the data-string). Thus, <u>a BCT program is (the numeral of) its own Gödel number</u>. E.g., the program 011 is interpreted as the integer 10 (ten = 122 in bijective base-2) &mdash; and indeed 011 is the tenth nonempty BCT program in a [http://en.wikipedia.org/wiki/Shortlex_order shortlex ordering] of the set of all BCT programs.', 7 => ' 0001 11 * g₁ 10 12 4 ', 8 => ' 0002 0 f 101 212 12 = g₁(4)', 9 => ' 0003 10 g₀ 01 21 5 = f(12)', 10 => ' 0004 0 f 01 21 5 = g₀(5)', 11 => ' 0005 11 * g₁ 1 2 2 = f(5)', 12 => ' 0006 0 f 11 22 6 = g₁(2)', 13 => ' 0007 10 g₀ 1 2 2 = f(6)', 14 => ' 0008 0 f 10 12 4 = g₀(2)', 15 => ' 0009 11 * g₁ 0 1 1 = f(4)', 16 => ' 0010 0 f 0 1 1 = g₁(1)' ]
Unix timestamp of change (timestamp)
1522507482