17
5
It's a funny accident that this world happens to have just 1 time dimension, but it doesn't have to be like that. It's easy to imagine worlds with 2 or more time dimensions, and in those worlds you could build computers and run software on them, just like in this one.
The System
Here is a system for running Brainf*ck programs in two time dimensions:
The two time dimensions are x and y. Each Brainf*ck program consists of an x half-program, and a y half-program, e.g., a program could be
x: +>+
y: [-]
The two half-programs each have their own program pointer, but they share a single tape pointer (that is, they both operate on the same cell of the tape).
Time is 2-dimensional, so it consists of a grid of moments:
Moving along the x dimension, the x half-program executes one time step. Moving along the y dimension, the y half-program executes one time step.
So, for example, let's say the tape starts out as [0] 0 0 ([] represents the tape pointer) and the x/y programs are + and ->-. The execution of this program would look like this:
x y tape x-action y-action
0 0 [ 0] 0 0 + at 0 - at 0
1 0 [ 1] 0 0 (done) - at 0
0 1 [-1] 0 0 + at 0 move >
1 1 [ 0] 0 0 (done) move >
Notice that, as time moves in the y direction, the x half-program keeps doing the same thing over and over, because its time does not progress.
The tape at each moment includes the cumulative effect of all actions that feed into it (each action counts once). So, for example, the tape at time (2, 1) contains the cumulative effect of:
- the x-action from (0, 0)
- the x-action from (1, 0)
- the x-action from (0, 1)
- the x-action from (1, 1)
- the y-action from (0, 0)
- the y-action from (1, 0)
- the y-action from (2, 0)
Cumulative means:
- All the increments and decrements to a cell sum together.
- All the left (-1) and right (+1) movements to the tape pointer sum together.
Instruction pointers do not accumulate. Each half-program gets its instruction pointer from the previous moment in its dimension. That is, x program pointers progress only in the x dimension, and y program pointers progress only in the y dimension. So, for example, in the program ([], +) starting from [0] 0 0, the execution would be
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 0 0 0 + at 0 0 0
1 0 0 0 0 + at 0 2 (from jump) 0
0 1 1 0 0 0 1
1 1 2 0 0 1 (from NO jump) 1
Some more moments from the above (+, ->-) simulation are:
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 [ 0] 0 0 + at 0 - at 0 0 0
1 0 [ 1] 0 0 - at 0 1 0
2 0 [ 1] 0 0 - at 0 1 0
0 1 [-1] 0 0 + at 0 > 0 1
1 1 [ 0] 0 0 > 1 1
2 1 [-1] 0 0 > 1 1
0 2 -1 [ 0] 0 + at 1 - at 1 0 2
1 2 0 1 [ 0] - at 2 1 2
2 2 [-1] 1 0 - at 0 1 2
The Brainf*ck operators allowed are the following (they have their standard meaning):
+,-: increment, decrement;[,]: loop until zero (processing a[or]takes one time-step, as in standard Brainf*ck);<,>: move left/right on the tape.
Complex Example
For the program (>, +) starting with [0] 0 0:
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 [ 0] 0 0 > + at 0 0 0
1 0 0 [ 0] 0 + at 1 1 0
0 1 [ 1] 0 0 > 0 1
1 1 1 1 [ 0] 1 1
For (+, -) starting with [0] 0 0:
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 [ 0] 0 0 + at 0 - at 0 0 0
1 0 [ 1] 0 0 - at 0 1 0
0 1 [-1] 0 0 + at 0 0 1
1 1 [ 0] 0 0 1 1
Note that the tape ends as [0] 0 0 because each + and - happens twice, summing to 0.
For the program (>+, [-]) starting with [0] 0 0:
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 [ 0] 0 0 > 0 0
1 0 0 [ 0] 0 + at 1 1 0
2 0 0 [ 1] 0 2 0
0 1 [ 0] 0 0 > 0 3
1 1 0 0 [ 0] + at 2 1 3
2 1 0 1 [ 1] - at 2 2 1
0 2 [ 0] 0 0 > 0 3
1 2 [ 0] 0 0 + at 0 1 3
2 2 [ 1] 1 0 2 2
Diagram with Arrows
The below diagram shows how to calculate the actions and the tape:
The Puzzle
Write a 2D Brainf*ck program (with an x half-program and a y half-program) to run on a 3-cell tape, that satisfies both the following conditions:
- If the tape starts as
[0] 0 0, at time (5, 5) it has a0in the zeroth cell. - If the tape starts as
[1] 0 0, at time (5, 5) it has a0in the zeroth cell.
Shortest program meeting the requirements wins.
Owen
Posted 2017-04-06T16:34:58.873
Reputation: 389
Just to verify: What's the result of running
+and>? If it's1 1 [0](pretty crazy but it's what the spec seems to suggest), How do instruction pointers combine? If the two threads are+and[], then at1 2the data tape would be[3], but is the second instruction pointer inside the loop ([]+path), or outside ([+]path) or even illegal(+[])? – John Dvorak – 2017-04-06T17:07:57.840@JanDvorak Ah, I think I see what you're asking. I forgot to add the each program gets its instruction pointer from the adjacent moment in its dimension. I'll edit that in, and try running (
+,>) to see if I get the same result as you. – Owen – 2017-04-06T17:10:22.810This is a nice challenge but it needs an objective winning criterion to be able to rank answers. – Martin Ender – 2017-04-06T17:11:25.263
Please provide an example with two complex programs and with the tape and IPs in each cell – John Dvorak – 2017-04-06T17:13:05.240
@JanDvorak That's a good idea. I'll add a full example. – Owen – 2017-04-06T17:18:24.277
@MartinEnder OK, I added one. – Owen – 2017-04-06T17:18:55.157
3The challenge still isn't really clear to me. How exactly does time progress through the grid. According to your graphic it seems that I can arrive at
(1,1)through either(1,0)or(0,1), but it one program starts with>and one starts with+, then surely their relative order matters? – Martin Ender – 2017-04-06T17:20:40.793I take it that the X program pointer is defined by what the X program did in the previous X-cycle, and ignores what happened in the previous Y-cycle, and the Y program pointer ignores Y program pointer the -X of it? That's ... still kinda crazy but at least it's well defined. – John Dvorak – 2017-04-06T17:26:03.550
@MartinEnder That's true, there are two paths to (1, 1), but the tape and program are calculated so that the order does not matter. The tape at (1, 1) includes the sum of the actions leading there, the x-prog-ptr at (1, 1) is the result of running the x-program at (0, 1), not depending on the x-prog-ptr at (1, 0). That is, program pointers move through one time dimension only. – Owen – 2017-04-06T17:33:11.410
@JanDvorak Yes, that is correct. I agree it's not the most natural, but it's the best I could come up with. – Owen – 2017-04-06T17:35:06.560
@Owen I don't understand what this has to do with program pointers. If program
xstarts with>andystarts with+how do I know whether I end up with0 [1] 0or1 [0] 0at time(1,1)? – Martin Ender – 2017-04-06T17:35:12.550@MartinEnder you end up with
1 1 [0]. – John Dvorak – 2017-04-06T17:36:14.517@MartinEnder With programs (
>,+), at (1, 1) you will have1 1 [0]. – Owen – 2017-04-06T17:36:57.1572
Uh what. I think we need a chatroom.
– Martin Ender – 2017-04-06T17:37:22.470It's less a funny accident that we live in 3+1 and more the fact that literally no other combination makes physics work.
– Mego – 2018-02-11T02:07:43.600