10 ms·
Tetris is capable of universal computation
- deleted 4y ago[deleted]
- askiiart 4y agoAs for Tetris storage, see also: Harder Drives - https://youtu.be/JcJSW7Rprio https://youtu.be/JcJSW7Rprio The Tetris part starts at 15:00, but I'd highly recommend watching it all.
- adenozine 4y agoSuckerpinch is one of the best youtube channels out there, I love his work. I came here to link this once I saw the title, but you've already done it! He reminds me of what Forth people get so excited about, fitting so much into such small places.
- askiiart 4y agoI'm out of the loop, mind sharing a link to what you're talking about?
- adenozine 4y agoMy post is a reply to one of Suckerpinch’s videos. You can just click the YouTube link in the parent post to mine.
- UncleMeat 4y agoIf you like his stuff you should check out the sigbovik proceedings each year. Most of his videos are about his papers there and he has even more papers he doesn't make videos about! I don't think anybody else is making papers as interesting as his (about half are just jokes with no real content) but there are other gems of a similar "work hard on a fundamentally silly problem" vein.
- alexb_ 4y agoOne of my favorites was an old one (I think 2013?) about "DollarCoin", a new cryptocurrency that is minted using a video of someone lighting a dollar bill on fire.
- dado3212 4y agoIs there an easy way to look all of them up?
- UncleMeat 4y agoPDFs here: https://sigbovik.org/ https://sigbovik.org/
- loxias 4y agohttps://www.youtube.com/watch?v=HLRdruqQfRk https://www.youtube.com/watch?v=HLRdruqQfRk (Uppestcase and Lowestcase Letters [advances in derp learning]) Is pure gold. I don't wanna spoil it, it just keeps getting better and better as the video progresses. I laughed so hard. If by some freak chance I ever become wealthy, I want to sponsor this sort of research.
- UncleMeat 4y agoThis one is my least favorite one of his, actually. The big problem is that it just didn't actually really work. Tom7 seems to start these projects only a couple weeks before sigbovik deadline (an incredible feat I marvel at regularly) so it is no surprise that some of them end up falling apart (harder drives with the cue carts failed too) but I really wish this one had worked. The C Compiler that only emits the printable bytes is my favorite one by a mile. The executables can only jump forward and only by an offset between two modestly large numbers. This makes laying out the code in the executable a really interesting problem and relies on weird old behavior where the instruction pointer can wrap on overflow. Wild!
- EvanAnderson 4y agoCame here to post this myself, too. Tom7 is a treasure.
- zero__one 4y agoThe same idea appeared earlier on this page: https://meatfighter.com/tetrisprinteralgorithm/ https://meatfighter.com/tetrisprinteralgorithm/
- deleted 4y ago[deleted]
- mysterydip 4y agoThis is amazing. I can't think of a practical use for this, but at the same time I think the world is better for its existing.
- subw00f 4y agoIt's art.
- andyjohnson0 4y agoIt seems like I quite often see posts here about how $thing$ can perform universal computation, or simulate a UTM, or whatever. And obviously the HN readership selects for these articles. But is there any significance to be found in all these things having this attribute? Does it tell us anything about the universality of computation as a property of the universe? I seem to recall that sed and C++ template installation are known to be Turing complete - and i can kind of understand that as they are designed to manipulate information, even if it is surprising that their limited syntax provides enough "power" for universality. But Tetris was not designed with this capability, yet it has it. Same with Minecraft - within which it is apparently possible to implement a Turing machine. I've seen claims that DNA replication and other naturally occuring systems may be capable of universal computation too. So in the bigger picture, whats going on here?
- modarts 4y agoA sprawling read on the topic https://www.amazon.com/G%C3%B6del-Escher-Bach-Eternal-Golden/dp/0465026567 https://www.amazon.com/G%C3%B6del-Escher-Bach-Eternal-Golden...
- andyjohnson0 4y agoYep. I first read that when I was twelve. I wouldnt say I understood much back then, or even now after a number of re-readings. But its an amazing book. "Sprawling" is one word that I would use to describe it.
- distcs 4y ago> But is there any significance to be found in all these things having this attribute? Is there any significance of a beautiful painting of a magnificent sunset over mountain meadow with horses grazing?
- andyjohnson0 4y ago> Is there any significance of a beautiful painting of a magnificent sunset over mountain meadow with horses grazing? Yes, but it was designed that way. By a person. For other people. Its unlikely to be perceived as "beautiful" by a whale or an oak tree or whatever. But if things that weren't designed to do computation, or even designed at all, nevertheless appear to be capable of it, what does that tell us about computation? Given that the fundamental physical behaviour of the universe can (maybe) be described computationally, is computation special in some way?
- selcuka 4y agoObviously the ultimate test is: Can it run Doom?
- mavhc 4y agoYes, just very slowly
- hypertele-Xii 4y agoActually, no, there's not enough RAM to run Doom. Not even slowly.
- undersuit 4y agoJust increase the size of the play board to infinity.
- heavenlyblue 4y agoJust a note, this doesn't seem to create an isomorphism between _actively_playing_ with randomised figures, tetris. It just explains how one could create a turing machine based on controlled positioning of the figures. So essentially this is boring.
- eouwt 4y agoAgreed...if you have to introduce an "agent" to make it complete, is it Tetris that's complete or Tetris + an agent?
- zero__one 4y agoHere is a list of Surprising Turing-complete things: https://www.gwern.net/Turing-complete https://www.gwern.net/Turing-complete Wang tiles are on the list. Are they Turing-complete by themselves? Or do they become Turing-complete only when an agent attempts to arrange them?
- woodrowbarlow 4y agothe claim is that this is theoretically possible in stock tetris with only one modification: an infinite board (with a floor). the infinite board solves piece randomization, because you can have a "junkyard" where you dump pieces until you get the one you want. it also solves the time pressure, because blocks spawned at row inifinity will never reach the canvas until you hard-drop them. finally, it prevents rows from clearing because they have infinite width (so the game won't interfere with your construction). their concept for gates is that if you nudge a block at a certain row as it's falling, it will either shift one column over or be blocked. this page is a good visualization: https://meatfighter.com/tetromino-computer/inverter-not.html https://meatfighter.com/tetromino-computer/inverter-not.html except... once you hard-drop a block in tetris, you can't nudge it. and if you don't hard-drop it, it will never reach your canvas. they kind-of hand-wave this in the section "infinite playfield". after describing the mechanics of a hard drop, they say: > A more generalized version, the semihard drop, attempts to vertically translate the piece from “row infinity” to a specified, finite row. if the fall timer can't get the block into a finite row, how would a player (without hard-dropping)? loved reading through this, though. the animations were perfect for describing the mechanism! very high-quality documentation for a fun project.
- UncleMeat 4y agoNES tetris has a RNG that can be manipulated so you always get the piece you want as long as you never need duplicates. You don't even need a junkyard.
- woodrowbarlow 4y agointeresting! unfortunately the board would be too small to build more than one or two gates before you start to run into row clearing and the ceiling. edit: is this your article? thank you for the wonderful post!
- UncleMeat 4y agoNo it is not my article. I just know weird things from other articles I also didn't write involving doing weird stuff with NES tetris.
- torben-friis 4y agoI was wondering how could they achieve it despite the randomness in piece generation, but they assume infinite width to avoid that issue altogether.
- jklinger410 4y agoWhat a really neat waste of time
- charcircuit 4y agoTerris is officially defined by The Tetris Company to have a 10x40 playfield with 10x20 of it being visible. They do not allow for arbitrary sizes. If you have to change the game for it to be capable of universal computation then you shouldn't claim that the game is capable of it.
- Aardwolf 4y agoHere'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 bands or springs but not looking practical to combine many together in a useful circuit
- kickofline 4y agorelevant xkcd: https://xkcd.com/505/ https://xkcd.com/505/
- DesiLurker 4y agoisn't this the core idea behind Wolfram Hypergraph thing? ref: https://writings.stephenwolfram.com/2020/04/finally-we-may-have-a-path-to-the-fundamental-theory-of-physics-and-its-beautiful/ https://writings.stephenwolfram.com/2020/04/finally-we-may-h...
- zero__one 4y agoThere are several issues with that comic: 1. In finite time, it is not possible for a human to create an infinite row of rocks. 2. The academic paper for Rule 110 describes it as "weakly universal" rather than Turing-complete because it depends on an infinite pattern. 3. The rocks act as RAM, not the CPU. The human is applying the rules. The human is the CPU. In the Tetris paper, the agent is just a TAS recording while Tetris acts as RAM and the CPU.
- jacobr1 4y agoNot quite what your are asking: but you could probably easily build a slide-rule, once you bootstrap the basic tools needed.
- kwhitefoot 4y agoIf you have basic metal working facilities you aren't far from being able draw wire and then you can make relays. It might take a while to replicate Konrad Zuse's machines but I think that it might be simpler to do that than go for purely mechanical computers, see https://en.wikipedia.org/wiki/Z3_(computer) https://en.wikipedia.org/wiki/Z3_(computer) But if you only want a calculator the there are plenty of examples from Blaise Pascal onwards: https://en.wikipedia.org/wiki/Pascal's_calculator https://en.wikipedia.org/wiki/Pascal's_calculator. A friend of mine in high school had a calculator like this one: https://www.computinghistory.org.uk/det/4584/Magic-Brain-Calculator/ https://www.computinghistory.org.uk/det/4584/Magic-Brain-Cal... that could be made quite easily. And of course the serious calculator enthusiast would have a Curta. Needs a bit more than basic metal working I suspect: https://en.wikipedia.org/wiki/Curta https://en.wikipedia.org/wiki/Curta
- aarchi 4y agoI just got a terrible idea: combine this with another project, that built Tetris in Conway's Game of Life. That would enable executing an arbitrary program in Tetris, simulated in Game of Life. https://codegolf.stackexchange.com/questions/11880/build-a-working-game-of-tetris-in-conways-game-of-life/142673#142673 https://codegolf.stackexchange.com/questions/11880/build-a-w...
- sophacles 4y agoAnd of course the program to run on the simulated tetris is Conway's game of Life.
- pierreyoda 4y agoThis 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 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 field, but it's far beyond my abilities for the moment - which may never change without years of research in my free time, which I cannot realistically do before I'm retired basically. If it wasn't, I would love to work on a new library specifically built for the kind of things like your idea, with the API aimed at working with metapixels-based "hardware", but with the lowest-level constructs (maybe by far) being thinks like RAM or CPU caches as building blocks - while still being able to zoom to the lowest level of cells in the renderer. But it's basically R&D and HPC combined if one wants to offer an interesting alternative to the established libraries. From what I know of upcoming hardware, such a library may have to wait a couple of years and basically target (as in, full buy-in, maybe at the programming language-level, certainly in tooling) the next Apple Silicon-like (or beyond) breakthough in commonly accessible hardware for a nice, "free" performance boost. Maybe GPUs are next?
- glompers 4y agoside 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 https://en.wikipedia.org/wiki/Vision_processing_unit
- _nora_ 4y agoThis feels like it'd be an awesome spy thing back in the Cold War days.
- postalrat 4y agoIs there a theory that anything that requires a certain level of computation to solve is itself capable of that level of computation?
- deleted 4y ago[deleted]