Talk:BackFlip

Is BackFlip selfmodifying?

I'm unsure whether BackFlip should categorize as self-modifying or not. Although the program does change itself, each mirror/arrow stays in the same place all program, so I'm reluctant to classify it like that. --ais523 15:42, 18 May 2006 (UTC)

Nice language. It depends on what you consider code and what you consider data. You might consider an analogy with computer memory, the bits stay in the same place but sometimes they change between 0 and 1. --Ørjan 20:10, 18 May 2006 (UTC)

Definitely self-modifying, as it modifies itself. Those mirrors are instructions, right? It doesn't matter if they stay in the same place in the program, as long as they change. As in this language there's no separate memory and memory is just a feature left for user to build, I'd definitely call it self-modifying as during its execution the actual program is modified in flipping mirrors. By the way, I love the idea of flipping mirrors! --Keymaker 01:15, 19 May 2006 (UTC)

How to make infinite memory

Maybe you could make infinite memory by adding one command * that makes it move memory pointer in same direction that program pointer is moving in. Each cell of the memory is one configuration of the program area (all start the same as input program) --Zzo38 01:51, 19 May 2006

Aargh, I just wrote another suggestion myself and it was lost without trace! Well, trying again: You could make a command @ such that when the program pointer winds around it, it reaches a new, separately modifiable copy of the original program. Winding around in the opposite direction returns to the previous copy. Hitting the command itself just bounces back. --Ørjan 21:05, 18 May 2006 (UTC)

Here's a command that would probably cause Turing-completeness, both by allowing infinite loops and by extending memory, and is also reversible: the & command duplicates its own row in the program, putting the copy immediately beneath its own row, and rebounds. This would allow for bignum registers and for infinite loops (e.g. keep extending the loop counter used in the first example program, after rotating 90 degrees). It seems a bit against the spirit of the language, though. --ais523 07:14, 19 May 2006 (UTC)

That is only partially reversible (one-to-one but not onto) as running the command in reverse depends on the two rows being equal (or else the inverse command is not itself reversible). Also it lacks symmetry, but that could be fixed by saying the command duplicates the row or column in the opposite direction of where the pointer came from. --Ørjan 11:57, 19 May 2006 (UTC)

That's why I feel uneasy about &. It's a method I used on another esolang I haven't posted to the wiki yet, but it just feels wrong here. Your [Ørjan's] @ suggestion looks interesting; how would multiple @s interact, or are you only allowing one of them? --ais523 12:20, 19 May 2006 (UTC)

Multiple @s could act in various ways, depending on which mathematical group you use to combine them. A simple way would be to count their winding numbers separately, that is to use a commutative group. Then to get back to the same place you only need to wind the right number around each. Then the copies of the program could be indexed by a list of integers.

Maximally, one could use the non-commutative free group, which counts not only the number of times wound around each @ but also keeps track of the order. Then you would need to wind backwards in approximately the same path, as if the @ were columns in a building and the instruction pointer were a dog tied to a long leash. In this case the index would be a complicated algebraic expression, an easier way to keep track might then be to let each copy link to the neighboring ones.

(I should mention that this gives an infinite tree structure of program copies. --Ørjan 12:56, 19 May 2006 (UTC))

Most complicatedly, one could have other symbols than @ that behaved in different ways, some might commute (with the same or another symbol) and some might not, and some might return you to the same place after a finite number of rounds... you have all the freedom of group theory. --Ørjan 12:43, 19 May 2006 (UTC)

The * command allows infinite loops, infinite memory, and is reversible (it is a reverse of itself when running in the opposite direction, just as the arrow commands are). Here is a example of a infinite loop program:

>*\
\</

--Zzo38 19:20, 23 May 2006 (UTC)

An infinite loop with @ can be made as easily:

V \
 @
\ /

--Ørjan 20:16, 23 May 2006 (UTC) (edited --Ørjan 11:45, 8 Jun 2006 (UTC))

Coming back to this subject over 10 years later: is there any reason why we can't just tile the plane with the input program? Admittedly defining termination becomes difficult in that case (although an obvious answer is "redirect program flow back to its original location"). Implementing an infinite loop under those circumstances would be trivial. --ais523 07:08, 7 April 2017 (UTC)

