Is ZZT-OOP Turing Complete?
Moderators: Commodore, Zenith Nadir
Is ZZT-OOP Turing Complete?
That is to say, do you think everything computable on a Turing-Complete machine is also representable on a theoretical boundary-less ZZT board, with no limit to the amount of objects?
I'm nupanick.
-
Quantum P.
- Level 17 Accordion Thief
- Posts: 1433
- Joined: Fri Sep 12, 2003 1:41 am
- Location: Edmonds, WA
- Contact:
If you can implement an interpreter for a Turing-complete language in ZZT, then ZZT itself ought to be Turing-complete. Assuming, like you said, no restriction on board size/program size/number of objects, etc.
-
Alexis Janson
- wacky morning DJ
- Posts: 307
- Joined: Fri Feb 20, 2004 1:05 am
i've actually MADE a turing machine in zzt, it was a piece of cake!
http://zzt.org/zgames/f/FLIMTOWN.zip
TRY TO KEEP UP
http://zzt.org/zgames/f/FLIMTOWN.zip
TRY TO KEEP UP
Okay, I'm considering the ZZT Game of Life engine I mentioned, and here's my concept of it: "cell" objects on a grid with one space between them, in two sections of the board. The two sections of the oversize board will act as a buffer, so one can be modified without changing the first. Every object on the first board has a state (set using Binders Keepers?) that causes it to
a. tell all other cell objects to surround themselves with boulders or such.
II check in each direction to see if it's blocked.
3.1) send a message to the corresponding cell on the mirror layout to change, and
3.2: change accordingly for next cycle.
Massive? Definitely. Possible? Maybe. Any better ideas?
a. tell all other cell objects to surround themselves with boulders or such.
II check in each direction to see if it's blocked.
3.1) send a message to the corresponding cell on the mirror layout to change, and
3.2: change accordingly for next cycle.
Massive? Definitely. Possible? Maybe. Any better ideas?
I'm nupanick.
-
Quantum P.
- Level 17 Accordion Thief
- Posts: 1433
- Joined: Fri Sep 12, 2003 1:41 am
- Location: Edmonds, WA
- Contact:
I realize this is tl;dr, so I broke it into three parts. Pretend I only posted the readable ones!
1. You could probably get away with not using an extra buffer. Each object would (1) put junk all around if it's alive, (2) check to see #if blocked, (3) decide whether to be alive or not, (4) wait half a second, and (5) change state to match decision made in Step 3. Notice Step 4! Everyone decides whether to be dead or alive next turn, but they don't change right away -- instead, they wait until everything is settled, then change.
2. In Conway's Game of Life, diagonally adjacent cells also count as neighbors. Unfortunately, #if blocked was not meant for checking diagonals.
Option 1: Have the objects move around to check the diagonals. Each object moves off the grid, checking out its surroundings in more detail. This might be more trouble than it's worth, especially if you have a whole bunch of objects trying to do this at the same time.
Option 2: Do some stat hacking. In an editor like KevEdit, you can manually modify an object's X Step and Y Step, which are the number of spaces the object walks per cycle. Set them both to one, and the object walks southeast. Now you can use flow for southeast, cw flow for southwest, ccw flow for northeast, and opp flow for northwest -- this should work for both #put and for #if blocked. The main drawback is that the object will be constantly on the move, but this can be cancelled out by keeping the object in a loop which runs \opp flow.
Option 3: Don't care. It's not Conway's Game of Life if you don't check the diagonals, but it's still a cellular automaton, and it's impressive enough being in ZZT and all.
3. Remember that you're limited to 150 objects, which restricts the maximum size of the Game of Life grid. If this turns out to be a significant restriction, you could have the state of the game stored entirely in terrain -- for example, use green normal to represent live cells and blue fake for dead cells. Then you'd need a series of objects to walk past the terrain, counting up the number of live cells and marking cells for life/death.
The above is what I was thinking. The objects would scroll from left to right, and they would be placed such that the rightmost ones run first. Each light gray arrow would check #if blocked s to detect any living cells -- if detected, it would #give gems 1. Then the red arrow would change the current cell, depending on how many gems the player had. To mark a live cell for death, it would #put s blue normal, and to mark a dead cell for life, it would #put s green fake. The dark gray arrows would then check for life, only this time running #take gems 1. This is to make sure that the gems counter only represents the number of living cells in a 3x3 region on the grid. After the objects scan each row, they return to their original position, #change blue normal blue fake, and #change green fake green normal.
Of course, this is far from optimal (it's really slow, we actually need fewer than 7 objects per row, you could scan multiple rows at a time using more objects and multiple counters, there might be a way to remove the spaces between cells on the grid, etc...), and it might not be worth trying to optimize the system -- but this gives you an idea of what I was thinking of. On second thought, to reduce code complexity, it might be more helpful to add more objects to the setup -- each cycle, the gray arrows check their surroundings and the red arrow marks the tile for life or death.
Binders Keepers would probably work well enough, though. Using Binders Keepers, a 20x7 grid with spaces between each tile would be 13 tiles tall and 39 wide, which consumes 140 objects and is roughly a third of the total area of the board.
1. You could probably get away with not using an extra buffer. Each object would (1) put junk all around if it's alive, (2) check to see #if blocked, (3) decide whether to be alive or not, (4) wait half a second, and (5) change state to match decision made in Step 3. Notice Step 4! Everyone decides whether to be dead or alive next turn, but they don't change right away -- instead, they wait until everything is settled, then change.
2. In Conway's Game of Life, diagonally adjacent cells also count as neighbors. Unfortunately, #if blocked was not meant for checking diagonals.
Option 1: Have the objects move around to check the diagonals. Each object moves off the grid, checking out its surroundings in more detail. This might be more trouble than it's worth, especially if you have a whole bunch of objects trying to do this at the same time.
Option 2: Do some stat hacking. In an editor like KevEdit, you can manually modify an object's X Step and Y Step, which are the number of spaces the object walks per cycle. Set them both to one, and the object walks southeast. Now you can use flow for southeast, cw flow for southwest, ccw flow for northeast, and opp flow for northwest -- this should work for both #put and for #if blocked. The main drawback is that the object will be constantly on the move, but this can be cancelled out by keeping the object in a loop which runs \opp flow.
Option 3: Don't care. It's not Conway's Game of Life if you don't check the diagonals, but it's still a cellular automaton, and it's impressive enough being in ZZT and all.
3. Remember that you're limited to 150 objects, which restricts the maximum size of the Game of Life grid. If this turns out to be a significant restriction, you could have the state of the game stored entirely in terrain -- for example, use green normal to represent live cells and blue fake for dead cells. Then you'd need a series of objects to walk past the terrain, counting up the number of live cells and marking cells for life/death.
The above is what I was thinking. The objects would scroll from left to right, and they would be placed such that the rightmost ones run first. Each light gray arrow would check #if blocked s to detect any living cells -- if detected, it would #give gems 1. Then the red arrow would change the current cell, depending on how many gems the player had. To mark a live cell for death, it would #put s blue normal, and to mark a dead cell for life, it would #put s green fake. The dark gray arrows would then check for life, only this time running #take gems 1. This is to make sure that the gems counter only represents the number of living cells in a 3x3 region on the grid. After the objects scan each row, they return to their original position, #change blue normal blue fake, and #change green fake green normal.
Of course, this is far from optimal (it's really slow, we actually need fewer than 7 objects per row, you could scan multiple rows at a time using more objects and multiple counters, there might be a way to remove the spaces between cells on the grid, etc...), and it might not be worth trying to optimize the system -- but this gives you an idea of what I was thinking of. On second thought, to reduce code complexity, it might be more helpful to add more objects to the setup -- each cycle, the gray arrows check their surroundings and the red arrow marks the tile for life or death.
Binders Keepers would probably work well enough, though. Using Binders Keepers, a 20x7 grid with spaces between each tile would be 13 tiles tall and 39 wide, which consumes 140 objects and is roughly a third of the total area of the board.
-
Alexis Janson
- wacky morning DJ
- Posts: 307
- Joined: Fri Feb 20, 2004 1:05 am
I'll keep an eye out for it next time I play. I personally spent most of the time that I tolerated it being amazed with the hacking tricks, like the well-stocked illusion board and the small-size boards. Do you know if that could be done in kevedit or if you'd have to modify individual bytes to get those results? Also found the infinite regress room, enjoyed playing the game-within-a-game.
Oh, and I thought of a neat way to check diagonals. Fill the spaces between the grid with solid objects, use some x-step and y-step modifications, and just the color of the surrounding objects. Would require LOTS of #put-ing over one piece at a time, #change-ing the rest, and then checking #if any, but it could be done in an idealistic ZZT-based turing machine with no size limitations. It would of course be incredibly slow.
Oh, and I thought of a neat way to check diagonals. Fill the spaces between the grid with solid objects, use some x-step and y-step modifications, and just the color of the surrounding objects. Would require LOTS of #put-ing over one piece at a time, #change-ing the rest, and then checking #if any, but it could be done in an idealistic ZZT-based turing machine with no size limitations. It would of course be incredibly slow.
I'm nupanick.
-
Alexis Janson
- wacky morning DJ
- Posts: 307
- Joined: Fri Feb 20, 2004 1:05 am
I don't know what you're talking about. I did do it in kevedit.Nupanick wrote:I personally spent most of the time that I tolerated it being amazed with the hacking tricks, like the well-stocked illusion board and the small-size boards. Do you know if that could be done in kevedit or if you'd have to modify individual bytes to get those results?
-
Zenith Nadir
- this is my hammer
- Posts: 2767
- Joined: Wed Mar 12, 2003 11:40 am
- Location: between the black and white spiders
i would have thought the prolific use of cut and paste would have been a tip-off that flimsy town of zzt was made in kevedit, personally...
anyway, the best thing in that game is not any turing machine code, but the board edge/player clone inter-board engine which makes the player always appear in a set place when entering another board
also, the zzt version of this picture, which conceals a hidden passage:
(WARNING: POST CONTAINS SPOILERS which you have already read)
anyway, the best thing in that game is not any turing machine code, but the board edge/player clone inter-board engine which makes the player always appear in a set place when entering another board
also, the zzt version of this picture, which conceals a hidden passage:
(WARNING: POST CONTAINS SPOILERS which you have already read)
he looked upon the world and saw it was still depraved 
Overall: Rotton egg for breakfast
Overall: Rotton egg for breakfast
Woah, I'd never seen brainfuck before, that's cool! And yeah, gingermuffins made an interpreter for it, a one-board engine that keeps track of all the values and code instructions. You set up a program and hit 'run,' very cool. I'm still working out the more complicated stuff, but I can make a program that multiplies the first input value by the second and outputs the result.
So, yeah, as a matter of principle, ZZT is turing complete because it can run brainfuck programs and brainfuck is turing complete. Neato!
Now... theoretically, this means that a sufficiently long brainfuck program can simulate all the built-in objects in ZZT... but ehh, I don't feel like making a meta-ZZT right now, and it'd probably be WAY too big to fit in one board, anyway. And making meta-ZZT-OOP would be tedious, you'd have to input each symbol bit by bit, but it could be done in principle.
So, yeah, as a matter of principle, ZZT is turing complete because it can run brainfuck programs and brainfuck is turing complete. Neato!
Now... theoretically, this means that a sufficiently long brainfuck program can simulate all the built-in objects in ZZT... but ehh, I don't feel like making a meta-ZZT right now, and it'd probably be WAY too big to fit in one board, anyway. And making meta-ZZT-OOP would be tedious, you'd have to input each symbol bit by bit, but it could be done in principle.
I'm nupanick.
-
Quantum P.
- Level 17 Accordion Thief
- Posts: 1433
- Joined: Fri Sep 12, 2003 1:41 am
- Location: Edmonds, WA
- Contact:
:(Quantum P. wrote:If you can implement an interpreter for a Turing-complete language in ZZT, then ZZT itself ought to be Turing-complete. Assuming, like you said, no restriction on board size/program size/number of objects, etc.