Brainfuck minus -

From Esolang
Jump to: navigation, search

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,<-)}