That could also work. I like that too. How might the variant of :≠ be made to take advantage of this? --Zzo38 (talk) 07:47, 20 January 2018 (UTC)

A BackFlip storage device

The following device has four memory states (A, B, C, and D), and three commands (X, Y, and Z).

• In state A, X and Y change to state B, and Z remains in state A.
• In state B, X and Y change to state C, and Z changes to state D. X will also cause the event function to run.
• In state C, X and Y change to state D, and Z changes to state B. Y will also cause the event function to run.
• In state D, X and Y change to state A, and Z changes to state C.

Unfortunately, it behaves in an undefined manner if you try to send it commands recursively (intuitively, this is because otherwise you could create an infinite loop if the event function called X four times). The #s round the edge are purely comments to set this register off. (I'm optimistic that this can actually store something; using just states A and C, XY is a negate instruction like @ in Smallfuck, and YYXY calls the event function in state C but not in state A). The code example below is one possibility for state A. (There is another arrangement of arrows and mirrors it sometimes reaches that acts exactly like state A.)

#######
 VV   # Input from the left on this row does X.
  \ V # Input from the left on this row does Z.
   V  # Input from the left on this row does Y.
# V   #
#>\<  #
#^/^  #
#V <  #
# >\< #
# ^/^ #
#> VV #
#  >\<#
#  ^/<#
    < # Outputs to the left for the event function,
####### which should return by backtracking.

--ais523 12:29, 19 May 2006 (UTC)

I just noticed I'd commented the Y and Z commands the wrong way round orignally. I've swapped them the correct way round in the above storage device. --ais523 16:38, 19 May 2006 (UTC)

The device does seem to be usable for computation; I've made it into an esoteric programming language of its own (ABCDXYZ). --ais523 13:46, 24 May 2006 (UTC)

I believe the lower part can be simplified a bit:

######
 VV  # Input from the left on this row does X.
  \ V# Input from the left on this row does Z.
   V # Input from the left on this row does Y.
# V  #
#>\< #
#^/^ #
#V < #
# >\<#
# ^/^#
#> V #
 \ < # Outputs to the left for the event function,
#^   # which should return by backtracking.
######

--Ørjan 15:22, 30 May 2006 (UTC)

Wanted patterns

Unless there is some fundamental limitation not yet discovered, there are a couple of patterns that ought to exist in BackFlip and which might be useful as building blocks.

First, a T-shaped intersection with 3 designated exits, in which any instruction pointer coming from the left leaves downward and any instruction pointer coming upward leaves toward the right, indefinitely. (An IP coming from the right may do anything, but 3 such intersections can be fit together to ensure all directions are treated symmetrically.) Given this and the "fixed" mirror pattern, it is easy to build guiding systems to connect exits to each other in any one-to-one manner.

Secondly, a single bit storage device (also with 3 designated exits in a T-shape). An IP coming from below flips the device and bounces. In the zero state, IPs from the left and right also bounce, while in the one state, they pass through, in either case without changing the state. --Ørjan 21:17, 30 May 2006 (UTC)

I'm starting to think there's some parity rule blocking those, but I'm not entirely sure what it is yet. --ais523 09:12, 5 Jun 2006 (UTC)

The first pattern can be made out of the second pattern (here, B refers to the second pattern, and * refers to the exits):

    V
*\\B/B *
 > / /<
   ^ ^
 >\ /<
  ^>\ ^
    *

Initially, the B on the left must rebound and the B on the right must allow passing through. (It works by remembering which entrance the pointer came in through, and routing it out through the correct exit, resetting the Bs if neccesary.) --ais523 14:02, 13 Jun 2006 (UTC)

Nice! By the way, the first pattern may also be theoretically important because it allows you to switch between patterns in which the same exits are used both to enter and to leave, and patterns where "input" exits and "output" exits are kept separate. The second type can be composed with each other, making such programs into a mathematical category. If the intersection pattern exists then all Backflip programs can be so composed.

Strangely enough, even if such T-patterns do not exist, it might still be possible to make a translation of combined input/output patterns into separated ones. Given the "arrows are unnecessary" proof, the only problem is to translate a flipping mirror: find a pattern that acts like a mirror where all exits have been split into input/output using the intersection pattern (T):

