Newton's Third Nightmare
Jump to navigation
Jump to search
.------------------------.
.=/==========================\=.
|/ \|
: NEWTON'S THIRD NIGHTMARE :
|\ /|
'=\==========================/='
'------------------------'
Newton's Third Nightmare is a two-dimensional tile-based language with finite forces, movable
objects, unstoppable forces and immovable objects drafted in October 2021 by User:RocketRace. Its
programs are infinite 2D grids of tiles with integer coordinates. Each tile has a defined behavior.
The program executes one tick at a time. During ticks, tiles will apply / receive forces from
/ to their surrounding tiles in any of the four cardinal directions.
== Forces ==
Forces can point in any of the four cardinal directions. Forces are additive, so two unit forces
applied on a tile in one direction during one tick are equivalent to a single 2-unit force
applied to the tile. A force will attempt to "push" every single tile along the path of the
force a number of units equal to the magnitude of the force. This force is propagated linearly
(tile by tile, starting from the source), but its effects are instantaneous. If two forces of
orthogonal directions are applied to a tile in one tick, the resulting "push" is computed in both
directions individually before being applied to both simultaneously. The magnitude of a force
is often annotated with a capital M. If two forces of opposite directions are applied to a tile
in one tick, the behavior is determined by their "order":
== Orders & strength ==
Forces have "orders", each order outclassing those below it. A force of order N is deemed stronger
than a force of any magnitude of order N-1. The highest order force is denoted an "unstoppable
force". If a tile experiences a force of order N and an opposite force of order N + 1, the net
force applied will be equivalent to that of the higher order force. The order of a force is often
annotated with a capital O.
Interactions between two tiles, one applying a force to the other, are decided by the "strength"
of the tiles and the force being applied. Tiles have a hierarchy of "strengths", each outclassing
those below it. The highest "strength" tile is denoted an "immovable tile", and the lowest strength
(0) is a vacuum (empty tile). Note that an immovable tile is considered to be stronger than an
unstoppable force. (Why couldn't philosophers figure it out before this?) The strength of a tile
determines its ability to withstand orders of forces.
== Interactions ==
If a tile attempts to apply a force of order X & magnitude N to a target tile of strength Y, the
following outcomes are possible:
1) Y == 0
The chain of tiles up to this tile are marked to be displaced one unit in the direction of the
force. The newly moved tile will attempt to apply a force of order X, magnitude N - 1 to the next
block in front of it, unless N - 1 == 0 in which case this force stops being processed. The force
is said to be "resolved".
.-----.
| |
----[A]---> (empty)
| |
'-----'
2) Y is immovable
The force is reflected across the target tile. The original force stops being processed, and an
unstoppable force starting from the original source of the force with magnitude N and an opposite
direction as the original is initiated. This force is said to be "reflected".
.-----. ( ) .-----.
| /----( )--X |
| [A] | ( omitted ) | [B] |
<---X | ( ) | |
'-----' ( ) '-----'
3) Y != 0, Y is not immovable, X >= Y
The force continues to propagate along the cardinal unchanged. Note that if X is unstoppable and Y
is immovable, the previous case is hit rather than this one.
.-----. .-----.
| | | |
---[A]-----[B]--->
| | | |
'-----' '-----'
4) Y != 0, Y is not immovable, X < Y
As with scenario 2, the force is reflected. This reflected force has order Y and magnitude N.
After all forces have been resolved, all tiles marked to be moved are displaced. At this point, a
tick is said to be elapsed. Situations that prevent resolution are detailed below.
== Stress ==
Because an immovable object overrules an unstoppable force, it is possible for a chain of tiles
experience an unstoppable force in one direction, which is then reflected back and forth in an
infinite loop. Such a chain is said to be under "stress". A chain under stress with an unstoppable
force of magnitude N will perform the following:
1. The "origin direction" is determined. This is the direction of the first instance of an unstoppable
force that was processed along this chain.
2. Of all the tiles in the chain, those with the lowest order are replaced with empty tiles ("destroyed").
3. If the source of the force is destroyed, the following step does not occur. The stress force
stops being processed.
4. If the number of tiles destroyed (which we name D) is greater than or equal to N, the stress
has been resolved. Otherwise, the chain's stress stops being processed, and a new unstoppable force
originating at the source of the force and facing the "origin direction" with a magnitude of (N - D)
begins being processed.
It can be shown that all chains under stress as described above will eventually resolve. This is left
as an exercise to the reader. Implementors may also note that point 4 only occurs if the magnitude of
the force is greater than the number of tiles in a chain.
== Pistons ==
We take a short interlude to introduce the primary catalysts for force -- the "pistons". A piston has
two forms: Extended and contracted. In extended form, the piston consists of two tiles: The piston body
and the piston head. In contracted form, it is represented by a single tile. Each form of piston can
face in one of the four cardinal directions, which determines the direction of force instantiated by
the piston.
A contracted piston tile is "powered" whenever it is adjacent in one of four cardinal directions to a
tile that generates "power". This check is performed at the start of a tick. Certain tiles will generate
power; any such behavior is specified for each tile. When powered, a contracted piston will instantiate
a force in its designated direction, attempting to "push" the piston head out of the piston body. When
the force eventually dissipates (as long as the piston body has not been destroyed under stress), there
will be an empty tile either in front of the piston tile or behind it. If there is a space in front of
it, that tile is replaced with a piston head. Otherwise, the tile behind will be replaced with a piston
body and the original piston tile will be replaced with a piston head. The direction of each of these
tiles is the same as the tile of the original piston.
If a piston body tile is not powered at the start of a tick, its corresponding piston head will
attempt to pull into the piston body. This applies a force only to the piston head, directed towards
the piston body. In normal circumstances, this has the simple effect of removing the piston head and
replacing the piston body with a contracted piston. However, as detailed in the next section, the
piston head may apply additional forces as a result of its pull.
== Rigid bodies & phantom forces ==
Up till this point, we have only discussed linear chains of tiles with one or more sources of force
in either of two opposing directions. However, Newton's Third Nightmare also features tiles which
can be bound together, and thus behave as rigid bodies. The boundary between two such tiles is
considered "rigid", and a collection of tiles sharing rigid boundaries is considered a "rigid unit".
As shown below, a force may be applied to one of the tiles in a direction orthogonal to tiles'
connection:
^ ^ ^
.---|---. .---|---. .---|---.
| | | | | | | | |
| [A]~~|~~~|~~[B]~~|~~~|~~[C] |
| | | ^ | | ^ | s |
'---|---' | '-------' | '---s---'
| +-----------+---> s
| | .---s---.
FORCE | | s |
| | [D] |
RIGID BOUNDARIES | |
MARKED WITH THESE '-------'
In this case, if tile A is deemed to propagate the force upwards, then tiles B and C (but not D)
will also propagate an identical force upward alongside tile A, as a result of being part of the
same rigid unit. Only non-rigid boundaries of the rigid unit in the direction of the force will
propagate a force. These newly created forces will be "phantomly bound", with the following implications:
1) If any of the forces propagate through a rigid unit, then only one of the forces that propagate
will be considered a candidate for further phantom binding. The newly created forces will be bound
to the original phantomly bound forces. For instance, if the example above had forces propagate
into both tiles A and B, still only three phantomly bound forces will be created:
^ ^ ^
.---|---. .---|---. .---|---.
| | | | | | | | |
| [A]~~|~~~|~~[B]~~|~~~|~~[C] |
| | | | | | | s |
'---|---' '---|---' '---s---'
| | s
| | .---s---.
FORCE FORCE | s |
| [D] |
| |
'-------'
2) If at least one of the forces are reflected, then the non-reflecting forces are discarded. Of
the reflected forces, only the one with the maximal order and magnitude (selected order first,
then magnitude) is reflected to the source. For instance, if A reflected off a non-immovable tile,
B resolved and C reflected off an immovable tile, the reflected force will be unstoppable.
3) If all of the forces are resolved, then all of the forces takes effect. All tiles in chains
propagated through by the phantomly bound forces will be displaced. In addition, the rigid body
itself will be displaced in its entirety by the appropriate amount of units.
4) If a phantomly bound force attempt to propagate through a rigid body it has already propagated
through, then the force will be resolved there. This is an example of a "phantom cycle", shown below.
Although tile E does not share digid boundaries with the other tiles, forces from G are still able
to reach B. If the other phantomly bound forces ABCDH also resolve, then tile E will be displaced
upwards as if it were shifting into an empty space.
^ ^ ^ ^
.---|---. .---|---. .---|---. .---|---.
| | | | | | | | | | | |
| [A]~~|~~~|~~[B]~~|~~~|~~[C]~~|~~~|~~[D]~~|
| | | | | | | | s |
'---|---' '-------' '-------' '---s---'
| RESOLVED s
FORCE .---^---. .---s---.
| | | | s |
| [E] | | [F] |
| | | | s |
'---|---' '---s---'
| ^ s
.---|---. .---|---. .---s---.
| | | | | | | s |
| [G]~~|~~~|~~[H]~~|~~~|~~[I] |
| | | | | |
'-------' '-------' '-------'
5) If a phantomly bound force attempts to propagate through the source of the force in question,
then the rigid body is said to be under "phantom stress". In such a case, any chains formed by
the forces propagating through the source will behave as if under stress. In the example below,
tiles ABCEFGH are one rigid unit, and the FORCE tile is a piston. Only the chain including FORCE
is under stress; the chain with D does not go through the force source and thus behaves normally
under clause 4. As the only tile in the chain is the piston, this results in the destruction of
the piston.
^ ^ ^
.---|---. .---|---. .---|---.
| | | | | | | | |
| [A]~~|~~~|~~[B]~~|~~~|~~[C] |
| | | | | | s |
'---|---' '-------' '-------'
| RESOLVED s
.---|---. .---^---. .---s---.
| | | | | | | s |
| FORCE | | [D] | | [E] |
| | | | | | s |
'-------' '---|---' '---s---'
!!! | s
.---^---. .---|---. .---s---.
| | | | | | | s |
| [F]~~|~~~|~~[G]~~|~~~|~~[H] |
| | | | | |
'-------' '-------' '-------'
== Conflict resolution ==
We introduce the concept of a "conflict", or a set of orthogonal forces that influences the other's
behavior. A conflict can happen when two tiles attempt to push a tile into the same space, when a
force would attempt to push a tile, which if resolved, would prevent another force's resolution,
... in any scenario where the outcome of one force is dependant on the outcome of another. The
result of such a scenario is determined by "conflict resolution". An example is shown below.
.-------. .-------.
| | | |
| FORCE---->| ??? |
| | | |
'-------' '-------'
^
.---|---.
| | |
| FORCE |
| |
'-------'
The first measure in conflict resolution is prioritization. That is, the outcome of the highest
order forces is guaranteed to take place before the outcome of a lower order one. If conflicting
forces are of the same order, then the highest magnitude force is prioritized. While this measure
can account for many conflicts, there are some scenarios which require more.
The individual resolved forces are collected together. At this phase of a tick, all forces in the
board have a method of direct resolution, and tile displacements have already been calculated.
If any space in the grid would be set to occupy more than one tile after these displacements,
that space in the grid is set to be immovable, regardless of the strength of the tile there. The
forces that propagated through such tiles are processed again from the beginning with this
additional information. (This causes them to reflect their forces, potentially resolving elsewhere,
going under stress, or causing further conflicts.)
If a new conflict occurs after this step, the conflict resolution algorithm is reapplied. Any spaces
set to be temporarily immovable at any point in this recursive algorithm are kept immovable until
the end of the tick.
== Input & output ==
Programs are able to commuicate with the outside world using a bitstream. Interpreters may choose
to interpret these bits any way they wish. The program has access to a readable buffer of incoming
bits, as well as a channel of bits it can write to. Specific IO-related tiles are described below.
== Bibliography of tiles ==
Here are the symbols used by the language for tiles. The table also marks their strength as well
as any additional features the tiles may hold.
+---------------+---------+-----------+----------------------------+
| Tile | Symbols | Strength | Notes |
+---------------+---------+-----------+----------------------------+
| Blank space | " " | 0 | |
+---------------+---------+-----------+----------------------------+
| Fragile tile | "+" | 1 | |
+---------------+---------+-----------+----------------------------+
| Stable tile | "#" | immovable | |
+---------------+---------+-----------+----------------------------+
| Generator | "@" | 2 | Powers adjacent tiles. |
+---------------+---------+-----------+----------------------------+
| Sticky tile | "%" | 2 | Any tiles adjacent to this |
| | | | become one rigid unit. |
+---------------+---------+-----------+----------------------------+
| Contracted | "<" "^" | | Symbols are left-, up-, |
| piston | ">" "v" | 3 | right-, and down-facing. |
| | | | Applies a M1, O2 force. |
+---------------+---------+-----------+----------------------------+
| Piston head | "[" "~" | 2 | Symbols are left-, up-, |
| | "]" "_" | | right-, and down-facing. |
+---------------+---------+-----------+----------------------------+
| Piston body | ")" "u" | 3 | Symbols are left-, up-, |
| | "(" "n" | | right-, and down-facing. |
+---------------+---------+-----------+----------------------------+
| | | | If powered, clones tiles |
| | | | adjacent to it, pushing |
| Replicator | "$" | 3 | the new tiles from it like |
| | | | 4-way piston heads. |
| | | | Applies a M1, O2 force. |
+---------------+---------+-----------+----------------------------+
| | | | If powered, reads the most |
| | | | recent input bit and if |
| | | | it is 1, powers adjacent |
| Asker | "?" | 2 | tiles. Every asker reads |
| | | | the same bit within a |
| | | | single tick. A bit is only |
| | | | popped from the buffer if |
| | | | read by askers. |
+---------------+---------+-----------+----------------------------+
| | | | If powered, writes a 1 to |
| | | | the output stream. If |
| Screamer | "!" | 2 | multiple screamers write |
| | | | in one tick, only one is |
| | | | recorded. |
+---------------+---------+-----------+----------------------------+
| | | | If powered, writes a 0 to |
| | | | the output stream. If |
| Holder | "," | 2 | multiple holders write in |
| | | | one tick, only one is |
| | | | recorded. 0s overridden by |
| | | | screamer 1s. |
+---------------+---------+-----------+----------------------------+
== Open conjectures ==
* Newton's Third Nightmare is Turing complete.
* Computing a single tick of Newton's Third Nightmare is NP-complete. (It may even be undecidable.)