Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Tetris is capable of universal computation

meatfighter.com

Post reply on HN
Print view View original

61–70 of 79 posts

Re: Tetris is capable of universal computation

#61

Post by zero__one »

woodrowbarlow wrote: post #38
zero__one wrote: post #32

Earlier quoted context omitted.

From https://meatfighter.com/tetromino-computer/input-language.ht... > In practice, IL programs direct the agent to construct a pile near the origin that progressively grows taller and wider. That being the case, it can work with a Tetris implementation that defines “row infinity” as a finite row whose index increases as a function of the number of spawns. In such an implementation, the agent emulates a semihard drop…

that's not really infinite, though, and other pages do describe it as truly infinite, e.g.: > When a newly spawned piece falls, it never gets closer to the floor due to the nature of infinity. i'm nitpicking, of course. everything described is possible with a sufficiently large board. you'll just have a time constraint to place each block.

For the method described in the paper to work, the infinite version of the game requires a semihard drop operation or something analogous as a legal move. In modern versions of Tetris, the rotation systems permit very unusual operations such as wall climbing or infinite lock delays, not to mention rotating in physically impossible ways. A semihard drop is not a big ask on an infinite playfield. It's within the spirit of the game.

Re: Tetris is capable of universal computation

#63

Post by zero__one »

kickofline wrote: post #50
Aardwolf wrote: post #49

Here'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…

relevant xkcd: https://xkcd.com/505/

There 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.

Re: Tetris is capable of universal computation

#64

Post by kwhitefoot »

Aardwolf wrote: post #49

Here'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…

If 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)

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.

A friend of mine in high school had a calculator like this one: 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

Re: Tetris is capable of universal computation

#65

Post by zero__one »

eouwt wrote: post #42
heavenlyblue wrote: post #19

Just 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.

Agreed...if you have to introduce an "agent" to make it complete, is it Tetris that's complete or Tetris + an agent?

Here is a list of Surprising Turing-complete things:

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?

Re: Tetris is capable of universal computation

#66

Post by pierreyoda »

aarchi wrote: post #51

I 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-w...

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 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?

Re: Tetris is capable of universal computation

#67

Post by glompers »

pierreyoda wrote: post #66
aarchi wrote: post #51

I 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-w...

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

Re: Tetris is capable of universal computation

#68

Post by gernb »

andyjohnson0 wrote: post #7

It 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 installati…

IIRC some people believe the universe at the smallest level just follows steps and these steps are basic and Turing complete.

Re: Tetris is capable of universal computation

#70

Post by adenozine »

askiiart wrote: post #21
adenozine wrote: post #6

Earlier quoted context omitted.

Suckerpinch 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.

I'm out of the loop, mind sharing a link to what you're talking about?

My post is a reply to one of Suckerpinch’s videos. You can just click the YouTube link in the parent post to mine.
Post reply on HN