*   T*
*  T *
* T  *
*T   *
>\// <
> \ /<
 ^^^^

Note that the translation of T itself is trivial: it does nothing more than connect inputs to outputs, which is easy if they are separated. --Ørjan 16:46, 13 Jun 2006 (UTC)

It's actually easy to do this for an arrow (this also shows a generalisation of arrows to any number of exits):

 VVVV
*/   *
* \  *
*  \ *
*   \*
 ^<<<

--ais523 11:56, 15 Jun 2006 (UTC)

Nice. I take you mean the ^<<< part as a generalization of arrows. I guess I should post my analysis of arrow patterns:

Arrow patterns

Let's say that two arrows are connected if one of them is pointing at the other. This property is preserved by execution (although which one is pointing at the other may change.) Thus we can divide any pattern consisting of just arrows into connected groups. There are exactly two types of them:

• A block is a group where none of the arrows is pointing outwards from the group (as I wrote about in the article.) A block always causes the pointer to bounce back.
• A tree is a group where exactly one arrow points outwards from the group. It acts like a generalized arrow: Entering by any arrow causes that one to point outwards instead, and you leave by the other one.

--Ørjan 13:58, 15 Jun 2006 (UTC)

Arrows are unnecessary

It seems that the only symbols needed for a BackFlip-equivalent are the flipping mirror and a symbol that always rebounds (or equivalently, flipping mirrors and fixed mirrors). To prove this, I introduce G, a 'modified arrow':

 R R
R///R
 /R/
R/\/R
 R R

(Here, R is a symbol that always rebounds.) This acts exactly like a normal backtracking arrow, except that an 'end-on hit', which normally causes a rebound, instead causes both the IP and the modified arrow to rotate anticlockwise. This modified arrow is currently pointing upwards. A normal backtracking arrow can be constructed like this:

 ^
>G<
 ^

(with G pointing upwards, and the arrow pointing upwards). This contains arrows, but each arrow only needs to consider two directions rather than 4, and a two-directional arrow can be implemented like this:

 R R
R/ \R
R\G/R
 R R

(with G pointing upwards, and the arrow pointing upwards). Combining these three patterns makes a backtracking arrow out of nothing but flipping mirrors and rebounders.

Although this is unlikely to be of practical use, it may aid proofs that patterns are impossible (as arrows need not be considered), and could lead to a bounded-storage tarpit (unfortunately, the name Flip is already taken). --ais523 09:12, 5 Jun 2006 (UTC)

I think you can also make an arrow like this:

 ^
>/<
 ^

I also modified your two-directional arrow design and got this:

 R R
R//\R
R\ \R
R R R
R\\/R
 R R

Two of R's are decorative. Here's a version with directed rebound symbols:

 - -
|//\|
|\-\|
|\\/|
 - -

And here's another implementation of an arrow (D is a reference to a doll in XOR):

   R R
  R/ \R
 R//\/\R
R/\RRR\\R
  \RDR\
R\\RRR\/R
 R\////R
  R\ /R
   R R

Orisphera (talk) 15:20, 31 January 2021 (UTC)

Flipping mirrors are insufficient

Having flipping mirrors and any one of

• symbols always rebounding
• symbols with a direction which always rebounds
• fixed mirrors
• arrows

gives you all of the others (showing that you can get arrows is the difficult part, shown by ais523 above).

However, flipping mirrors alone are not enough. To put this precisely:

• Theorem: A pattern containing only flipping mirrors cannot have less than four exits in a closed set, and exits in all four directions must be included.

By a closed set of exits I mean a set of exits such that if you enter by any combination of them in order, you always leave through another exit in the set.

Proof: Assume there is a pattern with a closed set of exits none of which leave upwards. Choose one with as few mirrors as possible (there must be at least two). Find the rightmost mirror m in the topmost line of the pattern, and the leftmost mirror n in the bottom line (they must be distinct). A picture:

*******m
***********
  n********

It must be possible to hit m as many times we want by entering the closed set of exits in some order, because otherwise we could remove m from the pattern entirely after it is no longer possible to hit it, contradicting the minimal number of mirrors.

