Brainfuck minus -
The article Brainfuck derivatives with nontrivial computational class proofs mentioned Permanent Brainfuck, a variation of brainfuck without the '-' instruction (and with unbounded cells). I (Keymaker) thought that ordinary brainfuck ought to be Turing-complete without '-' even with the ordinary cells -- and this is what I will show here, with the addition of making the system only use memory values 0 and 1: '+' never happens twice in the same cell.
So, this is not a brainfuck derivative, this is merely a way for programming brainfuck without using '-'.
Here is a translator in Python for translating Sequential tag system (and Cyclic tag system, this works for both) to brainfuck code that obeys the restrictions mentioned above. Use only programs that do not halt.
m = "1" # initial memory string
p = "011;10;101;" # program string
s = ">>> "
for x in m:
s = s + "+>>"
if x == "1":
s = s + "+"
s = s + "> "
s = s + "<<<[<<<]>>>"
print(s)
print("[")
for x in p:
if x == ";":
print(" >[>>>]+<[<<<]>>>")
elif x == "0":
print(" >[>>>]>[>[>>>]+>>]<<[<<<]>>>")
elif x == "1":
print(" >[>>>]>[>[>>>]+>>+>>>]<<<<<[<<<]>>>")
print("]")
Running the program above, loaded with the initial memory string "1" and the program string "011;10;101;", produces the following brainfuck program:
>>> +>>+> <<<[<<<]>>> [ >[>>>]>[>[>>>]+>>]<<[<<<]>>> >[>>>]>[>[>>>]+>>+>>>]<<<<<[<<<]>>> >[>>>]>[>[>>>]+>>+>>>]<<<<<[<<<]>>> >[>>>]+<[<<<]>>> >[>>>]>[>[>>>]+>>+>>>]<<<<<[<<<]>>> >[>>>]>[>[>>>]+>>]<<[<<<]>>> >[>>>]+<[<<<]>>> >[>>>]>[>[>>>]+>>+>>>]<<<<<[<<<]>>> >[>>>]>[>[>>>]+>>]<<[<<<]>>> >[>>>]>[>[>>>]+>>+>>>]<<<<<[<<<]>>> >[>>>]+<[<<<]>>> ]
By adding a debug character (assuming the brainfuck implementation has one) at the end of each instruction's simulation, one can observe the simulated memory string. For example like this:
>[>>>]>[>[>>>]+>>]<<[<<<]>>> ?
The '?' was placed at the end of the first instruction ('0'). It makes sense to add it to them all (or modify the translator to do the work automatically).
So, how to interpret state of the brainfuck memory? Running the above program, this state happens eventually:
000111110111111101100101100101101101000...
Split it in groups of three digits, like this:
000 111 110 111 111 101 100 101 100 101 101 101 000 ...
The simulated memory string uses three brainfuck cells per one digit.
000 xuv xuv xuv 000 ...
The first three cells are kept zero. Then follows the simulated string:
- x - marks the existence of a digit, always 1 (in case there is a digit)
- u - marks whether the digit is in use/exists as part of the memory string. 0 means it is there, 1 means it has been erased by the ';' instruction
- v - marks the value of the digit - 0 or 1
After the string the memory continues as nothing but zeroes -- as it does in brainfuck.
Reading the string of our example:
- 000 - zeroes before the actual string
- 111 - the first piece of actual string data. Since the 'u' cell is 1, it means this 1-digit has been removed from the simulation by the ';' instruction
- 110 - likewise, this 0-digit has been removed from the string by ';'
- 111 - removed 1-digit
- 111 - removed 1-digit
- 101 - notice the 'u' cell is 0. This is the first actual digit (1, the 'v' being 1) in the simulated memory string.
- 100 - second digit. 'u' will be 0 till the end of the string from its first occurrence. This digit is 0
- 101 - 1
- 100 - 0
- 101 - 1
- 101 - 1
- 101 - the last digit in the string
- 000 - the string has ended. The 'x' cell is 0; there is no more string data.
That's it. This shows that brainfuck is Turing-complete without '-', even with the cell range of 0-1.
What about Hao Wang's B-machine?
Seeing the above, one might think that it might be easy to translate to Hao Wang's B-machine (see Wang program). After all, B-machine has a tape, instructions for left and right, instruction to mark the tape, and a conditional jump if the current cell/tape-square is marked. Below is a translator in Python that one may use to translate brainfuck programs that use cell range 0-1 and no '-' and '+' only once per cell, to B-machine, the output represented as a collection of ordered pairs.
import sys
if len(sys.argv) < 2:
print("Error, need an input file.")
sys.exit()
try:
f = open(sys.argv[1])
except IOError:
print("Error in reading the file.")
sys.exit()
a = f.read()
f.close()
p = ""
for x in a:
if x == "+" or x == "<" or x == ">" or x == "[" or x == "]":
p = p + x
s = []
i = []
x = 0
while x < len(p):
if p[x] == "+":
i.append("*")
elif p[x] == ">":
i.append("->")
i.append("->")
elif p[x] == "<":
i.append("<-")
i.append("<-")
elif p[x] == "[":
s.append(len(i) - 1)
i.append("N" + str(len(i) + 6))
i.append("->");
i.append("?")
i.append("*")
i.append("?")
elif p[x] == "]":
q = s.pop()
n = len(i) - 1
i.append("N" + str(q + 7))
i.append("->")
i.append("<-")
i[q + 3] = "N" + str(n + 4)
i[q + 5] = "N" + str(n + 4)
x = x + 1
o = "{"
x = 0
while x < len(i):
o = o + "(" + str(x + 1) + "," + i[x]+ ")"
x = x + 1
print(o + "}")
Since I was unable to find out whether B-machine allows 'over-writing' an already marked cell, my translation might have unnecessary complexity because when it needs to mark the tape it first checks if the tape is already marked and does a jump over the operation if it is.
All the STS/CTS-to-brainfuck translations made with the method above can be translated to B-machine with the above program. Here is the example program in B-machine:
{(1,->)(2,->)(3,->)(4,->)(5,->)(6,->)(7,*)(8,->)(9,->)(10,->)(11,->)(12,*)(13,->)(14,->)(15,<-)(16,<-)(17,<-)(18,<-)(19,<-)(20,<-)(21,N26)(22,->)(23,N34)(24,*)(25,N34)(26,<-)(27,<-)(28,<-)(29,<-)(30,<-)(31,<-)(32,N26)(33,->)(34,<-)(35,->)(36,->)(37,->)(38,->)(39,->)(40,->)(41,N46)(42,->)(43,N798)(44,*)(45,N798)(46,->)(47,->)(48,N53)(49,->)(50,N61)(51,*)(52,N61)(53,->)(54,->)(55,->)(56,->)(57,->)(58,->)(59,N53)(60,->)(61,<-)(62,->)(63,->)(64,N69)(65,->)(66,N92)(67,*)(68,N92)(69,->)(70,->)(71,N76)(72,->)(73,N84)(74,*)(75,N84)(76,->)(77,->)(78,->)(79,->)(80,->)(81,->)(82,N76)(83,->)(84,<-)(85,*)(86,->)(87,->)(88,->)(89,->)(90,N69)(91,->)(92,<-)(93,<-)(94,<-)(95,<-)(96,<-)(97,N102)(98,->)(99,N110)(100,*)(101,N110)(102,<-)(103,<-)(104,<-)(105,<-)(106,<-)(107,<-)(108,N102)(109,->)(110,<-)(111,->)(112,->)(113,->)(114,->)(115,->)(116,->)(117,->)(118,->)(119,N124)(120,->)(121,N132)(122,*)(123,N132)(124,->)(125,->)(126,->)(127,->)(128,->)(129,->)(130,N124)(131,->)(132,<-)(133,->)(134,->)(135,N140)(136,->)(137,N170)(138,*)(139,N170)(140,->)(141,->)(142,N147)(143,->)(144,N155)(145,*)(146,N155)(147,->)(148,->)(149,->)(150,->)(151,->)(152,->)(153,N147)(154,->)(155,<-)(156,*)(157,->)(158,->)(159,->)(160,->)(161,*)(162,->)(163,->)(164,->)(165,->)(166,->)(167,->)(168,N140)(169,->)(170,<-)(171,<-)(172,<-)(173,<-)(174,<-)(175,<-)(176,<-)(177,<-)(178,<-)(179,<-)(180,<-)(181,N186)(182,->)(183,N194)(184,*)(185,N194)(186,<-)(187,<-)(188,<-)(189,<-)(190,<-)(191,<-)(192,N186)(193,->)(194,<-)(195,->)(196,->)(197,->)(198,->)(199,->)(200,->)(201,->)(202,->)(203,N208)(204,->)(205,N216)(206,*)(207,N216)(208,->)(209,->)(210,->)(211,->)(212,->)(213,->)(214,N208)(215,->)(216,<-)(217,->)(218,->)(219,N224)(220,->)(221,N254)(222,*)(223,N254)(224,->)(225,->)(226,N231)(227,->)(228,N239)(229,*)(230,N239)(231,->)(232,->)(233,->)(234,->)(235,->)(236,->)(237,N231)(238,->)(239,<-)(240,*)(241,->)(242,->)(243,->)(244,->)(245,*)(246,->)(247,->)(248,->)(249,->)(250,->)(251,->)(252,N224)(253,->)(254,<-)(255,<-)(256,<-)(257,<-)(258,<-)(259,<-)(260,<-)(261,<-)(262,<-)(263,<-)(264,<-)(265,N270)(266,->)(267,N278)(268,*)(269,N278)(270,<-)(271,<-)(272,<-)(273,<-)(274,<-)(275,<-)(276,N270)(277,->)(278,<-)(279,->)(280,->)(281,->)(282,->)(283,->)(284,->)(285,->)(286,->)(287,N292)(288,->)(289,N300)(290,*)(291,N300)(292,->)(293,->)(294,->)(295,->)(296,->)(297,->)(298,N292)(299,->)(300,<-)(301,*)(302,<-)(303,<-)(304,N309)(305,->)(306,N317)(307,*)(308,N317)(309,<-)(310,<-)(311,<-)(312,<-)(313,<-)(314,<-)(315,N309)(316,->)(317,<-)(318,->)(319,->)(320,->)(321,->)(322,->)(323,->)(324,->)(325,->)(326,N331)(327,->)(328,N339)(329,*)(330,N339)(331,->)(332,->)(333,->)(334,->)(335,->)(336,->)(337,N331)(338,->)(339,<-)(340,->)(341,->)(342,N347)(343,->)(344,N377)(345,*)(346,N377)(347,->)(348,->)(349,N354)(350,->)(351,N362)(352,*)(353,N362)(354,->)(355,->)(356,->)(357,->)(358,->)(359,->)(360,N354)(361,->)(362,<-)(363,*)(364,->)(365,->)(366,->)(367,->)(368,*)(369,->)(370,->)(371,->)(372,->)(373,->)(374,->)(375,N347)(376,->)(377,<-)(378,<-)(379,<-)(380,<-)(381,<-)(382,<-)(383,<-)(384,<-)(385,<-)(386,<-)(387,<-)(388,N393)(389,->)(390,N401)(391,*)(392,N401)(393,<-)(394,<-)(395,<-)(396,<-)(397,<-)(398,<-)(399,N393)(400,->)(401,<-)(402,->)(403,->)(404,->)(405,->)(406,->)(407,->)(408,->)(409,->)(410,N415)(411,->)(412,N423)(413,*)(414,N423)(415,->)(416,->)(417,->)(418,->)(419,->)(420,->)(421,N415)(422,->)(423,<-)(424,->)(425,->)(426,N431)(427,->)(428,N454)(429,*)(430,N454)(431,->)(432,->)(433,N438)(434,->)(435,N446)(436,*)(437,N446)(438,->)(439,->)(440,->)(441,->)(442,->)(443,->)(444,N438)(445,->)(446,<-)(447,*)(448,->)(449,->)(450,->)(451,->)(452,N431)(453,->)(454,<-)(455,<-)(456,<-)(457,<-)(458,<-)(459,N464)(460,->)(461,N472)(462,*)(463,N472)(464,<-)(465,<-)(466,<-)(467,<-)(468,<-)(469,<-)(470,N464)(471,->)(472,<-)(473,->)(474,->)(475,->)(476,->)(477,->)(478,->)(479,->)(480,->)(481,N486)(482,->)(483,N494)(484,*)(485,N494)(486,->)(487,->)(488,->)(489,->)(490,->)(491,->)(492,N486)(493,->)(494,<-)(495,*)(496,<-)(497,<-)(498,N503)(499,->)(500,N511)(501,*)(502,N511)(503,<-)(504,<-)(505,<-)(506,<-)(507,<-)(508,<-)(509,N503)(510,->)(511,<-)(512,->)(513,->)(514,->)(515,->)(516,->)(517,->)(518,->)(519,->)(520,N525)(521,->)(522,N533)(523,*)(524,N533)(525,->)(526,->)(527,->)(528,->)(529,->)(530,->)(531,N525)(532,->)(533,<-)(534,->)(535,->)(536,N541)(537,->)(538,N571)(539,*)(540,N571)(541,->)(542,->)(543,N548)(544,->)(545,N556)(546,*)(547,N556)(548,->)(549,->)(550,->)(551,->)(552,->)(553,->)(554,N548)(555,->)(556,<-)(557,*)(558,->)(559,->)(560,->)(561,->)(562,*)(563,->)(564,->)(565,->)(566,->)(567,->)(568,->)(569,N541)(570,->)(571,<-)(572,<-)(573,<-)(574,<-)(575,<-)(576,<-)(577,<-)(578,<-)(579,<-)(580,<-)(581,<-)(582,N587)(583,->)(584,N595)(585,*)(586,N595)(587,<-)(588,<-)(589,<-)(590,<-)(591,<-)(592,<-)(593,N587)(594,->)(595,<-)(596,->)(597,->)(598,->)(599,->)(600,->)(601,->)(602,->)(603,->)(604,N609)(605,->)(606,N617)(607,*)(608,N617)(609,->)(610,->)(611,->)(612,->)(613,->)(614,->)(615,N609)(616,->)(617,<-)(618,->)(619,->)(620,N625)(621,->)(622,N648)(623,*)(624,N648)(625,->)(626,->)(627,N632)(628,->)(629,N640)(630,*)(631,N640)(632,->)(633,->)(634,->)(635,->)(636,->)(637,->)(638,N632)(639,->)(640,<-)(641,*)(642,->)(643,->)(644,->)(645,->)(646,N625)(647,->)(648,<-)(649,<-)(650,<-)(651,<-)(652,<-)(653,N658)(654,->)(655,N666)(656,*)(657,N666)(658,<-)(659,<-)(660,<-)(661,<-)(662,<-)(663,<-)(664,N658)(665,->)(666,<-)(667,->)(668,->)(669,->)(670,->)(671,->)(672,->)(673,->)(674,->)(675,N680)(676,->)(677,N688)(678,*)(679,N688)(680,->)(681,->)(682,->)(683,->)(684,->)(685,->)(686,N680)(687,->)(688,<-)(689,->)(690,->)(691,N696)(692,->)(693,N726)(694,*)(695,N726)(696,->)(697,->)(698,N703)(699,->)(700,N711)(701,*)(702,N711)(703,->)(704,->)(705,->)(706,->)(707,->)(708,->)(709,N703)(710,->)(711,<-)(712,*)(713,->)(714,->)(715,->)(716,->)(717,*)(718,->)(719,->)(720,->)(721,->)(722,->)(723,->)(724,N696)(725,->)(726,<-)(727,<-)(728,<-)(729,<-)(730,<-)(731,<-)(732,<-)(733,<-)(734,<-)(735,<-)(736,<-)(737,N742)(738,->)(739,N750)(740,*)(741,N750)(742,<-)(743,<-)(744,<-)(745,<-)(746,<-)(747,<-)(748,N742)(749,->)(750,<-)(751,->)(752,->)(753,->)(754,->)(755,->)(756,->)(757,->)(758,->)(759,N764)(760,->)(761,N772)(762,*)(763,N772)(764,->)(765,->)(766,->)(767,->)(768,->)(769,->)(770,N764)(771,->)(772,<-)(773,*)(774,<-)(775,<-)(776,N781)(777,->)(778,N789)(779,*)(780,N789)(781,<-)(782,<-)(783,<-)(784,<-)(785,<-)(786,<-)(787,N781)(788,->)(789,<-)(790,->)(791,->)(792,->)(793,->)(794,->)(795,->)(796,N46)(797,->)(798,<-)}
Depth two nesting
The following substitutions implement a Turing complete one-dimensional subset of Home Row. This shows that brainfuck is Turing complete with the above restrictions as well as only two levels of loop nesting.
The five registers ("spots") of the Home Row grid row are represented as values in unary, interleaved on the tape. Each unary digit is represented in a way adapted from the above tag system representation.
The brainfuck tape splits into groups of three digits, which themselves are parts of groups of fifteen. Each group of fifteen contains one group of three for each encoded spot.
000 000 000 000 000 xuv xuv xuv xuv xuv ...
- x - marks whether the current spot has reached this far on the tape.
- u - marks whether the current digit has been erased (decrementing the spot).
- v - always zero, used to help navigating the tape.
Each spot's cross section of the tape (every fifth group of three) is thus of the form:
000 - initial zeros at left of tape (110)* - deleted unary digits (100)* - live digits (000)* - unending zeros to the right of tape
The number of 100 groups give the current value of the spot. To avoid corner cases in the code, all spots are initialized with one 110 group representing a pre-deleted digit.
Command substitutions
Commands start executing at the first nonzero x (in 110) of the current spot.
Initialization >>> >>> >>> >>> >>> +>+>> +>+>> +>+>> +>+>> +>+< s (decrement spot, decrementing zero is undefined behavior) > [>>> >>> >>> >>> >>>] + [<<< <<< <<< <<< <<<] >>> >>> >>> >>> >> a (increment spot) [>>> >>> >>> >>> >>>] + [<<< <<< <<< <<< <<<] >>> >>> >>> >>> >>> f (move to next spot (using previous on tape)) <<< [<<< <<< <<< <<< <<<] >>> >>> >>> >>> >>> jf (move to next spot if current spot is non-zero) [>>> >>> >>> >>> >>>] <<< <<< <<< <<< << [>] < [<<< <<< <<< <<< <<<] >>> >>> >>> >>> >>> > [<] < [<<< <<< <<< <<< <<<] >>> >>> >>> >>> >> l (loop when non-zero, * is [ for odd-numbered l and ] for even-numbered l) [>>> >>> >>> >>> >>>] <<< <<< <<< <<< << [>] < [<<< <<< <<< <<< <<<] >>> >>> >>> >>> >>> > * [>] <<