9th June 2021, 11:38 PM
With the introduction of Teleport Blocks, the potential for PR2 to incorporate complex designs has increased astronomically. One of the first things that came to mind for me was the possibility of making Turing-complete programs in PR2 (explanation of Turing completeness here: https://www.youtube.com/watch?v=RPQD7-AOjMI).
The requirements for Turing completeness are as follows:
The trickiest thing about this problem is that it's very hard to read state without modifying it. In layman's terms, most of the time a level makes you branch into different paths based on a Push Block, you push the block in the process. This makes it impossible to repeatedly read the state of the Push Block, as simply reading it changes the state.
Here's an image of a module I've been working on:
![[Image: 2233e4a5989fea139e4615df9e06a7c9.png]](https://i.gyazo.com/2233e4a5989fea139e4615df9e06a7c9.png)
Usage Instructions:
Touch BLUE to write to the bit (it will alternate between its two states.) Touch PURPLE to read the bit. Depending on which state the bit is in, you will be returned to the control room (bottom) through either GREEN or RED.
Explanation:
Touching BLUE brings you to the upper left room. If the PB here is in the left position, the player will hit it, then hit the leftmost up arrow, hit ORANGE, and go to the top right room. Here, the player will be forced to move the PB to the up position before hitting BROWN and returning to the control room.
If when the player hits BLUE, the PB is in the right position, the player will hit the rightmost up arrow, hit YELLOW, teleport to the right of PB and push it to the left, then hit PINK. They will then ride along the arrows in the top right room and be forced to push the PB down before hitting GRAY and returning to the control room.
When the player hits PURPLE, they teleport to the top right room and ride along the arrows. If the PB is in the up position, they fall and hit RED. If the PB is in the down position, they go sideways and hit GREEN.
Next steps from here:
While this system seems relatively robust, it's not flawless. For instance, when the player teleports to ORANGE in top right, they're meant to hit the PB and set it to the up position. However, it's possible for the player to hold down and avoid hitting it, returning to the control room without flipping the bit as intended. Similarly, when the player teleports to PINK in top right, they can move right fast enough avoid setting the PB to the down position. (Reusable stat blocks would be amazing here - you could set a player's stats to 0/0/0 and basically force them to play the level like a Don't Move until an operation finishes, at which point you restore their stats to normal.)
Second, this is a LOT of overhead for managing just a single bit. Complex state machines will require a ridiculous amount of overhead to function.
Finally, this example has not been expanded upon with logic gates. I think logical completeness is probably possible, since it would be easy to construct a NOR gate (if the bit is TRUE for either of the gates, send them somewhere causing the branch to diverge) and NOR is logically complete, but the idea of making anything complicated with this seems like an absolute nightmare (I can't see myself making a level based on this stuff without some kind of macro.)
Anyway, I think it might be interesting to have some discussions about what we can do with PR2 now that we have Turing completeness. I've experimented with different rules (see the "follow the leader" game Horse) but the possibilities that are opened up by Turing completeness are far greater. People have built complex machines in the past (Suuper made a calculator once) but the requirement for the player not to move meant these levels weren't viable for anything resembling an actual game, since it relied on the honor system.
What are your thoughts?
The requirements for Turing completeness are as follows:
- Arbitrary memory that allows for reading and writing of data
- Conditional branching
The trickiest thing about this problem is that it's very hard to read state without modifying it. In layman's terms, most of the time a level makes you branch into different paths based on a Push Block, you push the block in the process. This makes it impossible to repeatedly read the state of the Push Block, as simply reading it changes the state.
Here's an image of a module I've been working on:
Usage Instructions:
Touch BLUE to write to the bit (it will alternate between its two states.) Touch PURPLE to read the bit. Depending on which state the bit is in, you will be returned to the control room (bottom) through either GREEN or RED.
Explanation:
Touching BLUE brings you to the upper left room. If the PB here is in the left position, the player will hit it, then hit the leftmost up arrow, hit ORANGE, and go to the top right room. Here, the player will be forced to move the PB to the up position before hitting BROWN and returning to the control room.
If when the player hits BLUE, the PB is in the right position, the player will hit the rightmost up arrow, hit YELLOW, teleport to the right of PB and push it to the left, then hit PINK. They will then ride along the arrows in the top right room and be forced to push the PB down before hitting GRAY and returning to the control room.
When the player hits PURPLE, they teleport to the top right room and ride along the arrows. If the PB is in the up position, they fall and hit RED. If the PB is in the down position, they go sideways and hit GREEN.
Next steps from here:
While this system seems relatively robust, it's not flawless. For instance, when the player teleports to ORANGE in top right, they're meant to hit the PB and set it to the up position. However, it's possible for the player to hold down and avoid hitting it, returning to the control room without flipping the bit as intended. Similarly, when the player teleports to PINK in top right, they can move right fast enough avoid setting the PB to the down position. (Reusable stat blocks would be amazing here - you could set a player's stats to 0/0/0 and basically force them to play the level like a Don't Move until an operation finishes, at which point you restore their stats to normal.)
Second, this is a LOT of overhead for managing just a single bit. Complex state machines will require a ridiculous amount of overhead to function.
Finally, this example has not been expanded upon with logic gates. I think logical completeness is probably possible, since it would be easy to construct a NOR gate (if the bit is TRUE for either of the gates, send them somewhere causing the branch to diverge) and NOR is logically complete, but the idea of making anything complicated with this seems like an absolute nightmare (I can't see myself making a level based on this stuff without some kind of macro.)
Anyway, I think it might be interesting to have some discussions about what we can do with PR2 now that we have Turing completeness. I've experimented with different rules (see the "follow the leader" game Horse) but the possibilities that are opened up by Turing completeness are far greater. People have built complex machines in the past (Suuper made a calculator once) but the requirement for the player not to move meant these levels weren't viable for anything resembling an actual game, since it relied on the honor system.
What are your thoughts?