Before one of the first two hits m must be a /, and we are either leaving or entering the pattern through m, which must therefore have an exit upwards (in which case we have a contradiction) or rightwards (assumed from now). Assuming it is only rightwards, then m cannot ever be a \ when the pointer is not in the pattern, as you could then send the pointer back in from the right and leave upwards. So m must start as /, but then we cannot ever hit m without having entered from it, as that would leave the pattern with m=\.

But then we can again remove m entirely from the pattern, a contradiction, unless there are no other mirrors having exits. But that is not possible either, because by a symmetrical argument, the mirror n must also have exits.

So, we are left with no option other than our pattern having an upwards exit. The other directions follow symmetrically. --Ørjan 21:13, 6 Jun 2006 (UTC)

One possibility is to make the program area a torus, rather than having execution terminate when the IP goes off an edge. That way, a mirror on a row/column by itself would be a symbol with a direction that always rebounds. However, this would cause programs to get very large, and some other method of starting/terminating the program would be needed. --ais523 14:27, 15 Jun 2006 (UTC)

Yes, changing the topology is an option, although in a sense that is exactly what fixed mirrors buy you: the ability to use an arbitrary graph instead of a plane. I have the idea of programming BackFlip on a metalevel by using a circuit description language (MetaFlip?), which could if you want be automatically translated back using fixed mirrors. It would then only require flipping mirrors as the basic building block. For example an always bouncing circuit with two exits, corresponding to your single mirror on a toroidal line, could be described as

bounce(a b) { mirror(a c b c) }

A restriction is that since variables must be paired, circuits must have an even number of exits. --Ørjan 16:15, 15 Jun 2006 (UTC)

Implementation?

Backflip has been categorized as Implemented, but there is no link to the implementation. --Ørjan 12:52, 19 May 2006 (UTC)

I only implemented it yesterday, and the implementation isn't on the Internet (and is quite rudimentary; you have to keep pressing [Return] to step through the program). Does anyone know how to add it to http://esoteric.voxelperfect.net/files? --ais523 13:02, 19 May 2006 (UTC)

From the description, it looks like you have to ask graue to put it there. --Ørjan 13:31, 19 May 2006 (UTC)

The (greatly improved) implementation is now in the Archive, and a link to it is on the BackFlip wiki page. --ais523 11:07, 28 May 2006 (UTC)

Explanations Of Unclear Things

These things should be explained/clarified:

• Explain what a parity is.

  Even vs. odd number of something. --Ørjan 12:31, 16 April 2008 (UTC)

  What does that mean?--Melab 15:41, 16 April 2008 (UTC)

  The parity of a number is whether it's even or odd; two numbers have the same parity if they're either both even or odd, and a different parity otherwise. Some things 'preserve' parity; that is, they can't change whether a number is even or odd (although they can change its values). --ais523 20:55, 16 April 2008 (UTC)

• Explain how extensions work.

  Probably implementation-dependent. --Ørjan 12:31, 16 April 2008 (UTC)

  Yes, pretty much. The way my implementation does it is to output a specific character whenever the IP touches an extension character, and then cause the IP to rebound. --ais523 20:55, 16 April 2008 (UTC)

