Is there a theory that anything that requires a certain level of computation to solve is itself capable of that level of computation?
Tetris is capable of universal computation
71–79 of 79 posts
Re: Tetris is capable of universal computation
#72[deleted]
Re: Tetris is capable of universal computation
#73Earlier quoted context omitted.
You want to know how the Tetromino does memory allocation and garbage collection? I don't think the infinite board is that big of a deal. Turing Machines and Lambda Calculus have no limits on their memory space and we implement analogues of them in our limited memory space.
i'm talking about the theoretical model, not the implementation details. i'm focusing on the definition of "infinity" here: > On an infinite playfield, tetrominoes spawn at “row infinity” and column zero. When a newly spawned piece falls, it never gets closer to the floor due to the nature of infinity. This means, in finite—though potentially vast—time, the agent can shift the piece into any finite column. And once i…
Why isn't it? It just hides time passage. Oh no the computer gets a higher score... but it's not playing Tetris, the high score doesn't matter.
For instance: "For instance, if the agent emulates a semihard drop with a finite number of soft drops, then it will let a gravity drop serve as the final soft drop. "
Re: Tetris is capable of universal computation
#74Earlier quoted context omitted.
This is an excellent link, well known in the "community" around this. To add to it, here's a famous and really clear sub-2 minutes representation of the scales involved if it helps make things clearer, for those who've never seen the scales involved: https://www.youtube.com/watch?v=xP5-iIeKXE8 (and that's "just" the Game of Life in the Game of Life). I think I would enjoy helping push the state of the art in this fie…
side note, the TPU acronym is already taken by tensor processing units so Tetris GPUs will have to be something else… https://en.wikipedia.org/wiki/Vision_processing_unit
That's really interesting, I did not know about that, thanks for the link ! It's highly specific but could make a lot of cool "wow-effect" products or software suddenly viable, especially if it percolates to your average consumer hardware some way or another.
Re: Tetris is capable of universal computation
#75Earlier quoted context omitted.
i'm talking about the theoretical model, not the implementation details. i'm focusing on the definition of "infinity" here: > On an infinite playfield, tetrominoes spawn at “row infinity” and column zero. When a newly spawned piece falls, it never gets closer to the floor due to the nature of infinity. This means, in finite—though potentially vast—time, the agent can shift the piece into any finite column. And once i…
Why isn't it? It just hides time passage. Oh no the computer gets a higher score... but it's not playing Tetris, the high score doesn't matter. For instance: "For instance, if the agent emulates a semihard drop with a finite number of soft drops, then it will let a gravity drop serve as the final soft drop. "
it's math: no amount of soft-drops (or gravity drops) can bring a block from row infinity to row x. subtracting one from infinity is fruitless.
Re: Tetris is capable of universal computation
#76Earlier quoted context omitted.
Why isn't it? It just hides time passage. Oh no the computer gets a higher score... but it's not playing Tetris, the high score doesn't matter. For instance: "For instance, if the agent emulates a semihard drop with a finite number of soft drops, then it will let a gravity drop serve as the final soft drop. "
it's math: no amount of soft-drops (or gravity drops) can bring a block from row infinity to row x. subtracting one from infinity is fruitless.
And you can't have an infinite tape, but no one is out there saying the Turing Machine is fake.
Consider this. Our physical implementations of turing machines work even though we don't have an infinite memory. We do encounter some limitations because of such.
The Tetrino also works. You can create it and run it on a finite board. It would be limited just at our physical machines are limited without access to infinite memory.
Re: Tetris is capable of universal computation
#77Here's something I wonder: Imagine you're stuck on an island or in a forest, and you're stuck with what you find in nature only, or perhaps you get very primitive technology (e.g. basic metal working only): What's the simplest way you could build some (mechanical) logic gates to do some form of useful computation? I've seen some from lego or 3D printed ones, but they all look very complicated, e.g. requiring rubber b…
Water and dominos are possibilities https://www.youtube.com/watch?v=IxXaizglscw
Re: Tetris is capable of universal computation
#78Earlier quoted context omitted.
it's math: no amount of soft-drops (or gravity drops) can bring a block from row infinity to row x. subtracting one from infinity is fruitless.
And you can't have an infinite tape, but no one is out there saying the Turing Machine is fake. Consider this. Our physical implementations of turing machines work even though we don't have an infinite memory. We do encounter some limitations because of such. The Tetrino also works. You can create it and run it on a finite board. It would be limited just at our physical machines are limited without access to infinite…
i'm not saying it's impossible to model an infinite board using software (that's quite possible). i'm saying that if it's possible to soft-drop a block to an arbitrary row, then the model of infinity is faulty and inconsistent. and, unfortunately, both the infinite board and the soft-drop are required fundamental underpinnings of the proposed mechanism for computation.
Re: Tetris is capable of universal computation
#79Earlier quoted context omitted.
And you can't have an infinite tape, but no one is out there saying the Turing Machine is fake. Consider this. Our physical implementations of turing machines work even though we don't have an infinite memory. We do encounter some limitations because of such. The Tetrino also works. You can create it and run it on a finite board. It would be limited just at our physical machines are limited without access to infinite…
i'm not saying it's impossible to model an infinite board using software (that's quite possible). i'm saying that if it's possible to soft-drop a block to an arbitrary row, then the model of infinity is faulty and inconsistent . and, unfortunately, both the infinite board and the soft-drop are required fundamental underpinnings of the proposed mechanism for computation.
And I'm saying you don't need a board to be infinite to do work, you just need a board to be infinite to compute all work. Just like you need infinite tape for a Turing Machine to be able to compute all work.