• Explain these parts of "Possibly useful patterns":
  • "In order to create a turning path which is not essentially changed by following it, the one-sided fixed mirror patterns (as in the first example) may be used:" and its example need to be explained for something I forgot.

    The two patterns shown do the same thing: if the IP comes in on the second row from the left, it changes direction and goes down, and if the IP comes in from below on the left, it changes direction and goes left (thus it's a 'one-sided fixed mirror'). The patterns change into each other when this happens, but both do the same thing (thus 'not essentially changed'). --ais523 20:55, 16 April 2008 (UTC)

  • "It is easy to build patterns from which anything bounces back:" and its exampled need to be explained why the 2nd and 3rd setup options' first lines are offset by 1 down compared to the 1st option's first line.

    The blocks are approximately centered on the line, for pretty formatting. --Ørjan 12:31, 16 April 2008 (UTC)

    The point is that if any of the arrows on the outside are touched, the IP will rebound. The location of the block is less important. --ais523 20:55, 16 April 2008 (UTC)

• How can a moving arrow retrieve data?

  I'm not sure I understand. What are you referring to? --ais523 20:55, 16 April 2008 (UTC)

  I mean it talked about ways for it to return data if it exits the program how does it tell you what it retrieved.--Melab 15:32, 19 April 2008 (UTC)

  It doesn't, and so you have to run the program under a debugger to be sure that it's working correctly. (This situation is rare in commonly-used languages, but resonably common in esoteric languages, as output does not affect a language's computational class.) The program models a computation, which conceptually is what a program is, rather than carrying out a task (as you may be more used to programs doing). --ais523 11:02, 21 April 2008 (UTC)

--Melab 01:30, 16 April 2008 (UTC)

Boolean Logic

I realized that in order to do boolean logic, you only needed a one-time use bit storage device, that is, you only need to be able to read it once (and write to it once) after that its state can be destroyed. Such a one-time use bit storage can be created from the counter example. I then created NOT and AND gates (OR is unnecessary, but shouldn't be too hard) and a duplicator that copies the input to multiple outputs. Using these, it should be possible to compute any boolean function. --Weux082690 (talk) 15:42, 4 August 2016 (UTC)

Similarity to ants/turmites

I think the idea of BackFlip and some of its extensions seems to be similar to the idea of ants and turmites. Basically, the IP acts like an ant (a turmite (see below) that changes direction relative to the previous direction) except its behavior can depend on the direction it is going. It also acts like a turmite (a 2D Turing machine) that has 4 states and always moves according to its state.

Let's say there is one instruction that turns the IP clockwise/anticlockwise and flips and no other instructions (even no no-ops). Let's say it starts somewhere in the middle of the program, which, if it is infinite, has the same state of almost all instances of the instruction. Orisphera (talk) 15:38, 31 January 2021 (UTC)

I thought this was an interesting observation, so I decided to experiment and discovered that it's actually pretty easy to simulate Langton's Ant just using mirrors! a grid of mirrors, with states alternating in a checkerboard pattern, will behave like langton's ant if the instruction pointer is dropped in the middle of the grid (with the slight caveat that in order to make the program look exactly like langton's ant after running, the mirrors need to be manually inverted in a checkerboard pattern)

of course, in practice you can't start the IP in the middle of the program, but that's also fairly easy to simulate -- for example:

          \\\\\\\\\\\
          V<<<<<<<<<<
/\/\/\/\/\ /\/\/\/\/\
\/\/\/\/\/ \/\/\/\/\/
/\/\/\/\/\ /\/\/\/\/\
\/\/\/\/\/ \/\/\/\/\/
/\/\/\/\/\ /\/\/\/\/\
\/\/\/\/\/ \/\/\/\/\/
/\/\/\/\/\ /\/\/\/\/\
\/\/\/\/\/\\/\/\/\/\/
/\/\/\/\/\ /\/\/\/\/\
\/\/\/\/\/ \/\/\/\/\/
/\/\/\/\/\ /\/\/\/\/\
\/\/\/\/\/ \/\/\/\/\/
/\/\/\/\/\ /\/\/\/\/\
\/\/\/\/\/ \/\/\/\/\/
          ^

the structure in the top-right will initially direct the IP into the middle of the grid, and afterward will bounce the IP back (for a limited number of times) to prevent it from leaving. the mirror in the center of the program directs the IP into the grid, and then afterwards has essentially no effect due to the bouncing structure. (there's also an arrow at the bottom to theoretically bounce the IP if it get directed downward by the center mirror, but I suspect that that might not actually ever happen, for parity-related reasons)

I've also made a larger version that's big enough to run until it starts moving in the highway pattern: https://gist.github.com/Arctenik/37e66544eef41dea1035cd93108c7583

Arctenik (talk) 11:08, 31 January 2022 (UTC)

Cool! --Ørjan (talk) 01:16, 1 February 2022 (UTC)

An alternative instruction set

Here's an alternative instruction set: an instruction I called a G-mirror and the first pattern in Wanted patterns (and, of course, a no-op).

A G-mirror is a pattern that lets the IP pass through it without any changes in one direction (which changes when it's flipped) and when the IP comes from the other direction it turns and the G-mirror flips.

--(this comment by Orisphera‎ at 15:47, 31 January 2021 UTC; please sign your comments with ~~~~)